Optimal tridiagonal solvers on mesh interconnection networks

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


We consider the problem of designing optimal and effcient algorithms for solving tridiagonal linear systems on a mesh interconnection network. We derive precise upper and lower bounds for these solvers using odd-even cyclic reduction. We present various important lower bounds on execution time for solving these systems including general lower bounds which are independent of initial data assignment, lower bounds based on classifications of initial data assignments which classify assignments via the proportion of initial data assigned amongst processors, and lower bounds for commonly-used data layouts for tridiagonal solvers. Finally, algorithms are provided which have running times not only within a small constant factor of the lower bounds provided but which are within a small constant additive term of the lower bounds.

Original languageEnglish (US)
Title of host publicationParallel Computation - 4th International ACPC Conference Including Special Tracks on Parallel Numerics (ParNum 1999) and Parallel Computing in Image Processing, Video Processing, and Multimedia, Proceedings
EditorsPeter Zinterhof, Marian Vajteršic, Andreas Uhl
Number of pages10
ISBN (Print)3540656413, 9783540656418
StatePublished - 1999
Externally publishedYes
Event4th International ACPC Conference on Parallel Computation, ACPC 1999 - Salzburg, Austria
Duration: Feb 16 1999Feb 18 1999

Publication series

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


Conference4th International ACPC Conference on Parallel Computation, ACPC 1999

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Optimal tridiagonal solvers on mesh interconnection networks'. Together they form a unique fingerprint.

Cite this