A parallel block cyclic reduction algorithm for the fast solution of elliptic equations

E. Gallopoulos, Y. Saad

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


This paper presents an adaptation of the Block Cyclic Reduction (BCR) algorithm for a multi-vector processor. The main bottleneck of BCR lies in the solution of linear systems whose coefficient matrix is the product of tridiagonal matrices. This bottleneck is handled by expressing the rational function corresponding to the inverse of this product as a sum of elementary fractions. As a result the solution of this system leads to parallel solutions of tridiagonal systems. Numerical experiments performed on an Alliant FX/8 are reported.

Original languageEnglish (US)
Pages (from-to)143-159
Number of pages17
JournalParallel Computing
Issue number2
StatePublished - Apr 1989

Bibliographical note

Funding Information:
* A preliminary version of this work appeared in reference \[3\]a nd was presented at I.C.S. '87, June 8-12, 1987, Athens, Greece. The authors were supported by the National Science Foundation under Grants No. US NSF-MIP-8410110 and US NSF DCR85-09970, the US Department of Energy under Grant No. DOE DE-FG02-85ER25001, by the US Air Force under Contract AFSOR-85-0211, and the IBM donation.


  • Alliant FX/8
  • Block cyclic reduction algorithm
  • multi-vector processor
  • numerical experiments
  • parallelization using partial fraction expansions


Dive into the research topics of 'A parallel block cyclic reduction algorithm for the fast solution of elliptic equations'. Together they form a unique fingerprint.

Cite this