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

G. Chavez, G. Turkiyyah, D.E. Keyes
Domain Decomposition Methods in Science and Engineering XXIII, pp. 135-143, (2017)

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

Keywords

Linear systems, Algorithmic synergies, Cyclic Reduction, Hierarchical matrix

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(Nlog2 N) arithmetic complexity and O(NlogN) memory footprint. We provide a baseline for performance and applicability by comparing with well-known implementations of the -LU factorization and algebraic multigrid within a shared-memory parallel environment 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  -LU and that it can tackle problems where algebraic multigrid fails to converge.

Code

arxiv 1604.00617

Sources

Website PDF

See all publications 2017