Quasi-Optimal Randomized Recovery of \mathcal{H}^2 Matrices

DOI10.48550/arXiv.2610.04574MaRDI QIDQ7367865arXivFDO

Authors Anna Yesypenko

Publication date 3 October 2026

Published in arXiv

Tldr We propose randomized algorithms for efficient approximate reconstruction of $\mathcal{H}^2$ matrices from products with the matrix and its adjoint, leveraging adaptive geometric hierarchies; carried recovery requires $O(k+p)$ applications, independent of tree depth.

Full work available at URL https://doi.org/10.48550/arXiv.2610.04574

arXiv classification

math.NA

Cites work

• A fast algorithm for particle simulations
• A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
• A kernel-independent adaptive fast multipole algorithm in two and three dimensions
• A recursive skeletonization factorization based on strong admissibility
• A simplified fast multipole method based on strong recursive skeletonization
• Compressing Rank-Structured Matrices via Randomized Sampling
• Computing Functions of Symmetric Hierarchically Semiseparable Matrices
• Elliptic PDE learning is provably data-efficient
• Fast and stable randomized low-rank matrix approximation
• Fast construction of hierarchical matrix representation from matrix-vector multiplication
• Fast Directional Multilevel Algorithms for Oscillatory Kernels
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Fixed-sparsity matrix approximation from matrix-vector products
• FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions
• Hierarchical matrices: algorithms and analysis
• Introduction to hierarchical matrices with applications.
• Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices
• Matrices with hierarchical low-rank structures
• Near-optimal hierarchical matrix approximation from matrix-vector products
• Parallel randomized and matrix-free direct solvers for large structured dense linear systems
• PVFMM: A parallel kernel independent FMM for particle and volume potentials
• Quasi-optimal hierarchically semi-separable matrix approximation
• Randomized compression of rank-structured matrices accelerated with graph coloring
• Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations
• Randomized sparse direct solvers
• Robust and accurate stopping criteria for adaptive randomized sampling in matrix-free hierarchically semiseparable construction
• SlabLU: a two-level sparse direct solver for elliptic PDEs
• Sparse Recovery of Elliptic Solvers from Matrix-Vector Products
• Superfast Multifrontal Method for Large Structured Linear Systems of Equations

This page was built for publication: Quasi-Optimal Randomized Recovery of $\mathcal{H}^2$ Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7367865)