Direct Methods for Solving Tridiagonal Linear Systems in Parallel

TitleDirect Methods for Solving Tridiagonal Linear Systems in Parallel
Publication TypeTechnical Report
Year of Publication1995
AuthorsSantos, E. E.
Other Numbers969
Abstract

We consider the problem of solving tridiagonal linear systems on parallel distributed-memory machines. We present tight asymptotic bounds for solving these systems on the LogP model using two very common direct methods : odd-even cyclic reduction and prefix summing. Specifically, we present lower bounds on execution time independent of data layout, and lower bounds for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Moreover, algorithms are provided which have running times within a constant factor of the lower bounds provided.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-95-029.pdf
Bibliographic Notes

ICSI Technical Report TR-95-029

Abbreviated Authors

E. E. Santos

ICSI Publication Type

Technical Report