Matrix-free Construction of HSS Representations Using Adaptive Randomized Sampling
summary
Presents a matrix-free sampling pipeline that builds HSS hierarchies by multiplying A (or A and Aᵀ) with random blocks, adaptively increasing samples in chunks (e.g. +16 or +64) and orthogonalizing incrementally so previously compressed nodes aren’t recomputed. Stopping uses a derived adaptive stopping via chi-square estimate tying sample vector norms to the Frobenius error. Implements ULV factorization, uses H-matrix approximations to speed sampling, shows adaptive runs that hit ~17 refinements but still outperform restart-from-scratch, and scales to thousands of cores (up to ~4k–6k) while noting sampling dominates cost.
AI-written summary · about
chapters (11)
- 0:00Intro
- 1:50Hierarchical matrix approximation
- 2:58Hierarchical matrix formats
- 4:55Block cluster tree and nested bases
- 6:58HSS matrix - ULV factorization
- 7:39Low rank compression via randomized sampling (RS)
- 11:49Practical issues
- 12:54Automatic adaptive sampling is essential for robustness
- 14:40Adaptive sampling: probabilistic error estimation
- 20:34Mitigate dense sampling cost
- 23:39Dense scalability
related talks
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
29mImplementing Randomized Matrix Algorithms in Parallel and Distributed Environments
33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...
37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?
01h 31mPast, Present and Future of Randomized Numerical Linear Algebra II
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
48mRandomized Numerical Linear Algebra