Adaptive nested cross approximation of non-local operators

Ivan Oseledets, Aleksandr MikhalevarXiv 2013 · arXiv

Abstract

A new fast algebraic method for obtaining an $\mathcal{H}^2$-approximation of a matrix from its entries is presented. The main idea behind the method is based on the nested representation and the maximum-volume principle to select submatrices in low-rank matrices. A special iterative approach for the computation of so-called representor sets is established. The main advantage of the method is that it uses only the hierarchical partitioning of the matrix and does not require special proxy surfaces to be selected in advance. The numerical experiments for the N-body problem and for the boundary integral operator confirm the effectiveness and robustness of the approach. The complexity is linear in the matrix size and polynomial in the ranks. The algorithm is implemented as an open-source Python package that is available online.

Introduction

In scientific and engineering disciplines such as electromagnetics, acoustics, and quantum chemistry, researchers frequently encounter "non-local" operators. Discretizing these operators leads to large, dense $N \times N$ matrices where every element interacts with every other element. Storing such matrices requires $O(N^2)$ memory, and matrix-vector multiplication takes $O(N^2)$ time—costs that become prohibitive as $N$ scales to hundreds of thousands or millions.

Hierarchical matrix formats, specifically $\mathcal{H}$ and $\mathcal{H}^2$, mitigate this by exploiting the low-rank nature of interactions between distant groups of points. However, the challenge lies in efficiently constructing these approximations without computing all $N^2$ entries. While "cross-approximation" methods can build these structures using only a subset of rows and columns (representing sets), traditional techniques for selecting these sets often require complex, problem-specific geometric constructions known as "proxy surfaces."

Methodology: Iterative Multicharge Barnes-Hut (MCBH)

The authors propose a purely algebraic, iterative method to compress dense matrices into the $\mathcal{H}^2$ format. The core of this approach is the Iterative Multicharge Barnes-Hut (MCBH) algorithm.

$\mathcal{H}^2$-Matrix Structure

The $\mathcal{H}^2$ format utilizes a nested representation. Unlike standard low-rank approximations that store independent factors for each block, $\mathcal{H}^2$ uses "transfer matrices" to relate bases across different levels of a hierarchical tree. This reduces storage requirements from $O(N \log N)$ to $O(N)$.

Hierarchical partitioning of a matrix into admissible far (white) and close (grey) blocks at different levels of refinement.

Nested Cross Approximation and Maxvol

The algorithm extends cross-approximation to this nested structure. To ensure numerical stability and high accuracy, it employs the Maximum Volume Principle (maxvol) to select submatrices with the largest determinants. This algebraic selection process identifies the most "representative" rows and columns without needing geometric priors.

Selection of row and column representing sets ($s_i, t$) and the corresponding submatrices used in the iterative MCBH algorithm.

Iterative Refinement

Drawing an analogy to tensor decompositions (like the Tensor Train format), the MCBH algorithm performs "sweeps" up and down the hierarchical tree. It alternates between selecting representing sets (top-to-bottom) and updating nested bases (bottom-to-top), allowing the approximation to converge adaptively in just one or two iterations.

Experimental Evaluation

The method was evaluated on two demanding physical problems:

  1. N-body Electrostatics: Up to 100,000 particles in a 3D cube interacting via a $1/r$ potential.
  2. Solvation Problem: A boundary integral equation on a complex molecular surface with 222,762 triangles.

Key Results

  • Linear Scaling: Experiments confirmed that both construction time and memory consumption scale linearly ($O(N)$) with the problem size.
  • High Precision: The method achieved relative errors as low as $10^{-9}$ for electrostatic problems and $10^{-4}$ for the large-scale solvation problem (completed in ~320 seconds).
  • Robustness: Unlike previous algebraic methods like ACAMERGE, which may stall at high precision, MCBH maintains smooth convergence even for very low error tolerances.

Discussion and Future Work

The primary innovation of this work is geometry-free adaptivity. By relying solely on matrix entries and the maxvol principle, the method is more general and easier to apply to diverse problems than those requiring proxy surfaces.

While the current implementation is serial, the algorithm's structure is inherently parallelizable, similar to the Barnes-Hut or Fast Multipole Method (FMM). Future work will focus on parallelization and further reducing memory footprints by computing interaction matrices on-the-fly. Although the method performs exceptionally in practice, a formal theoretical proof for the existence of quasi-optimal MCBH approximations remains an open challenge.

The algorithm is available as an open-source Python package, h2tools.

Summary updated

Abstract

A new fast algebraic method for obtaining an $\mathcal{H}^2$-approximation of a matrix from its entries is presented. The main idea behind the method is based on the nested representation and the maximum-volume principle to select submatrices in low-rank matrices. A special iterative approach for the computation of so-called representor sets is established. The main advantage of the method is that it uses only the hierarchical partitioning of the matrix and does not require special proxy surfaces to be selected in advance. The numerical experiments for the N-body problem and for the boundary integral operator confirm the effectiveness and robustness of the approach. The complexity is linear in the matrix size and polynomial in the ranks. The algorithm is implemented as an open-source Python package that is available online.
BibTeX
@misc{oseledets2013adaptive,
  author = {Ivan Oseledets and Aleksandr Mikhalev},
  title = {{Adaptive nested cross approximation of non-local operators}},
  year = {2013},
  eprint = {1309.1773},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1309.1773},
}
Figure