EFFICIENT CONSTRUCTION OF AN HSS PRECONDITIONER FOR SYMMETRIC POSITIVE DEFINITE H2 MATRICES

In an iterative approach for solving linear systems with dense, ill-conditioned, symmetric positive definite (SPD) kernel matrices, both fast matrix-vector products and fast preconditioning operations are required. Fast (linear-scaling) matrix-vector products are available by expressing the kernel matrix in an H-2 representation or an equivalent fast multipole method representation. This paper is concerned with preconditioning such matrices using the hierarchically semiseparable (HSS) matrix representation. Previously, an algorithm was presented to construct an HSS approximation to an SPD kernel matrix that is guaranteed to be SPD. However, this algorithm has quadratic cost and was only designed for recursive binary partitionings of the points defining the kernel matrix. This paper presents a general algorithm for constructing an SPD HSS approximation. Importantly, the algorithm uses the H-2 representation of the SPD matrix to reduce its computational complexity from quadratic to quasilinear. Numerical experiments illustrate how this SPD HSS approximation performs as a preconditioner for solving linear systems arising from a range of kernel functions.

Automated summary

This paper presents a general algorithm for constructing an SPD HSS approximation as a preconditioner for solving linear systems with dense, ill-conditioned, symmetric positive definite (SPD) kernel matrices. The algorithm uses the H-2 representation of the SPD matrix to reduce computational complexity from quadratic to quasilinear, and numerical experiments demonstrate its performance.