Fast Multiplication of Matrices with Decay

Abstract

A fast algorithm for the approximate multiplication of matrices with decay is introduced; the Sparse Approximate Matrix Multiply (SpAMM) reduces complexity in the product space, a different approach from current methods that economize within the matrix space through truncation or rank reduction. Matrix truncation (element dropping) is compared to SpAMM for quantum chemical matrices with approximate exponential and algebraic decay. For matched errors in the electronic total energy, SpAMM is found to require fewer to far fewer floating point operations relative to dropping. The challenges and opportunities afforded by this new approach are discussed, including the potential for high performance implementations.

Cited by in corpus (5)

• An N-Body Solution to the Problem of Fock Exchange
• Accelerating Sparse Approximate Matrix Multiplication on GPUs
• Approximate multiplication of nearly sparse matrices with decay in a fully recursive distributed task-based parallel framework
• Sparse approximate matrix-matrix multiplication for density matrix purification with error control
• Solvers for $\mathcal{O}(N)$ Electronic Structure in the Strong Scaling Limit