A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
arXiv:1403.5337 · doi:10.1016/j.jcp.2015.10.012
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.
References in corpus (2)
Cited by in corpus (30)
- An Immersed Boundary Method for Rigid Bodies
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- The Inverse Fast Multipole Method
- A Butterfly-Accelerated Volume Integral Equation Solver for Broad Permittivity and Large-Scale Electromagnetic Analysis
- Inverse Obstacle scattering in two dimensions with multiple frequency data and multiple angles of incidence
- Efficiency Assessment of Approximated Spatial Predictions for Large Datasets
- Fast symmetric factorization of hierarchical matrices with applications
- A Robust Hierarchical Solver for Ill-conditioned Systems with Applications to Ice Sheet Modeling
- Fast Multipole Method as a Matrix-Free Hierarchical Low-Rank Approximation
- Block Basis Factorization for Scalable Kernel Matrix Evaluation
- Parallel QR Factorization of Block Low-Rank Matrices
- A distributed-memory package for dense Hierarchically Semi-Separable matrix computations using randomization
- Fast Approximation of the Gauss-Newton Hessian Matrix for the Multilayer Perceptron
- Fast QR decomposition of HODLR matrices
- A power Schur complement Low-Rank correction preconditioner for general sparse linear systems
- Recursively Preconditioned Hierarchical Interpolative Factorization for Elliptic Partial Differential Equations
- Second Order Accurate Hierarchical Approximate Factorization of Sparse SPD Matrices
- A Direct Elliptic Solver Based on Hierarchically Low-rank Schur Complements
- Fast, adaptive, high order accurate discretization of the Lippmann-Schwinger equation in two dimension
- A fast direct solver for high frequency scattering from a large cavity in two dimensions
- An efficient preconditioner for the fast simulation of a 2D Stokes flow in porous media
- A Fast and Memory Efficient Sparse Solver with Applications to Finite-Element Matrices
- Graph-Induced Rank Structures and their Representations
- Approximate inversion of discrete Fourier integral operators
- Sparse Approximate Multifrontal Factorization with Butterfly Compression for High Frequency Wave Equations
- Overlapping Domain Decomposition Preconditioner for Integral Equations
- MatRox: Modular approach for improving data locality in Hierarchical (Mat)rix App(Rox)imation
- Geostatistical Modeling and Prediction Using Mixed-Precision Tile Cholesky Factorization
- On the best approximation of the hierarchical matrix product
- High Performance Multivariate Geospatial Statistics on Manycore Systems