An optimized sparse approximate matrix multiply for matrices with decay

DOI10.1137/120870761MaRDI QIDQ4917165zbMATH OpenOpenAlexFDO

Authors Nicolas Bock, Matt Challacombe

Publication date 29 April 2013

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.1692

zbMATH Keywords

\(N\)-bodymatrices with decaynumerical examplesquantum chemistryreduced complexity algorithmSpAMMsparse approximate matrix multiplysparse linear algebra

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to linear algebra (15-04) Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20)

Abstract: We present an optimized single-precision implementation of the Sparse Approximate Matrix Multiply (SpAMM{}) [M. Challacombe and N. Bock, arXiv {�f 1011.3534} (2010)], a fast algorithm for matrix-matrix multiplication for matrices with decay that achieves an $mathcalO(nlogn)$ computational complexity with respect to matrix dimension $n$. We find that the max norm of the error achieved with a SpAMM{} tolerance below $2imes10^{-8}$ is lower than that of the single-precision { t SGEMM} for dense quantum chemical matrices, while outperforming { t SGEMM} with a cross-over already for small matrices ($nsim1000$). Relative to naive implementations of SpAMM{} using Intel's Math Kernel Library ({ t MKL}) or AMD's Core Math Library ({ t 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.

Recommendations

• Fast sparse matrix multiplication
• Algorithms – ESA 2004
• Memory-Efficient Sparse Matrix-Matrix Multiplication by Row Merging on Many-Core Architectures
• Decay bounds and \(O(n)\) algorithms for approximating functions of sparse matrices
• GPU-accelerated sparse matrix-matrix multiplication by iterative row merging

Cited in

(7)

• Sparse approximate matrix-matrix multiplication for density matrix purification with error control
• Decay properties for functions of matrices over \(C^\ast\)-algebras
• Exploiting multiple levels of parallelism in sparse matrix-matrix multiplication
• Localization in matrix computations: theory and applications
• Solvers for \(\mathcal{O}(N)\) electronic structure in the strong scaling limit
• Task-based parallel computation of the density matrix in quantum-based molecular dynamics using graph partitioning
• Spin summations: a high-performance perspective

Describes a project that uses

Uses Software

• SpAMM
• FreeON
• TASCEL
• PAPI
• SUMMA
• CHARM++
• HOT

This page was built for publication: An optimized sparse approximate matrix multiply for matrices with decay

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4917165)