# How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?

Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k << n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the number of disk accesses?

Are there known algorithms for this problem? I searched for external matrix multiplication etc. but couldn't find much.

• The answers you are searching for are pretty well documented in wikipedia articles about efficient matrix multiplication, cache-oblivious algorithms and cache behavior of matrix multiplication algorithms. – Rainer P. Feb 21 '16 at 19:28
• @RainerP. Make into an answer? – Yuval Filmus Feb 21 '16 at 20:11
• Since $X^TX$ only involves dots between columns, a simple algorithm suggests itself: go back and forth through the columns (and a shorter run every time, no point calculating every dot both ways around, you already know the result is symmetric). Every time you turn around, for a short while everything is cached. Also the access pattern is completely predictable and contiguous so you can prefetch like mad. Obviously not asymptotically optimal though. – harold Feb 21 '16 at 22:10
• Since that is then just picking every pair from an array (the elements are vectors but that's fine), this should apply – harold Feb 21 '16 at 22:18
• – vzn Feb 24 '16 at 16:40