Accelerated Cyclic Reduction: A distributed-memory fast solver for structured linear systems

Gustavo Chávez*, George Turkiyyah, Stefano Zampini, Hatem Ltaief, David Keyes

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


We present Accelerated Cyclic Reduction (ACR), a distributed-memory fast solver for rank-compressible block tridiagonal linear systems arising from the discretization of elliptic operators, developed here for three dimensions. Algorithmic synergies between Cyclic Reduction and hierarchical matrix arithmetic operations result in a solver that has O(kNlogN(logN+k2)) arithmetic complexity and O(k Nlog N) memory footprint, where N is the number of degrees of freedom and k is the rank of a block in the hierarchical approximation, and which exhibits substantial concurrency. We provide a baseline for performance and applicability by comparing with the multifrontal method with and without hierarchical semi-separable matrices, with algebraic multigrid and with the classic cyclic reduction method. Over a set of large-scale elliptic systems with features of nonsymmetry and indefiniteness, the robustness of the direct solvers extends beyond that of the multigrid solver, and relative to the multifrontal approach ACR has lower or comparable execution time and size of the factors, with substantially lower numerical ranks. ACR exhibits good strong and weak scaling in a distributed context and, as with any direct solver, is advantageous for problems that require the solution of multiple right-hand sides. Numerical experiments show that the rank k patterns are of O(1) for the Poisson equation and of O(n) for the indefinite Helmholtz equation. The solver is ideal in situations where low-accuracy solutions are sufficient, or otherwise as a preconditioner within an iterative method.

Original languageEnglish (US)
Pages (from-to)65-83
Number of pages19
JournalParallel Computing
StatePublished - May 2018

Bibliographical note

Publisher Copyright:
© 2017


  • Cyclic reduction
  • Elliptic equations
  • Fast direct solvers
  • Hierarchical matrices

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence


Dive into the research topics of 'Accelerated Cyclic Reduction: A distributed-memory fast solver for structured linear systems'. Together they form a unique fingerprint.

Cite this