Journal
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
Volume 42, Issue 2, Pages 683-707Publisher
SIAM PUBLICATIONS
DOI: 10.1137/20M1365776
Keywords
symmetric positive definite preconditioner; HSS matrix representation; H-2 matrix representation; kernel matrix
Categories
Funding
- National Science Foundation [ACI1609842, ACI-2003683]
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available