HODLR2D: A New Class of Hierarchical Matrices
V A Kandappan, Vaishnavi Gujjula, Sivaram Ambikasaran · SIAM Journal on Scientific Computing · 2023
Abstract. This article introduces HODLR2D, a new hierarchical low-rank representation for a class of dense matrices arising out of [Formula: see text]-body problems in two dimensions. Using this new hierarchical framework, we propose a new fast matrix-vector product that scales almost linearly. We apply this fast matrix-vector product to accelerate the iterative solution of large dense linear systems arising out of radial basis function interpolation and discretized integral equation. The space and computational complexity of HODLR2D matrix-vector products scale as [Formula: see text], where [Formula: see text] is the maximum rank of the compressed matrix subblocks. For the logarithmic kernel function, we prove that [Formula: see text]. We also numerically observe a similar scaling for other kernel functions in 2D. We thereby demonstrate that the storage and computational complexity of HODLR2D matrix-vector products remain tractable for large [Formula: see text]. Additionally, we also study the parallel scalability of HODLR2D as part of this article.