Fast construction of hierarchical matrix representation from matrix-vector multiplication
From MaRDI portal
Publication:544585
DOI10.1016/J.JCP.2011.02.033zbMATH Open1218.65038arXiv1001.0149OpenAlexW2169370352MaRDI QIDQ544585FDOQ544585
Authors: Lexing Ying, Lin Lin, Jianfeng Lu 
Publication date: 15 June 2011
Published in: Journal of Computational Physics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1001.0149
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
fast algorithmnumerical examplesGreen's functionelliptic operatormatrix-vector multiplicationrandomized singular value decompositionhierarchical matrix construction
Numerical solutions to overdetermined systems, pseudoinverses (65F20) Integral representations of solutions to PDEs (35C15) Boundary element methods for boundary value problems involving PDEs (65N38)
Cites Work
- Title not available (Why is that?)
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Existence of \(\mathcal H\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^\infty\)-coefficients
- Fast wavelet transforms and numerical algorithms I
- A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
- Nested Dissection of a Regular Finite Element Mesh
- A fast algorithm for particle simulations
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- CUR matrix decompositions for improved data analysis
- A theory of pseudoskeleton approximations
- Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
- Title not available (Why is that?)
- Metric-based upscaling
- Multi-Level Adaptive Solutions to Boundary-Value Problems
- On the fast matrix multiplication in the boundary element method by panel clustering
- Title not available (Why is that?)
- A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient Method
- Title not available (Why is that?)
- A Multigrid Tutorial, Second Edition
- Title not available (Why is that?)
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Randomized algorithms for the low-rank approximation of matrices
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- A fast direct solver for a class of elliptic partial differential equations
- A fast randomized algorithm for the approximation of matrices
- Title not available (Why is that?)
- A fast adaptive solver for hierarchically semiseparable representations
Cited In (53)
- SlabLU: a two-level sparse direct solver for elliptic PDEs
- Adaptive fast multiplication of \(\mathcal{H}^2\)-matrices
- A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity
- A multiscale neural network based on hierarchical nested bases
- Hierarchical off-diagonal low-rank approximation of Hessians in inverse problems, with application to ice sheet model initialization
- Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems
- Robust and accurate stopping criteria for adaptive randomized sampling in matrix-free hierarchically semiseparable construction
- Interconnected hierarchical structures for fast direct elliptic solution
- A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces
- A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
- A heterogeneous stochastic FEM framework for elliptic PDEs
- Randomized numerical linear algebra: Foundations and algorithms
- Randomized compression of rank-structured matrices accelerated with graph coloring
- Sparse Recovery of Elliptic Solvers from Matrix-Vector Products
- Generative modeling via tree tensor network states
- Butterfly factorization via randomized matrix-vector multiplications
- Effective and robust preconditioning of general SPD matrices via structured incomplete factorization
- Adaptive finite element method for fractional differential equations using hierarchical matrices
- An \(O(N \log N)\) hierarchical random compression method for kernel matrices by sampling partial matrix entries
- Iterative representing set selection for nested cross approximation.
- Approximate inversion of discrete Fourier integral operators
- Compressed absorbing boundary conditions via matrix probing
- The method of polarized traces for the 2D Helmholtz equation
- Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices
- Hierarchical matrix arithmetic with accumulated updates
- A Multiscale Neural Network Based on Hierarchical Matrices
- Effective matrix-free preconditioning for the augmented immersed interface method
- Scalable Gaussian Process Computations Using Hierarchical Matrices
- Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations
- Bridging and Improving Theoretical and Computational Electrical Impedance Tomography via Data Completion
- Fast macroscopic forcing method
- Multidimensional butterfly factorization
- Tensor train construction from tensor actions, with application to compression of large high order derivative tensors
- Fast structured direct spectral methods for differential equations with variable coefficients. I. The one-dimensional case
- Variational training of neural network approximations of solution maps for physical models
- A fast memory efficient construction algorithm for hierarchically semi-separable representations
- Hierarchical orthogonal matrix generation and matrix-vector multiplications in rigid body simulations
- Principled interpolation of Green's functions learned from data
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- Random sampling and efficient algorithms for multiscale PDEs
- Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations
- Compressing Rank-Structured Matrices via Randomized Sampling
- Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs
- Interpolative Decomposition Butterfly Factorization
- Learning elliptic partial differential equations with randomized linear algebra
- Butterfly factorization
- Structured matrix recovery from matrix‐vector products
- Point spread function approximation of high-rank Hessians with locally supported nonnegative integral kernels
- A fast multiscale Galerkin method for solving a boundary integral equation in a domain with corners
- Scalable Matrix-Free Adaptive Product-Convolution Approximation for Locally Translation-Invariant Operators
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- Parallel randomized and matrix-free direct solvers for large structured dense linear systems
- 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
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)
