An Optimized Sparse Approximate Matrix Multiply for Matrices with Decay
Authors:
- Nicolas BockNBNicolas Bock
- Matt ChallacombeMCMatt Challacombe
- 1 January 2013
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 35 (1) , C72-C98
Abstract
We present an optimized single-precision implementation of the sparse approximate matrix multiply (SpAMM}) [M. Challacombe and N. Bock, arXiv 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 general matrix-matrix multiply (SGEMM}) for dense quantum chemical matrices, while outperforming SGEMM with a cross-over already for small matrices ($n \sim 1000$). Relative to naive implementations of SpAMM using Intel's Math Kernel Library or AMD's Core Math Library, 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 2x to 3x speedups.
Keywords
All Related Versions
This publication has 104 references indexed in Scilit:
- The Combinatorics of Cache Misses during Matrix MultiplicationJournal of Computer and System Sciences, 2001
- A general parallel sparse-blocked matrix multiply for linear scaling SCF theoryComputer Physics Communications, 2000
- Canonical purification of the density matrix in electronic-structure theoryPhysical Review B, 1998
- Linear-scaling quantum mechanical calculations of biological molecules: The divide-and-conquer approachComputational Materials Science, 1998
- Linear scaling methods for electronic structure calculations and quantum molecular dynamics simulationsCurrent Opinion in Solid State and Materials Science, 1996
- A portable parallel particle programComputer Physics Communications, 1995
- Hierarchical N-body methodsComputer Physics Communications, 1988
- Decay rates for inverses of band matricesMathematics of Computation, 1984
- Stability of fast algorithms for matrix multiplicationNumerische Mathematik, 1980
- Sur une courbe, qui remplit toute une aire planeMathematische Annalen, 1890