Fast construction of hierarchical matrix representation from matrix-vector multiplication
From MaRDI portal
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 applications of the matrix on structured random test vectors and extra computational cost, where 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.
Recommendations
- A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
- Construction of data-sparse \(\mathcal{H}^2\)-matrices by hierarchical compression
- Compressing Rank-Structured Matrices via Randomized Sampling
- Survey on the technique of hierarchical matrices
- Hierarchical matrices: algorithms and analysis
Cites work
- scientific article; zbMATH DE number 1714594 (Why is no real title available?)
- scientific article; zbMATH DE number 3874483 (Why is no real title available?)
- scientific article; zbMATH DE number 1531793 (Why is no real title available?)
- scientific article; zbMATH DE number 949303 (Why is no real title available?)
- scientific article; zbMATH DE number 2113718 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
- A Multigrid Tutorial, Second Edition
- A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient Method
- A fast adaptive solver for hierarchically semiseparable representations
- A fast algorithm for particle simulations
- A fast direct solver for a class of elliptic partial differential equations
- A fast randomized algorithm for the approximation of matrices
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- A theory of pseudoskeleton approximations
- CUR matrix decompositions for improved data analysis
- Existence of \(\mathcal H\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^\infty\)-coefficients
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
- Fast wavelet transforms and numerical algorithms I
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Metric-based upscaling
- Multi-Level Adaptive Solutions to Boundary-Value Problems
- Nested Dissection of a Regular Finite Element Mesh
- On the fast matrix multiplication in the boundary element method by panel clustering
- Randomized algorithms for the low-rank approximation of matrices
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
Cited in
(53)- Adaptive fast multiplication of \(\mathcal{H}^2\)-matrices
- SlabLU: a two-level sparse direct solver for elliptic PDEs
- Iterative representing set selection for nested cross approximation.
- Adaptive finite element method for fractional differential equations using hierarchical matrices
- A multiscale neural network based on hierarchical nested bases
- Tensor train construction from tensor actions, with application to compression of large high order derivative tensors
- Interpolative Decomposition Butterfly Factorization
- Butterfly factorization
- Generative modeling via tree tensor network states
- Butterfly factorization via randomized matrix-vector multiplications
- A fast memory efficient construction algorithm for hierarchically semi-separable representations
- A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
- Effective matrix-free preconditioning for the augmented immersed interface method
- Variational training of neural network approximations of solution maps for physical models
- Point spread function approximation of high-rank Hessians with locally supported nonnegative integral kernels
- Fast structured direct spectral methods for differential equations with variable coefficients. I. The one-dimensional case
- Compressing Rank-Structured Matrices via Randomized Sampling
- A heterogeneous stochastic FEM framework for elliptic PDEs
- Scalable Gaussian Process Computations Using Hierarchical Matrices
- Randomized compression of rank-structured matrices accelerated with graph coloring
- Effective and robust preconditioning of general SPD matrices via structured incomplete factorization
- Approximate inversion of discrete Fourier integral operators
- A fast multiscale Galerkin method for solving a boundary integral equation in a domain with corners
- Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- Principled interpolation of Green's functions learned from data
- Interconnected hierarchical structures for fast direct elliptic solution
- Multidimensional butterfly factorization
- Random sampling and efficient algorithms for multiscale PDEs
- An \(O(N \log N)\) hierarchical random compression method for kernel matrices by sampling partial matrix entries
- A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces
- Hierarchical off-diagonal low-rank approximation of Hessians in inverse problems, with application to ice sheet model initialization
- Hierarchical orthogonal matrix generation and matrix-vector multiplications in rigid body simulations
- The method of polarized traces for the 2D Helmholtz equation
- Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems
- Fast macroscopic forcing method
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- Learning elliptic partial differential equations with randomized linear algebra
- Randomized numerical linear algebra: Foundations and algorithms
- Parallel randomized and matrix-free direct solvers for large structured dense linear systems
- Hierarchical matrix arithmetic with accumulated updates
- Scalable Matrix-Free Adaptive Product-Convolution Approximation for Locally Translation-Invariant Operators
- Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs
- HODLR\(d\)D: a new black-box fast algorithm for \(N\)-body problems in \(d\)-dimensions with guaranteed error bounds. Applications to integral equations and support vector machines
- Sparse Recovery of Elliptic Solvers from Matrix-Vector Products
- Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations
- Robust and accurate stopping criteria for adaptive randomized sampling in matrix-free hierarchically semiseparable construction
- Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations
- Compressed absorbing boundary conditions via matrix probing
- A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity
- A Multiscale Neural Network Based on Hierarchical Matrices
- Structured matrix recovery from matrix‐vector products
- Bridging and Improving Theoretical and Computational Electrical Impedance Tomography via Data Completion
This page was built for publication: Fast construction of hierarchical matrix representation from matrix-vector multiplication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q544585)
