Fast construction of hierarchical matrix representation from matrix-vector multiplication

Lin Lin, Jianfeng Lu, Lexing Ying

TL;DR

This paper introduces a fast "peeling" algorithm to construct hierarchical matrix ($\mathcal{H}$-matrix) representations using only a "black box" matrix-vector multiplication subroutine. By leveraging randomized singular value decomposition (SVD) and clever spatial partitioning, the method recovers complex operators like Green's functions in just $\mathcal{O}(\log n)$ multiplications, offering a powerful tool for numerical homogenization and fast solvers.

What Problem Does This Paper Address?

In many areas of computational science, we deal with large, dense matrices that represent physical interactions—such as the Green’s function of an elliptic partial differential equation (PDE). While these matrices are technically dense (every element is non-zero), they often possess a "hierarchical" structure: their off-diagonal blocks are low-rank.

The challenge is that we often don't have direct access to the individual entries of these matrices. Instead, we have a "black box" (like a multigrid solver or a sparse direct method) that can compute the product of the matrix and a vector. If the matrix is $n \times n$, a naive recovery would require $n$ multiplications. This paper asks: If we know a matrix has a hierarchical structure, can we reconstruct its full representation much faster using only these black-box multiplications?

Methods

The authors propose a top-down "peeling algorithm" that systematically extracts the low-rank components of the matrix level by level. The approach relies on three main pillars:

  1. Randomized SVD: To find a low-rank approximation of a block without seeing its entries, the algorithm multiplies the block by a small number of random Gaussian vectors. This captures the "range" of the block, allowing for a highly accurate factorization with very few samples.
  2. The Peeling Strategy: This is the core innovation. Because the matrix blocks are spatially separated, the authors can combine multiple random tests into a single matrix-vector multiplication. By exploiting the zero-pattern of the hierarchical structure, they "peel off" the off-diagonal interactions at one level before moving deeper into the hierarchy.
  3. Hierarchical Refinement ($\mathcal{H}^1$ to $\mathcal{H}^2$): The algorithm doesn't just stop at basic hierarchical forms ($\mathcal{H}^1$). it moves toward the more efficient $\mathcal{H}^2$ representation. This involves "uniformization" (ensuring different blocks share the same basis) and "projection" (linking bases across different levels of the hierarchy), which reduces the overall computational complexity and memory footprint.

Datasets

The paper evaluates the algorithm using synthetic numerical examples rather than external datasets:

  • 2D Elliptic Operators: The primary test case is the inverse of a discretized Laplacian operator ($H = -\Delta + V$) on a 2D square grid with periodic boundary conditions.
  • Random Potentials: To test robustness, the authors use high-contrast random potentials ($V$), which ensures the Green’s function has complex behavior that isn't easily smoothed away.
  • Grid Sizes: Tests were performed on grids ranging from $32 \times 32$ up to $512 \times 512$ (resulting in $n$ up to 262,144).

Key Insights and Ideas

  • Sparsity in the Interaction List: The "aha moment" is realizing that for a box in a 2D grid, its "interaction list" (the blocks it interacts with that are low-rank) is relatively small and spatially predictable. This allows the authors to group boxes into a constant number of sets (64 sets in 2D) so that their interactions don't overlap, enabling massive parallelization of the randomized SVD.
  • Black-Box Generality: Unlike previous methods that required accessing specific matrix entries, this method only needs the result of $G \cdot x$. This makes it applicable to any system where a fast solver exists but the explicit inverse is unknown.
  • Logarithmic Scaling: The number of required matrix-vector multiplications scales as $\mathcal{O}(\log n)$, which is a massive improvement over linear scaling for large-scale systems.

Key Results

  • Efficiency: For a $512 \times 512$ grid, the $\mathcal{H}^2$ version of the algorithm was significantly faster and more memory-efficient than the simpler $\mathcal{H}^1$ version.
  • Accuracy: The algorithm achieved high precision, with relative errors in the operator norm (2-norm) consistently around $10^{-7}$, matching the prescribed error tolerance.
  • Optimal Partitioning: The authors identified that the algorithm performs best when the "leaf" boxes of the hierarchy are roughly $8 \times 8$ in size.
  • Complexity: The total computational cost is $\mathcal{O}(n \log n)$ extra steps beyond the $\mathcal{O}(\log n)$ matrix-vector multiplications, making it highly competitive for large $n$.

Limitations and Future Work

  • High Constant Factors: While the scaling is $\mathcal{O}(\log n)$, the actual number of matrix-vector multiplications can be in the thousands. This might be too expensive for simple problems but is a bargain for complex homogenization tasks.
  • Geometric Constraints: The current implementation is tailored to rectangular domains and uniform grids. The authors note that extending this to unstructured grids (using quadtrees) and 3D geometries is the next logical step.
  • 3D Scaling: While the algorithm extends to 3D, the authors expect the constant factors (the number of sets needed to avoid overlap) to grow significantly, which may require even more clever grouping strategies.

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