Efficient construction of an HSS preconditioner for symmetric positive definite H2 matrices

Xin Xing, Hua Huang, Edmond Chow

Abstract

In an iterative approach for solving linear systems with 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 $\mathcal{H}^2$ representation or an equivalent fast multipole method representation. Preconditioning such matrices, however, requires a structured matrix approximation that is more regular than the $\mathcal{H}^2$ representation, such as the hierarchically semiseparable (HSS) matrix representation, which provides fast solve operations. 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 $\mathcal{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.

Introduction

Many scientific applications—ranging from Gaussian processes in statistics to hydrodynamic interactions in biophysics—rely on "kernel matrices." These matrices are typically dense, meaning every element interacts with every other element, leading to $O(N^3)$ costs for direct solvers. While iterative solvers like Conjugate Gradient can help, these matrices are often "ill-conditioned," requiring a preconditioner to converge in a reasonable number of steps.

Hierarchical matrix formats (like HSS and $\mathcal{H}^2$) exploit the fact that off-diagonal blocks of these matrices often have low numerical rank. However, two major hurdles remained: preserving the SPD property and maintaining computational efficiency. Most fast HSS construction methods do not guarantee that the resulting approximation remains symmetric positive definite. If a preconditioner isn't SPD, the iterative solver (PCG) may fail. Furthermore, previous algorithms that could guarantee the SPD property had a quadratic ($O(N^2)$) construction cost, making them impractical for very large-scale problems.

This paper introduces a quasilinear-time algorithm ($O(N \log N)$) for constructing HSS preconditioners that are guaranteed to be SPD. By leveraging an existing $\mathcal{H}^2$ matrix representation and randomized linear algebra, the authors overcome the quadratic cost of previous SPD-preserving methods.

Methods

The authors propose an "Accelerated SPD HSS" construction algorithm. The core components include:

Scaling-and-Compression

Instead of compressing off-diagonal blocks directly, the algorithm scales them using the Cholesky factors of the diagonal blocks. This specific transformation ensures that the resulting hierarchical approximation is mathematically guaranteed to be SPD.

The scaling-and-compression process used to ensure the HSS approximation remains symmetric positive definite.

H2 Acceleration and Hierarchical Construction

The "aha" moment of the paper is using an $\mathcal{H}^2$ representation as a starting point. Because $\mathcal{H}^2$ matrices already have a nested low-rank structure, the authors can compute the necessary HSS components by performing operations on small, already-compressed blocks rather than the full dense matrix. The algorithm is generalized to handle $m$-ary trees (like quadtrees or octrees), which are more natural for 2D and 3D spatial data than simple binary trees.

Hierarchical construction of the matrix approximation across different levels of the partition tree.

To find the optimal basis for the low-rank blocks, the authors use randomized matrix-vector products. This avoids expensive Singular Value Decompositions (SVDs) on large blocks, keeping the complexity at $O(N \log N)$. By using randomized methods, the algorithm performs "blocked" matrix multiplications, allowing it to run much faster on modern hardware compared to algorithms that process entries one by one.

Experimental Evaluation

The algorithm was evaluated using synthetic kernel matrices generated from 3D point sets (up to 2.56 million points), including points distributed on the surface of a sphere and within a ball. Four specific kernel functions were tested: Matérn-3/2, Gaussian, Inverse Multiquadric (IMQ), and Rotne–Prager–Yamakawa (RPY).

Numerical experiments confirm that the construction time scales as $O(N \log N)$, allowing the method to handle millions of points where previous $O(N^2)$ methods would take days. The SPDHSS preconditioner significantly reduced the number of iterations for the Conjugate Gradient solver compared to simpler methods like Block Jacobi or FSAI (Factorized Sparse Approximate Inverse), especially for highly ill-conditioned systems.

Conclusion

This work bridges the gap between different hierarchical formats. HSS is excellent for preconditioning because it supports fast inversion (via ULV decomposition), but it is "rigid" (weak admissibility). $\mathcal{H}^2$ is more flexible and efficient for matrix-vector products but harder to invert. This paper uses the efficiency of $\mathcal{H}^2$ to build the "invertible" HSS structure.

While the SPD-preserving constraint leads to slightly higher approximation errors compared to unconstrained HSS for the same rank, the resulting stability is essential for iterative solvers. Future work could involve more robust adaptive rank strategies to maintain specific error thresholds automatically and adapting the technique for sparse SPD matrices arising from partial differential equations (PDEs).

Summary updated

Abstract

In an iterative approach for solving linear systems with 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 $\mathcal{H}^2$ representation or an equivalent fast multipole method representation. Preconditioning such matrices, however, requires a structured matrix approximation that is more regular than the $\mathcal{H}^2$ representation, such as the hierarchically semiseparable (HSS) matrix representation, which provides fast solve operations. 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 $\mathcal{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.
BibTeX
@article{xing2021efficient,
  author = {Xin Xing and Hua Huang and Edmond Chow},
  title = {{Efficient construction of an HSS preconditioner for symmetric positive definite H2 matrices}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2021},
  url = {https://openreview.net/forum?id=aSmCIxATqec},
}
Figure