Tuning Strassen's Matrix Multiplication for Memory Efficiency

Strassen's algorithm for matrix multiplication gains its lower arithmetic complexityatthe expense of reduced locality of reference, which makes it challenging to implement the algorithm e#ciently on a modern machine with a hierarchical memory system. We report on an implementation of this algorithm that uses several unconventional techniques to make the algorithm memory-friendly. First, the algorithm internally uses a non-standard arraylayout known as Morton order that is based on a quad-tree decomposition of the matrix. Second, we dynamically select the recursion truncation point to minimize padding without a#ecting the performance of the algorithm, whichwe can do by virtue of the cache behavior of the Morton ordering. Each technique is critical for performance, and their combination as done in our code multiplies their e#ectiveness. Performance comparisons of our implementation with that of competing implementations show that our implementation often outperforms the altern..