On the Compression of Low Rank Matrices

DOI10.1137/030602678zbMath1083.65042OpenAlexW2038922352MaRDI QIDQ5318307

Zydrunas Gimbutas, Hongwei Cheng, Vladimir Rokhlin, Per-Gunnar Martinsson

Publication date: 22 September 2005

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e960e7d2e4cdcb20f80222f76f21c8573fd5fd24

zbMATH Keywords

algorithmsingular value decompositiondouble layer potentialmatrix inversionmatrix factorizationlow rank approximationsecond kind integral equationmatrix-vector multiplicationsexterior Dirichlet boundary value problemintegral equations of potential theoryQR factorisation

Mathematics Subject Classification ID

Factorization of matrices (15A23) Numerical methods for integral equations (65R20) Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Integral equations of the convolution type (Abel, Picard, Toeplitz and Wiener-Hopf type) (45E10) Boundary element methods for boundary value problems involving PDEs (65N38)

Related Items

Pass-efficient methods for compression of high-dimensional turbulent flow data, A fast direct singular boundary method for three-dimensional potential problems, Approximate inversion of discrete Fourier integral operators, Overlapping Domain Decomposition Preconditioner for Integral Equations, Linear-scaling selected inversion based on hierarchical interpolative factorization for self Green's function for modified Poisson-Boltzmann equation in two dimensions, A fast block low-rank dense solver with applications to finite-element matrices, Randomized Local Model Order Reduction, A Technique for Updating Hierarchical Skeletonization-Based Factorizations of Integral Operators, Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations, An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane, Periodic band structure calculation by the Sakurai-Sugiura method with a fast direct solver for the boundary element method with the fast multipole representation, A fast direct solver for quasi-periodic scattering problems, A simplified technique for the efficient and highly accurate discretization of boundary integral equations in 2D on domains with corners, A fast direct solver for scattering from periodic structures with multiple material interfaces in two dimensions, Far-field compression for fast kernel summation methods in high dimensions, Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging, Scalable \textit{in situ} compression of transient simulation data using time-dependent bases, A fast direct solver for scattering problems involving elongated structures, A fast direct solver for two dimensional quasi-periodic multilayered media scattering problems, An Accelerated Divide-and-Conquer Algorithm for the Bidiagonal SVD Problem, Error analysis of an accelerated interpolative decomposition for 3D Laplace problems, Distributed-memory hierarchical interpolative factorization, Randomized generalized singular value decomposition, Low-rank approximation of integral operators by using the Green formula and quadrature, A tensor-train accelerated solver for integral equations in complex geometries, A randomized algorithm for the decomposition of matrices, A low-rank control variate for multilevel Monte Carlo simulation of high-dimensional uncertain systems, A new class of highly accurate solvers for ordinary differential equations, On the Complexity of the Block Low-Rank Multifrontal Factorization, Increasing horizontal resolution in numerical weather prediction and climate simulations: illusion or panacea?, Randomized LU decomposition, New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem, Interpolative Decomposition Butterfly Factorization, An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations, Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations, Literature survey on low rank approximation of matrices, A computational model of the flight dynamics and aerodynamics of a jellyfish-like flying machine, System Identification via CUR-Factored Hankel Approximation, Compression of tokamak boundary plasma simulation data using a maximum volume algorithm for matrix skeleton decomposition, An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation, On computing distributions of products of non-negative independent random variables, Hierarchical interpolative factorization preconditioner for parabolic equations, Second kind integral equations for the first kind Dirichlet problem of the biharmonic equation in three dimensions, Fast structured LU factorization for nonsymmetric matrices, Bi-fidelity approximation for uncertainty quantification and sensitivity analysis of irradiated particle-laden turbulence, Analytical Low-Rank Compression via Proxy Point Selection, Regression-aware decompositions, Reduced Basis Approximations for Maxwell’s Equations in Dispersive Media, Randomized algorithms for the low-rank approximation of matrices, A boundary integral equation approach to computing eigenvalues of the Stokes operator, A New Preconditioner that Exploits Low-Rank Approximations to Factorization Error, A fast randomized algorithm for the approximation of matrices, An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers, A fast solver for Poisson problems on infinite regular lattices, A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains, Adaptively Compressed Polarizability Operator for Accelerating Large Scale Ab Initio Phonon Calculations, A Recursive Skeletonization Factorization Based on Strong Admissibility, An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths, Efficient methods for grouping vectors into low-rank clusters, An algorithm for the rapid evaluation of special function transforms, Diffusion wavelets, Sparse identification of nonlinear dynamical systems via reweighted \(\ell_1\)-regularized least squares, A fast direct solver for boundary integral equations in two dimensions, Fast randomized matrix and tensor interpolative decomposition using countsketch, An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures, Practical error bounds for a non-intrusive bi-fidelity approach to parametric/stochastic model reduction, Fast algorithms for spherical harmonic expansions. III, Randomized interpolative decomposition of separated representations, Block Basis Factorization for Scalable Kernel Evaluation, Geometric component analysis and its applications to data analysis, Fast Coulomb Matrix Construction via Compressing the Interactions Between Continuous Charge Distributions, A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators, A DEIM Induced CUR Factorization, Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations, Interpolative Decomposition via Proxy Points for Kernel Matrices, Split representation of adaptively compressed polarizability operator, Smoothed Corners and Scattered Waves, A Fast Algorithm for Simulating Multiphase Flows Through Periodic Geometries of Arbitrary Shape, Fast direct solvers for integral equations in complex three-dimensional domains, Allocation Strategies for High Fidelity Models in the Multifidelity Regime, Fast Low-Rank Kernel Matrix Factorization Using Skeletonized Interpolation, 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, A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices, ASKIT: An Efficient, Parallel Library for High-Dimensional Kernel Summations, The black-box fast multipole method, A fast integral equation method for the two-dimensional Navier-Stokes equations, Fast and backward stable transforms between spherical harmonic expansions and bivariate Fourier series, Coarse-Grained Modeling of Protein Unfolding Dynamics, Simulation of two-dimensional steady-state heat conduction problems by a fast singular boundary method, Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains, Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning, ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions, Subspace Iteration Randomization and Singular Value Problems, A high-order accurate accelerated direct solver for acoustic scattering from surfaces, Fast Updating Multipole Coulombic Potential Calculation, A Distributed-Memory Package for Dense Hierarchically Semi-Separable Matrix Computations Using Randomization, Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format, Bi-fidelity reduced polynomial chaos expansion for uncertainty quantification, A fast algorithm for the inversion of general Toeplitz matrices, Randomized numerical linear algebra: Foundations and algorithms, libdlr: efficient imaginary time calculations using the discrete Lehmann representation, FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions, Algebraic inverse fast multipole method: a fast direct solver that is better than HODLR based fast direct solver, A fast solver for the narrow capture and narrow escape problems in the sphere, A fast time domain solver for the equilibrium Dyson equation, Compressing Rank-Structured Matrices via Randomized Sampling