A direct elliptic solver based on hierarchically low-rank Schur complements

DOI10.1007/978-3-319-52389-7_12MaRDI QIDQ5282901zbMATH OpenOpenAlexFDO

Authors Gustavo Chávez, George M. Turkiyyah, D. E. Keyes

Publication date 17 July 2017

Published in Lecture Notes in Computational Science and Engineering (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22)

Abstract: A parallel fast direct solver for rank-compressible block tridiagonal linear systems is presented. Algorithmic synergies between Cyclic Reduction and Hierarchical matrix arithmetic operations result in a solver with $O(Nlo{g}^{2}N)$ arithmetic complexity and $O(NlogN)$ memory footprint. We provide a baseline for performance and applicability by comparing with well known implementations of the $mathcalH$-LU factorization and algebraic multigrid with a parallel implementation that leverages the concurrency features of the method. Numerical experiments reveal that this method is comparable with other fast direct solvers based on Hierarchical Matrices such as $mathcalH$-LU and that it can tackle problems where algebraic multigrid fails to converge.

Recommendations

• A Parallel Fast Direct Solver for Block Tridiagonal Systems with Separable Matrices of Arbitrary Dimension
• A fast direct solver for a class of elliptic partial differential equations
• Multifrontal Hierarchically Solver for 3D Discretized Elliptic Equations
• A fast direct solver for elliptic problems on general meshes in 2D
• scientific article; zbMATH DE number 1760073

Cites work

• scientific article; zbMATH DE number 2088244 (Why is no real title available?)
• A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
• A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
• A fast block low-rank dense solver with applications to finite-element matrices
• A fast direct solver for elliptic problems on general meshes in 2D
• A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
• An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
• Domain decomposition based \({\mathcal H}\)-LU preconditioning
• Fast algorithms for hierarchically semiseparable matrices
• Hierarchical Cholesky decomposition of sparse matrices arising from curl–curl-equation
• Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
• On Direct Methods for Solving Poisson’s Equations
• Parallel \(\mathcal H\)-matrix arithmetics on shared memory systems
• Robust Approximate Cholesky Factorization of Rank-Structured Symmetric Positive Definite Matrices
• Superfast Multifrontal Method for Large Structured Linear Systems of Equations
• The Methods of Cyclic Reduction, Fourier Analysis and the FACR Algorithm for the Discrete Solution of Poisson’s Equation on a Rectangle

Cited in

(9)

• A fast direct solver for structured linear systems by recursive skeletonization
• SlabLU: a two-level sparse direct solver for elliptic PDEs
• A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
• Interconnected hierarchical structures for fast direct elliptic solution
• A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling
• Parallel accelerated cyclic reduction preconditioner for three-dimensional elliptic PDEs with variable coefficients
• A note on the fast direct method for discrete elliptic problems
• Automatic stabilization of finite-element simulations using neural networks and hierarchical matrices
• Algebraic inverse fast multipole method: a fast direct solver that is better than HODLR based fast direct solver

Describes a project that uses

Uses Software

• hypre
• hlib

This page was built for publication: A direct elliptic solver based on hierarchically low-rank Schur complements

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