Optimal parallel algorithms for solving tridiagonal linear systems

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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. For each method, we begin by presenting lower bounds on execution time for solving tridiagonal linear systems. Specifically, we present lower bounds in which it is assumed that the number of data items per processor is bounded, a general lower bound, 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. Lastly, the bounds for odd-even cyclic reduction and prefix summing are compared.

Original languageEnglish (US)
Title of host publicationEuro-Par 1997 Parallel Processing - Third International Conference, Proceedings
PublisherSpringer-Verlag Berlin Heidelberg
Pages700-709
Number of pages10
ISBN (Print)9783540634409
DOIs
StatePublished - Dec 1 1997
Externally publishedYes
Event3rd International Conference on Parallel Processing, Euro-Par 1997 - Passau, Germany
Duration: Aug 26 1997Aug 29 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1300 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Conference on Parallel Processing, Euro-Par 1997
CountryGermany
CityPassau
Period8/26/978/29/97

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal parallel algorithms for solving tridiagonal linear systems'. Together they form a unique fingerprint.

  • Cite this

    Santos, E. E. (1997). Optimal parallel algorithms for solving tridiagonal linear systems. In Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings (pp. 700-709). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1300 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/bfb0002802