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

DOI10.1007/978-3-319-52389-7_12zbMATH Open1367.65149arXiv1604.00617OpenAlexW2337503749MaRDI QIDQ5282901FDOQ5282901

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

Publication date: 17 July 2017

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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
• Fast algorithms for hierarchically semiseparable matrices
• A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
• Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
• Domain decomposition based \({\mathcal H}\)-LU preconditioning
• Parallel \(\mathcal H\)-matrix arithmetics on shared memory systems
• Superfast Multifrontal Method for Large Structured Linear Systems of Equations
• A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
• On Direct Methods for Solving Poisson’s Equations
• A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
• The Methods of Cyclic Reduction, Fourier Analysis and the FACR Algorithm for the Discrete Solution of Poisson’s Equation on a Rectangle
• A fast direct solver for elliptic problems on general meshes in 2D
• An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
• Robust Approximate Cholesky Factorization of Rank-Structured Symmetric Positive Definite Matrices
• Hierarchical Cholesky decomposition of sparse matrices arising from curl–curl-equation
• A fast block low-rank dense solver with applications to finite-element matrices

Cited In (2)

• Parallel accelerated cyclic reduction preconditioner for three-dimensional elliptic PDEs with variable coefficients
• Automatic stabilization of finite-element simulations using neural networks and hierarchical matrices

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)