Fast Multiplication of Matrices with Decay
For computational scientists dealing with large matrices with decay (e.g., quantum chemistry), this method offers a more efficient alternative to existing truncation techniques.
The paper introduces SpAMM, a fast algorithm for approximate multiplication of matrices with decay that reduces complexity in the product space, and shows it requires fewer floating point operations than matrix truncation for quantum chemical matrices with exponential or algebraic decay, achieving matched errors in electronic total energy.
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.