Simultaneous Matrix-Free HSS Compression and Factorization with Adaptive Ranks
Abstract
Many dense matrices in scientific computing have hierarchically low-rank off-diagonal structure but are accessible only through routines that apply the matrix and, in general, its transpose or adjoint to vectors, that is, through matrix--vector products (matvecs). We present a fully matrix-free algorithm that compresses such a matrix into Hierarchically Semi-Separable (HSS) form and factorizes it simultaneously with the off-diagonal ranks chosen adaptively from a prescribed tolerance. The method uses 𝒪(k) matvecs with each operator, where k is the largest off-diagonal rank found. Building on fixed-rank block nullification, it samples the matrix in small random batches and enlarges each local basis until a randomized error estimate falls below the tolerance. Unitary nullspace updates give 𝒪(k3) local dense work, the same asymptotic cost as when the ranks are known in advance. Because compression and elimination proceed together, no separate factorization step is required. Excluding the matvecs, the factorization uses 𝒪(N) arithmetic and storage when the off-diagonal ranks are bounded, and its inverse is applied in 𝒪(N) time. Experiments on Poisson and Helmholtz Schur complements, Matérn covariance matrices, and a complex Lippmann--Schwinger equation demonstrate the factorization as both a direct solver and a preconditioner on problems with up to millions of unknowns.
Related
- Adaptive accuracy-driven splitting in Ozaki matrix multiplication and application to block LU factorization
- Wideband Directional ℋ2-Matrix Compression for the Electric Field Integral Equation with Geometry-Adaptive Cluster Trees
- Matrix factorization of quotient singularities of type A and D
- LoCCA: Localized Chebyshev Cross Approximation for Kernel Matrix Factorization via Nodal Perturbation Stability
- Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization
BibTeX
@misc{do2026simultaneous,
title = {{Simultaneous Matrix-Free HSS Compression and Factorization with Adaptive Ranks}},
author = {Elly Do and Chao Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16913},
eprint = {2610.16913},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16913},
}
RIS
TY - UNPB
TI - Simultaneous Matrix-Free HSS Compression and Factorization with Adaptive Ranks
AU - Elly Do
AU - Chao Chen
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16913
UR - https://arxiv.org/abs/2610.16913
AB - Many dense matrices in scientific computing have hierarchically low-rank off-diagonal structure but are accessible only through routines that apply the matrix and, in general, its transpose or adjoint to vectors, that is, through matrix--vector products (matvecs). We present a fully matrix-free algorithm that compresses such a matrix into Hierarchically Semi-Separable (HSS) form and factorizes it simultaneously with the off-diagonal ranks chosen adaptively from a prescribed tolerance. The method uses 𝒪(k) matvecs with each operator, where k is the largest off-diagonal rank found. Building on fixed-rank block nullification, it samples the matrix in small random batches and enlarges each local basis until a randomized error estimate falls below the tolerance. Unitary nullspace updates give 𝒪(k^3) local dense work, the same asymptotic cost as when the ranks are known in advance. Because compression and elimination proceed together, no separate factorization step is required. Excluding the matvecs, the factorization uses 𝒪(N) arithmetic and storage when the off-diagonal ranks are bounded, and its inverse is applied in 𝒪(N) time. Experiments on Poisson and Helmholtz Schur complements, Matérn covariance matrices, and a complex Lippmann--Schwinger equation demonstrate the factorization as both a direct solver and a preconditioner on problems with up to millions of unknowns.
ER -