A fast block low-rank dense solver with applications to finite-element matrices
From MaRDI portal
Publication:2374895
DOI10.1016/J.JCP.2015.10.012zbMATH Open1349.65595arXiv1403.5337OpenAlexW1712535590MaRDI QIDQ2374895FDOQ2374895
Authors: AmirHossein Aminfar, Sivaram Ambikasaran, Eric Darve 
Publication date: 5 December 2016
Published in: Journal of Computational Physics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1403.5337
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
adaptive cross approximationiterative solversnumerical linear algebrafast direct solvershierarchically off-diagonal low-rank matricesmultifrontal elimination
Computational methods for sparse matrices (65F50) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30)
Cites Work
- FETI-DP: A dual-prime unified FETI method. I: A faster alternative to the two-level FETI method
- The University of Florida sparse matrix collection
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
- An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
- Fast algorithms for hierarchically semiseparable matrices
- A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
- Nested Dissection of a Regular Finite Element Mesh
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Methods of conjugate gradients for solving linear systems
- CUR matrix decompositions for improved data analysis
- A theory of pseudoskeleton approximations
- Approximation of boundary element matrices
- Updating the Inverse of a Matrix
- Fast monte-carlo algorithms for finding low-rank approximations
- A fast direct solver for high frequency scattering from a large cavity in two dimensions
- Construction and arithmetics of \(\mathcal H\)-matrices
- Title not available (Why is that?)
- The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- FETI-DP, BDDC, and block Cholesky methods
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- A frontal solution program for finite element analysis
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- A domain decomposition method for the Helmholtz equation and related optimal control problems
- 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 structured linear systems by recursive skeletonization
- On the Compression of Low Rank Matrices
- A Fast Solver for HSS Representations via Sparse Matrices
- A fast direct solver for a class of elliptic partial differential equations
- A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains
- \(\mathcal H^2\)-matrix approximation of integral operators by interpolation
- An adaptive fast direct solver for boundary integral equations in two dimensions
- An \(O(N)\) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads
- Efficient structured multifrontal factorization for general large sparse matrices
- A fast randomized algorithm for the approximation of matrices
- Randomized sparse direct solvers
- A sparse \({\mathcal H}\)-matrix arithmetic: General complexity estimates
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- Fast Algorithms for Boundary Integral Equations
- Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging
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
- Improving multifrontal methods by means of block low-rank representations
- Title not available (Why is that?)
- A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite-element matrices
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- A parallel geometric multifrontal solver using hierarchically semiseparable structure
- A direct elliptic solver based on hierarchically low-rank Schur complements
- Fast multipole preconditioners for sparse matrices arising from elliptic equations
- 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
- Fast approximation of the Gauss-Newton Hessian matrix for the multilayer perceptron
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- 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
Uses Software
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)
