An Optimized Sparse Approximate Matrix Multiply for Matrices with Decay

2012/03/08 by Bock, Nicolas, Challacombe, Matt
#15-04 #65-04 #65F15 #65Z15 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Software (cs.MS) #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.1203.1692

Abstract

We present an optimized single-precision implementation of the Sparse Approximate Matrix Multiply (\SpAMM) [M. Challacombe and N. Bock, arXiv \bf 1011.3534 (2010)], a fast algorithm for matrix-matrix multiplication for matrices with decay that achieves an 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 × 10^-8 is lower than that of the single-precision \tt SGEMM for dense quantum chemical matrices, while outperforming \tt SGEMM with a cross-over already for small matrices (n ∼ 1000). Relative to naive implementations of \SpAMM using Intel's Math Kernel Library (\tt MKL) or AMD's Core Math Library (\tt 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.

Cited by

• The Ubiquitous Sparse Matrix-Matrix Products

Related

• Fast Multiplication of Matrices with Decay
• Approximate multiplication of nearly sparse matrices with decay in a fully recursive distributed task-based parallel framework
• Efficient Matrix Multiplication: The Sparse Power-of-2 Factorization
• Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity
• Task-Based Algorithm for Matrix Multiplication: A Step Towards Block-Sparse Tensor Computing