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
- scientific article; zbMATH DE number 1531793 (Why is no real title available?)
- A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
- A Fast Solver for HSS Representations via Sparse Matrices
- 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 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 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 O(N) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads
- An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
- An adaptive fast direct solver for boundary integral equations in two dimensions
- Approximation of boundary element matrices
- CUR matrix decompositions for improved data analysis
- Construction and arithmetics of \(\mathcal H\)-matrices
- 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
- 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
- Fast Algorithms for Boundary Integral Equations
- Fast algorithms for hierarchically semiseparable matrices
- Fast monte-carlo algorithms for finding low-rank approximations
- 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
- 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
- H^2-matrix approximation of integral operators by interpolation
Cited in
(38)- Sparse hierarchical solvers with guaranteed convergence
- Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners
- Fast algorithms for large dense matrices with applications to biofluids
- Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
- A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization
- On the complexity of the block low-rank multifrontal factorization
- Performance and scalability of the block low-rank multifrontal factorization on multicore architectures
- A Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems
- The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- Hierarchical interpolative factorization for elliptic operators: differential equations
- A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling
- Bridging the gap between flat and hierarchical low-rank matrix formats: the multilevel block low-rank format
- Approximate inversion of discrete Fourier integral operators
- Block Low-Rank Matrices with Shared Bases: Potential and Limitations of the BLR$^2$ Format
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- Block basis factorization for scalable kernel evaluation
- Random walks in frequency and the reconstruction of obstacles with cavities from multi-frequency data
- Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic
- A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite-element matrices
- Improving multifrontal methods by means of block low-rank representations
- scientific article; zbMATH DE number 7417726 (Why is no real title available?)
- Fast multipole preconditioners for sparse matrices arising from elliptic equations
- A parallel geometric multifrontal solver using hierarchically semiseparable structure
- A direct elliptic solver based on hierarchically low-rank Schur complements
- 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
- Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices
- Literature survey on low rank approximation of matrices
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- Fast approximation of the Gauss-Newton Hessian matrix for the multilayer perceptron
- Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations
- Fully parallel and pipelined sparse direct solver for large symmetric indefinite finite element problems
- Overlapping domain decomposition preconditioner for integral equations
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Algebraic inverse fast multipole method: a fast direct solver that is better than HODLR based fast direct solver
- On the Best Approximation of the Hierarchical Matrix Product
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)
