Scaling H2 Factorization to Billion-Unknown Three-Dimensional Problems
Abstract
Strong recursive skeletonization provides approximate direct solvers for dense matrices from integral equations and kernel methods, but distributed implementations face substantial communication costs and limited parallelism, especially in three dimensions. We present a distributed-memory ℋ2 factorization solver for symmetric matrices that combines spatial box coloring, delayed Schur complement updates, streamed sketching-based interpolative decomposition, and BLAS-3 and shared-memory kernels. Spatial coloring enables every process to participate in each boundary stage, while delayed updates and streamed sketching reduce dense storage and communication. To our knowledge, this is the first distributed-memory strong recursive skeletonization factorization demonstrated for three-dimensional volume integral equations at billion-unknown scale. Experiments on up to 512 compute nodes demonstrate factorization of a three-dimensional Laplace system with 3.62 billion unknowns, alongside three-dimensional Helmholtz tests and a two-dimensional Matérn system with 268 million unknowns. Combining streamed sketching and fully delayed updates reduces factorization time by 6.9× for Laplace and 8.5× for Helmholtz relative to the unsketched, eager configuration, while reducing maximum per-process resident memory by 57\% and 54\%, respectively.
Related
- CP-factorization for high dimensional tensor time series and double projection iterations
- Scale-free Hankel factorization and explicit one-dimensional plunge bounds for time-frequency localization operators
- The singular Gaussian scaling limit for a tagged particle in the infinite-dimensional Dyson model at β=2
- Local scaling limit of the four-dimensional uniform spanning tree
- Scaling limit of the collision measure for two-dimensional random walks
BibTeX
@misc{liang2026scaling,
title = {{Scaling H2 Factorization to Billion-Unknown Three-Dimensional Problems}},
author = {Tianyu Liang and Chao Chen and James Demmel and Yang Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30131},
eprint = {2610.30131},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30131},
}
RIS
TY - UNPB
TI - Scaling H2 Factorization to Billion-Unknown Three-Dimensional Problems
AU - Tianyu Liang
AU - Chao Chen
AU - James Demmel
AU - Yang Liu
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.30131
UR - https://arxiv.org/abs/2610.30131
AB - Strong recursive skeletonization provides approximate direct solvers for dense matrices from integral equations and kernel methods, but distributed implementations face substantial communication costs and limited parallelism, especially in three dimensions. We present a distributed-memory ℋ^2 factorization solver for symmetric matrices that combines spatial box coloring, delayed Schur complement updates, streamed sketching-based interpolative decomposition, and BLAS-3 and shared-memory kernels. Spatial coloring enables every process to participate in each boundary stage, while delayed updates and streamed sketching reduce dense storage and communication. To our knowledge, this is the first distributed-memory strong recursive skeletonization factorization demonstrated for three-dimensional volume integral equations at billion-unknown scale. Experiments on up to 512 compute nodes demonstrate factorization of a three-dimensional Laplace system with 3.62 billion unknowns, alongside three-dimensional Helmholtz tests and a two-dimensional Matérn system with 268 million unknowns. Combining streamed sketching and fully delayed updates reduces factorization time by 6.9× for Laplace and 8.5× for Helmholtz relative to the unsketched, eager configuration, while reducing maximum per-process resident memory by 57\% and 54\%, respectively.
ER -