The proxy point method for rank-structured matrices

Abstract

Rank-structured matrix representations, e.g., $\mathcal{H}^2$ and HSS, are commonly used to reduce computation and storage cost for dense matrices defined by interactions between many bodies. The main bottleneck for their application is the expensive computation required to represent a matrix in a rank-structured matrix format which involves compressing specific matrix blocks into low-rank form. This dissertation is mainly about the study and application of a hybrid analytic-algebraic compression method, called \textit{the proxy point method}. This work uncovers the full strength of this presently underutilized method that could potentially resolve the above bottleneck for all rank-structured matrix techniques. As a result, this work could extend the applicability and improve the performance of rank-structured matrix techniques and thus facilitate dense matrix computations in a wider range of scientific computing problems, such as particle simulations, numerical solution of integral equations, and Gaussian processes. Application of the proxy point method in practice is presently very limited. Only two special instances of the method have been used heuristically to compress interaction blocks defined by specific kernel functions over points. We address several critical problems of the proxy point method which limit its applicability. A general form of the method is then proposed, paving the way for its wider application in the construction of different rank-structured matrix representations with kernel functions that are more general than those usually used. In addition to kernel-defined interactions between points, we further extend the applicability of the proxy point method to compress the interactions between charge distributions in quantum chemistry calculations. Specifically, we propose a variant of the proxy point method to efficiently construct an $\mathcal{H}^2$ matrix representation of the four-dimensional electron repulsion integral tensor. The linear-scaling matrix-vector multiplication algorithm for the constructed $\mathcal{H}^2$ matrix is then used for fast Coulomb matrix construction which is an important step in many quantum chemical methods. Two additional contributions related to $\mathcal{H}^2$ and HSS matrices are also presented. First, we explain the exact equivalence between $\mathcal{H}^2$ matrices and the fast multipole method (FMM). This equivalence has not been rigorously studied in the literature. Numerical comparisons between FMM and $\mathcal{H}^2$ matrices based on the proxy point method are also provided, showing the relative advantages and disadvantages of the two methods. Second, we consider the application of HSS approximations as preconditioners for symmetric positive definite (SPD) matrices. Preserving positive definiteness is essential for rank-structured matrix approximations to be used efficiently in various algorithms and applications, e.g., the preconditioned conjugate gradient method. We propose two methods for constructing HSS approximations to an SPD matrix that preserve positive definiteness.