An Optimized Sparse Approximate Matrix Multiply for Matrices with Decay
This work provides a practical, optimized algorithm for fast matrix multiplication in quantum chemistry, offering speedups over standard libraries for matrices with decay.
The paper presents an optimized single-precision implementation of the Sparse Approximate Matrix Multiply (SpAMM) for matrices with decay, achieving O(n log n) complexity. The optimized version outperforms SGEMM for matrices as small as n~1000 and is significantly faster than naive implementations using MKL or ACML.
We present an optimized single-precision implementation of the Sparse Approximate Matrix Multiply (\SpAMM{}) [M. Challacombe and N. Bock, arXiv {\bf 1011.3534} (2010)], a fast algorithm for matrix-matrix multiplication for matrices with decay that achieves an $\mathcal{O} (n \log n)$ computational complexity with respect to matrix dimension $n$. We find that the max norm of the error achieved with a \SpAMM{} tolerance below $2 \times 10^{-8}$ is lower than that of the single-precision {\tt SGEMM} for dense quantum chemical matrices, while outperforming {\tt SGEMM} with a cross-over already for small matrices ($n \sim 1000$). Relative to naive implementations of \SpAMM{} using Intel's Math Kernel Library ({\tt MKL}) or AMD's Core Math Library ({\tt ACML}), our optimized version is found to be significantly faster. Detailed performance comparisons are made for quantum chemical matrices with differently structured sub-blocks. Finally, we discuss the potential of improved hardware prefetch to yield 2--3x speedups.