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$
7
  • 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, 2016 at 19:28
  • 3
    $\begingroup$ @RainerP. Make into an answer? $\endgroup$ Feb 21, 2016 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$
    – user555045
    Feb 21, 2016 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$
    – user555045
    Feb 21, 2016 at 22:18
  • 2
    $\begingroup$ see also is matrix multiplied by transpose something special? / Mathematics $\endgroup$
    – vzn
    Feb 24, 2016 at 16:40

1 Answer 1

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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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