An Optimized Sparse Approximate Matrix Multiply for Matrices with Decay

摘要

We present an optimized single-precision implementation of the SparseApproximate Matrix Multiply (SpAMM{}) [M. Challacombe and N. Bock, arXiv {f1011.3534} (2010)], a fast algorithm for matrix-matrix multiplication formatrices with decay that achieves an $mathcal{O} (n log n)$ computationalcomplexity with respect to matrix dimension $n$. We find that the max norm ofthe error achieved with a SpAMM{} tolerance below $2 imes 10^{-8}$ is lowerthan that of the single-precision {t SGEMM} for dense quantum chemicalmatrices, while outperforming {t SGEMM} with a cross-over already for smallmatrices ($n sim 1000$). Relative to naive implementations of SpAMM{} usingIntel's Math Kernel Library ({t MKL}) or AMD's Core Math Library ({tACML}), our optimized version is found to be significantly faster. Detailedperformance comparisons are made for quantum chemical matrices with differentlystructured sub-blocks. Finally, we discuss the potential of improved hardwareprefetch to yield 2--3x speedups.