An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation

DOI10.1007/s10915-013-9714-zzbMath1292.65030arXiv1407.1572OpenAlexW2188296733MaRDI QIDQ2441120

Eric Darve, Sivaram Ambikasaran

Publication date: 21 March 2014

Published in: Journal of Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

numerical linear algebraradial basis functionfast direct solverhierarchical matrixpartial hierarchically semi-separable representation

Mathematics Subject Classification ID

Numerical interpolation (65D05) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

SuperDC: Superfast Divide-And-Conquer Eigenvalue Decomposition With Improved Stability for Rank-Structured Matrices, A Direct Elliptic Solver Based on Hierarchically Low-Rank Schur Complements, Towards a unified approach to electromagnetic analysis of objects embedded in multilayers, A New Directional Algebraic Fast Multipole Method Based Iterative Solver for the Lippmann-Schwinger Equation Accelerated with HODLR Preconditioner, Approximate inversion of discrete Fourier integral operators, A fast block low-rank dense solver with applications to finite-element matrices, Immersed boundary smooth extension: a high-order method for solving PDE on arbitrary smooth domains using Fourier spectral methods, A Technique for Updating Hierarchical Skeletonization-Based Factorizations of Integral Operators, SemiAutomatic Task Graph Construction for $\mathcal{H}$-Matrix Arithmetic, Multi-Resolution Filters for Massive Spatio-Temporal Data, An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane, A parallelizable direct solution of integral equation methods for electromagnetic analysis, ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices, Distributed-memory hierarchical interpolative factorization, Low-rank updates and divide-and-conquer methods for quadratic matrix equations, Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners, A fast direct boundary element method for 3D acoustic problems based on hierarchical matrices, HODLR2D: A New Class of Hierarchical Matrices, A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions, A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite‐element matrices, FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions, Simple non-extensive sparsification of the hierarchical matrices, A hybrid stochastic interpolation and compression method for kernel matrices, A multigrid method for kernel functions acting on interacting structures with applications to biofluids, Schur complement-based domain decomposition preconditioners with low-rank corrections, An explicitly-sparse representation for oscillatory kernels with wave atom-like functions, Algebraic inverse fast multipole method: a fast direct solver that is better than HODLR based fast direct solver, 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, A fast solver for the narrow capture and narrow escape problems in the sphere, A new fast direct solver for the boundary element method, Hierarchical off-diagonal low-rank approximation of Hessians in inverse problems, with application to ice sheet model initialization, Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices, Random walks in frequency and the reconstruction of obstacles with cavities from multi-frequency data, A fast direct solver for boundary value problems on locally perturbed geometries, On the Best Approximation of the Hierarchical Matrix Product, Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs, An \(O(N \log N)\) hierarchical random compression method for kernel matrices by sampling partial matrix entries, Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations, Low-Rank Representation of Tensor Network Operators with Long-Range Pairwise Interactions, Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations, Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations, A fast and well-conditioned spectral method for singular integral equations, A Recursive Skeletonization Factorization Based on Strong Admissibility, A parallel shared-memory implementation of a high-order accurate solution technique for variable coefficient Helmholtz problems, Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity, The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems, Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation, Compressing Rank-Structured Matrices via Randomized Sampling, Reconstruction of a compactly supported sound profile in the presence of a random background medium, Fast direct isogeometric boundary element method for 3D potential problems based on HODLR matrix, Parallel accelerated cyclic reduction preconditioner for three-dimensional elliptic PDEs with variable coefficients, The method of polarized traces for the 2D Helmholtz equation, Preconditioners for hierarchical matrices based on their extended sparse form, Fast, Adaptive, High-Order Accurate Discretization of the Lippmann--Schwinger Equation in Two Dimensions, Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations, Interpolative Decomposition via Proxy Points for Kernel Matrices, A Fast Algorithm for Simulating Multiphase Flows Through Periodic Geometries of Arbitrary Shape, Scalable Gaussian Process Computations Using Hierarchical Matrices, Fast Alternating BiDirectional Preconditioner for the 2D High-Frequency Lippmann--Schwinger Equation, Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices, Preparing sparse solvers for exascale computing, On the BEM for acoustic wave problems, Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations, Sparse Cholesky Factorization by Kullback--Leibler Minimization, Sparsifying Preconditioner for the Lippmann--Schwinger Equation, High Resolution Inverse Scattering in Two Dimensions Using Recursive Linearization, Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems, On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary

Uses Software

• Eigen

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast directional multilevel summation for oscillatory kernels based on Chebyshev interpolation
• A fast direct solver for elliptic problems on general meshes in 2D
• A kernel-independent adaptive fast multipole algorithm in two and three dimensions
• A fast direct solver for a class of elliptic partial differential equations
• An adaptive fast direct solver for boundary integral equations in two dimensions
• A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains
• A fast randomized algorithm for the approximation of matrices
• The black-box fast multipole method
• On the fast matrix multiplication in the boundary element method by panel clustering
• QMR: A quasi-minimal residual method for non-Hermitian linear systems
• Fast evaluation of radial basis functions. I
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• A theory of pseudoskeleton approximations
• Construction and arithmetics of \(\mathcal H\)-matrices
• On the existence and computation of rank-revealing LU factorizations
• A fast direct solver for boundary integral equations in two dimensions
• A fast adaptive multipole algorithm in three dimensions
• Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
• Strong rank revealing LU factorizations
• The effect of the nugget on Gaussian process emulators of computer models
• Fast fitting of radial basis functions: Methods based on preconditioned GMRES iteration
• A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
• The fast multipole method: Numerical implementation
• An Analysis of Sparse Approximate Inverse Preconditioners for Boundary Integral Equations
• Randomized algorithms for the low-rank approximation of matrices
• Fast algorithms for hierarchically semiseparable matrices
• Fast Radial Basis Function Interpolation via Preconditioned Krylov Iteration
• Fast direct solvers for integral equations in complex three-dimensional domains
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Updating the Inverse of a Matrix
• Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
• Preconditioning for Boundary Integral Equations
• Local error estimates for radial basis function interpolation of scattered data
• Solution of Sparse Indefinite Systems of Linear Equations
• Radial Basis Functions
• The Fast Multipole Method I: Error Analysis and Asymptotic Complexity
• An introduction to hierarchical matrices
• A point interpolation meshless method based on radial basis functions
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• A Transpose-Free Quasi-Minimal Residual Algorithm for Non-Hermitian Linear Systems
• A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
• On the Compression of Low Rank Matrices
• Fast monte-carlo algorithms for finding low-rank approximations
• Some Fast Algorithms for Sequentially Semiseparable Representations
• The principle of minimized iterations in the solution of the matrix eigenvalue problem
• Methods of conjugate gradients for solving linear systems
• A fast algorithm for particle simulations
• A bibliography on semiseparable matrices
• Conditioning of coefficient matrices of ordinary kriging
• Efficient generation of conditional simulations by Chebyshev matrix polynomial approximations to the symmetric square root of the covariance matrix