SpAMM swMATH ID: 12769 Software Authors: Bock, Nicolas; Challacombe, Matt Description: An optimized sparse approximate matrix multiply for matrices with decay. We present an optimized single-precision implementation of the sparse approximate matrix multiply (SpAMM) [M. Challacombe and N. Bock, “Fast multiplication of matrices with decay”, arXiv:1011.3534 (2010)], a fast algorithm for matrix-matrix multiplication for matrices with decay that achieves an 𝒪(nlogn) computational complexity with respect to matrix dimension n. We find that the max norm of the error achieved with a SpAMM tolerance below 2×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∼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. Homepage: http://epubs.siam.org/doi/abs/10.1137/120870761 Keywords: sparse approximate matrix multiply; sparse linear algebra; SpAMM; reduced complexity algorithm; quantum chemistry; \(N\)-body; matrices with decay; numerical examples Related Software: CHARM++; SUMMA; ONETEP; SparseMatrix; TASCEL; FreeON; Ergo; Gromacs; METIS; PETSc; Krylstat; Eigtool; CSparse; SpGEMM; symrcm; Trilinos; NWChem; Quantum Espresso; ChaNGa; 2HOT Cited in: 7 Publications all top 5 Cited by 24 Authors 2 Benzi, Michele 2 Bock, Nicolas 2 Challacombe, Matt 1 Artemov, Anton G. 1 Azad, Ariful 1 Ballard, Grey M. 1 Boito, Paola 1 Buluç, Aydın 1 Demmel, James Weldon 1 Ghale, Purnima 1 Grigori, Laura 1 Hahn, Georg 1 Kalé, Laxmikant V. 1 Kroonblawd, Matthew P. 1 Mniszewski, Sue 1 Negre, Christian F. A. 1 Pavel, Robert S. 1 Pino, Sergio 1 Rubensson, Emanuel H. 1 Sardeshmukh, Vivek B. 1 Schwartz, Oded 1 Shi, Guangjie 1 Toledo, Sivan 1 Williams, Samuel Cited in 3 Serials 4 SIAM Journal on Scientific Computing 1 Journal of Computational Physics 1 Linear Algebra and its Applications all top 5 Cited in 9 Fields 7 Numerical analysis (65-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 3 Quantum theory (81-XX) 1 Combinatorics (05-XX) 1 Functional analysis (46-XX) 1 Operator theory (47-XX) 1 Computer science (68-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Biology and other natural sciences (92-XX) Citations by Year