A fast block low-rank dense solver with applications to finite-element matrices
From MaRDI portal
Publication:2374895
Abstract: This article presents a fast solver for the dense "frontal" matrices that arise from the multifrontal sparse elimination process of 3D elliptic PDEs. The solver relies on the fact that these matrices can be efficiently represented as a hierarchically off-diagonal low-rank (HODLR) matrix. To construct the low-rank approximation of the off-diagonal blocks, we propose a new pseudo-skeleton scheme, the boundary distance low-rank approximation, that picks rows and columns based on the location of their corresponding vertices in the sparse matrix graph. We compare this new low-rank approximation method to the adaptive cross approximation (ACA) algorithm and show that it achieves betters speedup specially for unstructured meshes. Using the HODLR direct solver as a preconditioner (with a low tolerance) to the GMRES iterative scheme, we can reach machine accuracy much faster than a conventional LU solver. Numerical benchmarks are provided for frontal matrices arising from 3D finite element problems corresponding to a wide range of applications.
Recommendations
- Multifrontal Hierarchically Solver for 3D Discretized Elliptic Equations
- Improving multifrontal methods by means of block low-rank representations
- A Fast Solver for HSS Representations via Sparse Matrices
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- Performance and scalability of the block low-rank multifrontal factorization on multicore architectures
Cites work
- H^2-matrix approximation of integral operators by interpolation
- A direct solver with O(N) complexity for integral equations on one-dimensional domains
- A domain decomposition method for the Helmholtz equation and related optimal control problems
- A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations
- A fast direct solver for a class of elliptic partial differential equations
- A fast direct solver for boundary integral equations in two dimensions
- A fast direct solver for elliptic problems on general meshes in 2D
- A fast direct solver for high frequency scattering from a large cavity in two dimensions
- A fast direct solver for structured linear systems by recursive skeletonization
- A fast randomized algorithm for the approximation of matrices
- A Fast Solver for HSS Representations via Sparse Matrices
- A frontal solution program for finite element analysis
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
- A sparse \({\mathcal H}\)-matrix arithmetic: General complexity estimates
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- A theory of pseudoskeleton approximations
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
- An O(N) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads
- An adaptive fast direct solver for boundary integral equations in two dimensions
- Approximation of boundary element matrices
- Construction and arithmetics of \(\mathcal H\)-matrices
- CUR matrix decompositions for improved data analysis
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Efficient structured multifrontal factorization for general large sparse matrices
- Fast Algorithms for Boundary Integral Equations
- Fast algorithms for hierarchically semiseparable matrices
- Fast monte-carlo algorithms for finding low-rank approximations
- FETI-DP, BDDC, and block Cholesky methods
- FETI-DP: A dual-prime unified FETI method. I: A faster alternative to the two-level FETI method
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- scientific article; zbMATH DE number 1531793 (Why is no real title available?)
- Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging
- Methods of conjugate gradients for solving linear systems
- Nested Dissection of a Regular Finite Element Mesh
- On the Compression of Low Rank Matrices
- Randomized sparse direct solvers
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- The University of Florida sparse matrix collection
- Updating the Inverse of a Matrix
Cited in
(42)- Fast multipole preconditioners for sparse matrices arising from elliptic equations
- Approximate inversion of discrete Fourier integral operators
- Fast algorithms for large dense matrices with applications to biofluids
- A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling
- Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite-element matrices
- Hierarchical interpolative factorization for elliptic operators: differential equations
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- Literature survey on low rank approximation of matrices
- On the Best Approximation of the Hierarchical Matrix Product
- Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations
- Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices
- A Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Block Low-Rank Matrices with Shared Bases: Potential and Limitations of the BLR^2 Format
- Overlapping domain decomposition preconditioner for integral equations
- Fast approximation of the Gauss-Newton Hessian matrix for the multilayer perceptron
- scientific article; zbMATH DE number 7417726 (Why is no real title available?)
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic
- Block basis factorization for scalable kernel evaluation
- Performance and scalability of the block low-rank multifrontal factorization on multicore architectures
- Improving multifrontal methods by means of block low-rank representations
- A parallel geometric multifrontal solver using hierarchically semiseparable structure
- A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization
- A direct elliptic solver based on hierarchically low-rank Schur complements
- Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners
- On the complexity of the block low-rank multifrontal factorization
- Bridging the gap between flat and hierarchical low-rank matrix formats: the multilevel block low-rank format
- The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- A multigrid method for kernel functions acting on interacting structures with applications to biofluids
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- Algebraic inverse fast multipole method: a fast direct solver that is better than HODLR based fast direct solver
- Random walks in frequency and the reconstruction of obstacles with cavities from multi-frequency data
- Sparse hierarchical solvers with guaranteed convergence
- Fully parallel and pipelined sparse direct solver for large symmetric indefinite finite element problems
- Recursive sparse LU decomposition based on nested dissection and low rank approximations
- Distributed-memory \(\mathcal{H}\)-matrix algebra. I: Data distribution and matrix-vector multiplication
- Multi-layer hierarchical structures
- Tree quasi-separable matrices: a simultaneous generalization of sequentially and hierarchically semiseparable representations
This page was built for publication: A fast block low-rank dense solver with applications to finite-element matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2374895)
