Fast construction of hierarchical matrix representation from matrix-vector multiplication

DOI10.1016/J.JCP.2011.02.033zbMath1218.65038arXiv1001.0149OpenAlexW2169370352MaRDI QIDQ544585

Lexing Ying, Lin Lin, Jian-feng Lu

Publication date: 15 June 2011

Published in: Journal of Computational Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1001.0149

zbMATH Keywords

Green's functionnumerical examplesfast algorithmelliptic operatormatrix-vector multiplicationrandomized singular value decompositionhierarchical matrix construction

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Integral representations of solutions to PDEs (35C15) Boundary element methods for boundary value problems involving PDEs (65N38)

Related Items (42)

Randomized numerical linear algebra: Foundations and algorithms ⋮ Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems ⋮ Approximate inversion of discrete Fourier integral operators ⋮ Effective matrix-free preconditioning for the augmented immersed interface method ⋮ Fast Structured Direct Spectral Methods for Differential Equations with Variable Coefficients, I. The One-Dimensional Case ⋮ Compressed Absorbing Boundary Conditions via Matrix Probing ⋮ Effective and Robust Preconditioning of General SPD Matrices via Structured Incomplete Factorization ⋮ Generative modeling via tree tensor network states ⋮ Principled interpolation of Green's functions learned from data ⋮ 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 ⋮ Hierarchical off-diagonal low-rank approximation of Hessians in inverse problems, with application to ice sheet model initialization ⋮ Interpolative Decomposition Butterfly Factorization ⋮ Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices ⋮ Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations ⋮ Fast macroscopic forcing method ⋮ Learning elliptic partial differential equations with randomized linear algebra ⋮ Random Sampling and Efficient Algorithms for Multiscale PDEs ⋮ Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs ⋮ A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces ⋮ Tensor Train Construction From Tensor Actions, With Application to Compression of Large High Order Derivative Tensors ⋮ A fast multiscale Galerkin method for solving a boundary integral equation in a domain with corners ⋮ Multidimensional butterfly factorization ⋮ Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations ⋮ Compressing Rank-Structured Matrices via Randomized Sampling ⋮ A heterogeneous stochastic FEM framework for elliptic PDEs ⋮ The method of polarized traces for the 2D Helmholtz equation ⋮ A Multiscale Neural Network Based on Hierarchical Matrices ⋮ Scalable Gaussian Process Computations Using Hierarchical Matrices ⋮ Adaptive finite element method for fractional differential equations using hierarchical matrices ⋮ Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations ⋮ Scalable Matrix-Free Adaptive Product-Convolution Approximation for Locally Translation-Invariant Operators ⋮ An Efficient Multicore Implementation of a Novel HSS-Structured Multifrontal Solver Using Randomized Sampling ⋮ Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems ⋮ A multiscale neural network based on hierarchical nested bases ⋮ Robust and Accurate Stopping Criteria for Adaptive Randomized Sampling in Matrix-Free Hierarchically Semiseparable Construction ⋮ Variational training of neural network approximations of solution maps for physical models ⋮ Butterfly Factorization Via Randomized Matrix-Vector Multiplications ⋮ Bridging and Improving Theoretical and Computational Electrical Impedance Tomography via Data Completion ⋮ Butterfly Factorization ⋮ Interconnected hierarchical structures for fast direct elliptic solution ⋮ A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• CUR matrix decompositions for improved data analysis
• A fast direct solver for a class of elliptic partial differential equations
• A fast adaptive solver for hierarchically semiseparable representations
• A fast randomized algorithm for the approximation of matrices
• On the fast matrix multiplication in the boundary element method by panel clustering
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• A theory of pseudoskeleton approximations
• Existence of \(\mathcal H\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^\infty\)-coefficients
• Randomized algorithms for the low-rank approximation of matrices
• Fast wavelet transforms and numerical algorithms I
• Metric-based upscaling
• Superfast Multifrontal Method for Large Structured Linear Systems of Equations
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• Multi-Level Adaptive Solutions to Boundary-Value Problems
• A Multigrid Tutorial, Second Edition
• A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient Method
• A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
• 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
• Nested Dissection of a Regular Finite Element Mesh
• A fast algorithm for particle simulations

This page was built for publication: Fast construction of hierarchical matrix representation from matrix-vector multiplication