A Direct Elliptic Solver Based on Hierarchically Low-rank Schur Complements

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(N{\log }^{2}N)$ arithmetic complexity and $O(N\log N)$ memory footprint. We provide a baseline for performance and applicability by comparing with well known implementations of the $\mathcal{H}$-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 $\mathcal{H}$-LU and that it can tackle problems where algebraic multigrid fails to converge.

References in corpus (2)

• A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
• An efficient multi-core implementation of a novel HSS-structured multifrontal solver using randomized sampling

Cited by in corpus (1)

• Parallel accelerated cyclic reduction preconditioner for three-dimensional elliptic PDEs with variable coefficients