Tridiagonal solvers with multiple right hand sides on k-dimensional mesh and torus interconnection networks

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of designing optimal and efficient algorithms for solving tridiagonal linear systems with multiple right-hand side vectors on k-dimensional mesh and torus interconnection networks. We derive asymptotic upper and lower bounds for these solvers using odd-even cyclic reduction. We present various important bounds on execution time including general lower bounds which are independent of initial data assignment, and lower bounds based on classifying assignments via the proportion of initial data assigned amongst processors. Finally, different algorithms are designed in order to achieve running times that are within a small constant factor of the lower bounds provided.

Original languageEnglish (US)
Pages (from-to)659-672
Number of pages14
JournalParallel Processing Letters
Volume13
Issue number4
DOIs
StatePublished - Dec 1 2003
Externally publishedYes

Keywords

  • Algorithm design and analysis
  • Complexity analysis
  • Mesh
  • Parallel computing
  • Torus
  • Tridiagonal linear systems

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Tridiagonal solvers with multiple right hand sides on k-dimensional mesh and torus interconnection networks'. Together they form a unique fingerprint.

Cite this