A Parallel Algorithm for Solving Sparse Triangular Systems

Chin Wen Ho, R. C.T. Lee

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

In this paper, we propose a fast parallel algorithm, which is generalized from the parallel algorithms for solving banded linear systems, to solve sparse triangular systems. We transform the original problem into a directed graph. The solving procedure then consists of eliminating edges in this graph. The worst case time-complexity of this parallel algorithm is O(log2n) where n is the size of the coefficient matrix. When the coefficient matrix is a triangular banded matrix with bandwidth m, then the time-complexity of our algorithm is O(log(m) log(n)).

Original languageEnglish
Pages (from-to)848-852
Number of pages5
JournalIEEE Transactions on Computers
Volume39
Issue number6
DOIs
StatePublished - Jun 1990

Keywords

  • CREW PRAM
  • cyclic reduction
  • directed graph model
  • parallel computation
  • presubstitution
  • recursive doubling
  • sparse triangular linear systems

Fingerprint

Dive into the research topics of 'A Parallel Algorithm for Solving Sparse Triangular Systems'. Together they form a unique fingerprint.

Cite this