Fast construction of hierarchical matrix representation from matrix-vector multiplication

Lin Lin, Jianfeng Lu, Lexing Ying

Abstract

We develop a hierarchical matrix construction algorithm using matrix-vector multiplications, based on the randomized singular value decomposition of low-rank matrices. The algorithm uses $\mathcal{O}(\log n)$ applications of the matrix on structured random test vectors and $\mathcal{O}(n \log n)$ extra computational cost, where $n$ is the dimension of the unknown matrix. Numerical examples on constructing Green's functions for elliptic operators in two dimensions show efficiency and accuracy of the proposed algorithm.

Introduction

In many areas of scientific computing—particularly when solving elliptic partial differential equations (PDEs)—researchers encounter matrices that are technically dense but possess a hidden, exploitable structure. These matrices, such as those representing Green’s functions, are often hierarchically low-rank: while the global matrix is full-rank, specific off-diagonal blocks can be approximated very accurately by low-rank factorizations.

The standard approach to building these hierarchical representations usually requires direct access to individual matrix entries. However, in many practical scenarios, the operator is only available as a "black box" (such as a multigrid or sparse direct solver) that can perform matrix-vector multiplications (matvecs). This paper introduces a "peeling" algorithm designed to efficiently recover the full hierarchical structure using only a limited number of these black-box operations.

Methodology: The Peeling Algorithm

The authors propose a top-down peeling algorithm that extracts the low-rank structure level-by-level, moving from the largest off-diagonal blocks down to the smallest. The method relies on several key technical innovations:

1. Randomized SVD

To find the low-rank approximation of a specific block, the algorithm employs randomized singular value decomposition. By multiplying the block by a small set of random Gaussian vectors, the algorithm probes the range of the matrix, allowing for a rapid approximation of its singular value decomposition without needing to see every entry.

2. Simultaneous Probing and Peeling

Probing every block individually would be computationally prohibitive. The authors observe that at any given level of the hierarchical tree, many off-diagonal blocks do not overlap in their row or column indices. By carefully structuring the random test vectors, they can probe multiple non-overlapping blocks simultaneously with a single matvec call.

Once the approximations for a specific level are calculated, their contribution is "peeled off" (subtracted) from the matrix. This reveals the next level of smaller off-diagonal blocks, which were previously obscured by the larger ones. This recursive subtraction ensures that the algorithm can isolate and approximate the entire hierarchy.

3. Extension to $\mathcal{H}^2$ Matrices

The algorithm is further refined from basic $\mathcal{H}^1$ matrices to more sophisticated $\mathcal{H}^2$ representations. This involves "uniformization" (ensuring blocks share a common basis) and "projection" (linking bases between parent and child levels). These steps significantly reduce the memory footprint and computational complexity of the resulting representation.

Numerical Evaluation

The algorithm was tested using numerical simulations of 2D elliptic operators, which provide a challenging benchmark for hierarchical construction:

  • Discretized Laplacian with Random Potential: $H = -\Delta + V$, where $V$ is a high-contrast random potential, testing robustness against non-smooth coefficients.
  • General Elliptic Operators: $H = -\nabla \cdot (a(r)\nabla) + V(r)$, representing complex physical media.

Tests were performed on grids ranging from $32 \times 32$ up to $512 \times 512$, resulting in matrices with up to $n = 262,144$ unknowns.

Key Results and Insights

  • Logarithmic Scaling: The algorithm requires only $\mathcal{O}(\log n)$ matvecs to reconstruct the matrix. This is possible because the number of levels in the hierarchy grows logarithmically with $n$, and the number of probes required per level remains constant.
  • Accuracy: In tests involving Green's functions, the algorithm achieved relative errors in the range of $10^{-7}$ to $10^{-9}$ using a modest number of random vectors. Numerical results demonstrate that error remains stable despite the recursive nature of the peeling process.
  • Efficiency: For $n=512$, the $\mathcal{H}^2$ construction was nearly three times faster than the $\mathcal{H}^1$ version, demonstrating the practical benefits of the more advanced hierarchical format.

Limitations and Future Directions

While the asymptotic scaling is excellent, the "constant factor" can be large; some examples required several thousand matvecs. This might be a limitation if the underlying black-box matvec is extremely expensive. Furthermore, while the logic applies to unstructured grids, the current implementation is tailored for regular rectangular grids.

Future work includes extending the implementation to 3D—where interaction lists are larger and constant factors will likely increase—and applying the method to boundary integral operators and more complex geometric structures.

Summary updated

Abstract

We develop a hierarchical matrix construction algorithm using matrix-vector multiplications, based on the randomized singular value decomposition of low-rank matrices. The algorithm uses $\mathcal{O}(\log n)$ applications of the matrix on structured random test vectors and $\mathcal{O}(n \log n)$ extra computational cost, where $n$ is the dimension of the unknown matrix. Numerical examples on constructing Green's functions for elliptic operators in two dimensions show efficiency and accuracy of the proposed algorithm.
BibTeX
@article{lin2011fast,
  author = {Lin Lin and Jianfeng Lu and Lexing Ying},
  title = {{Fast construction of hierarchical matrix representation from matrix-vector multiplication}},
  journal = {Journal of Computational Physics},
  year = {2011},
  url = {https://openreview.net/forum?id=_XxLAY_Qfa},
}
Figure