Fast construction of hierarchical matrix representation from matrix-vector multiplication

2009/12/31 by Lin Lin, Lin, Lin, Jianfeng Lu +3 · 10 citations
Computer Science · Physics and Astronomy · #65C20 (Secondary) #65F30 (Primary) #Electromagnetic Scattering and Analysis #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1001.0149

openalex publication_date 2009/12/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We develop a hierarchical matrix construction algorithm using matrix-vector multiplications, based on the randomized singular value decomposition of low-rank matrices. The algorithm uses O(log n) applications of the matrix on structured random test vectors and O(n log n) extra computational cost, where n is the dimension of the unknown matrix. Numerical examples on constructing Green's functions for elliptic operators in two dimensions show efficiency and accuracy of the proposed algorithm.

Citations

• Rapid factorization of structured matrices via randomized sampling
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

Cited by

• A Superfast Direct Solver for Type-III Inverse Nonuniform Discrete Fourier Transform
• Rank of Matrices Arising out of Singular Kernel Functions
• Data selection: at the interface of PDE-based inverse problem and randomized linear algebra
• Error Estimates for the Arnoldi Approximation of a Matrix Square Root
• Adaptive Sketching Based Construction of H2 Matrices on GPUs
• On the randomized SVD in infinite dimensions
• Quasi-optimal hierarchically semi-separable matrix approximation
• BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions
• H-HIGNN: A Scalable Graph Neural Network Framework with Hierarchical Matrix Acceleration for Simulation of Large-Scale Particulate Suspensions
• Parallel Sparse and Data-Sparse Factorization-based Linear Solvers

Related

• Compressing rank-structured matrices via randomized sampling
• On the best approximation of the hierarchical matrix product
• Adaptive multiplication of rank-structured matrices in linear complexity
• Hierarchical Tucker Low-Rank Matrices: Construction and Matrix-Vector Multiplication
• Hierarchical matrix arithmetic with accumulated updates