6
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Rainer P. Feb 21 '16 at 19:28
  • 3
    $\begingroup$ @RainerP. Make into an answer? $\endgroup$ – Yuval Filmus Feb 21 '16 at 20:11
  • 1
    $\begingroup$ 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. $\endgroup$ – harold Feb 21 '16 at 22:10
  • 1
    $\begingroup$ Since that is then just picking every pair from an array (the elements are vectors but that's fine), this should apply $\endgroup$ – harold Feb 21 '16 at 22:18
  • 2
    $\begingroup$ see also is matrix multiplied by transpose something special? / Mathematics $\endgroup$ – vzn Feb 24 '16 at 16:40
3
$\begingroup$

"Blocked matrix multiplication" is one way to optimize matrix multiplication for memory access.

From "Using Blocking to Increase Temporal Locality" by Bryant and O’Hallaron (2012):

Blocking a matrix multiply routine works by partitioning the matrices into submatrices and then exploiting the mathematical fact that these submatrices can be manipulated just like scalars.

"The cache performance and optimizations of blocked algorithms" by Lam, Rothbrg, and Wolf (1991):

...presents cache performance data for blocked programs and evaluates several optimizations to improve this performance.

More lecture notes:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.