Data Structure and Algorithms for Recursively Low-Rank Compressed Matrices

TitleData Structure and Algorithms for Recursively Low-Rank Compressed Matrices
Publication TypeReport
Year of Publication2014
AuthorsChen, J
Other NumbersANL/MCS-P5112-0314
AbstractWe present a data structure and several operations it supports for recursively low- rank compressed matrices; that is, the diagonal blocks of the matrix are recursively partitioned, and the off-diagonal blocks in each partition level admit a low-rank approximation. Such a compression is embraced in many linear- or near-linear-time methods for kernel matrices, including the fast multipole method, the framework of hierarchical matrices, and several other variants. For this compressed representation, we develop a principled data structure that enables the design of matrix algorithms by using tree traversals and that facilitates computer implementation, especially in the parallel setting. We present three basic operations supported by the data structure—matrix-vector multiplication, matrix inversion, and determinant calculation—all of which have a strictly linear cost. These operations consequently enable the solution of other matrix problems with practical significance, such as the solution of a linear system and the computation of the diagonal of a matrix inverse. We show comprehensive experiments with various matrices and kernels to demonstrate the favorable numerical behavior and computational scaling of the algorithms.