Optimal and efficient parallel tridiagonal solvers using direct methods

Research output: Contribution to journalArticlepeer-review


The problem of solving tridiagonal linear systems on parallel distributed-memory environments is considered in this paper. In particular, two common direct methods for solving such systems are considered: odd-even cyclic reduction and prefix summing. For each method, a variety of lower bounds on execution time for solving tridiagonal linear systems are presented. Specifically, lower bounds are presented that (a) hold when the number of data items per processor is bounded, (b) are general lower bounds, and (c) for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Furthermore, algorithms are presented that have running times within a constant factor of the lower bounds provided. Lastly, a comparison of bounds for odd-even cyclic reduction and prefix summing is given.

Original languageEnglish (US)
Pages (from-to)97-115
Number of pages19
JournalJournal of Supercomputing
Issue number2
StatePublished - Nov 2004
Externally publishedYes


  • Direct methods
  • Linear algebra
  • LogP model
  • Parallel algorithms
  • Parallel complexity
  • Tridiagonal solvers

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Optimal and efficient parallel tridiagonal solvers using direct methods'. Together they form a unique fingerprint.

Cite this