HODLR2D: A New Class of Hierarchical Matrices

DOI10.1137/22M1491253MaRDI QIDQ6054287zbMATH OpenOpenAlexFDO

Authors Vaishnavi Gujjula, Sivaram Ambikasaran

Publication date 27 September 2023

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

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

zbMATH Keywords

\(N\)-body problemshierarchical matricesiterative methodslow-rank matrix approximationsradial basis functions

Mathematics Subject Classification ID

Integral representations, integral operators, integral equations methods in two dimensions (31A10) Numerical radial basis function approximation (65D12) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Numerical methods for integral equations (65R20) Complexity and performance of numerical algorithms (65Y20)

Abstract: This article introduces HODLR2D, a new hierarchical low-rank representation for a class of dense matrices arising out of $N$ body problems in two dimensions. Using this new hierarchical framework, we propose a new fast matrix-vector product that scales almost linearly. We apply this fast matrix-vector product to accelerate the iterative solution of large dense linear systems arising out of radial basis function interpolation and discretized integral equation. The space and computational complexity of HODLR2D matrix-vector products scales as $mathcalO(pNlog(N))$, where $p$ is the maximum rank of the compressed matrix subblocks. We also prove that $pinmathcalO(log(N)log(log(N)))$, which ensures that the storage and computational complexity of HODLR2D matrix-vector products remain tractable for large $N$. Additionally, we also present the parallel scalability of HODLR2D as part of this article.

Recommendations

• HODLRdD: 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
• Adaptive fast multiplication of \(\mathcal{H}^2\)-matrices
• \(\mathcal H^2\)-matrix arithmetics in linear complexity
• Compressing Rank-Structured Matrices via Randomized Sampling

Cites work

• A direct solver with O(N) complexity for integral equations on one-dimensional domains
• A fast algorithm for particle simulations
• A fast direct solver for high frequency scattering from a large cavity in two dimensions
• A higher order parallelized multilevel fast multipole algorithm for 3-D scattering
• A new directional algebraic fast multipole method based iterative solver for the Lippmann-Schwinger equation accelerated with HODLR preconditioner
• A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• Adaptive low-rank approximation of collocation matrices
• An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
• An Accelerated Kernel-Independent Fast Multipole Method in One Dimension
• Approximation of boundary element matrices
• Bridging the gap between flat and hierarchical low-rank matrix formats: the multilevel block low-rank format
• Constructing nested bases approximations from the entries of non-local operators
• Construction and arithmetics of \(\mathcal H\)-matrices
• Construction of data-sparse \(\mathcal{H}^2\)-matrices by hierarchical compression
• Efficient mesh deformation based on radial basis function interpolation by means of the inverse fast multipole method
• Fast Radial Basis Function Interpolation via Preconditioned Krylov Iteration
• Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Hierarchical matrices based on a weak admissibility criterion
• scientific article; zbMATH DE number 733664 (Why is no real title available?)
• scientific article; zbMATH DE number 1064576 (Why is no real title available?)
• scientific article; zbMATH DE number 1955860 (Why is no real title available?)
• Improving multifrontal methods by means of block low-rank representations
• Incomplete cross approximation in the mosaic-skeleton method
• Introduction to hierarchical matrices with applications.
• Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging
• Likelihood approximation with hierarchical matrices for large spatial datasets
• On the complexity of the block low-rank multifrontal factorization
• On the fast matrix multiplication in the boundary element method by panel clustering
• Rapid solution of integral equations of scattering theory in two dimensions
• The black-box fast multipole method
• The fast multipole method: Numerical implementation
• Training very large scale nonlinear SVMs using alternating direction method of multipliers coupled with the hierarchically semi-separable kernel approximations

Cited in

(5)

• Algebraic inverse fast multipole method: a fast direct solver that is better than HODLR based fast direct solver
• HODLRdD: 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
• HODLR3D: hierarchical matrices for N-body problems in three dimensions
• New algebraic fast algorithms for N-body problems in two and three dimensions
• Mixed precision HODLR matrices

This page was built for publication: HODLR2D: A New Class of Hierarchical Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6054287)