A Parallel Algorithm for Solving Sparse Triangular Systems

Chin Wen Ho; R. C.T. Lee

doi:10.1109/12.53610

A Parallel Algorithm for Solving Sparse Triangular Systems

Chin Wen Ho, R. C.T. Lee

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	848-852
Number of pages	5
Journal	IEEE Transactions on Computers
Volume	39
Issue number	6
DOIs	https://doi.org/10.1109/12.53610
State	Published - Jun 1990

Keywords

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

Access to Document

10.1109/12.53610

Cite this

@article{2d61efa9c702406b92fc976275a78dbf,

title = "A Parallel Algorithm for Solving Sparse Triangular Systems",

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)).",

keywords = "CREW PRAM, cyclic reduction, directed graph model, parallel computation, presubstitution, recursive doubling, sparse triangular linear systems",

author = "Ho, {Chin Wen} and Lee, {R. C.T.}",

note = "Funding Information: To solve this system, Wing and Huang [21] proposed that we may construct a directed graph as Fig. 1. In the diagram, each block Manuscript received September 9, 1987; revised April 19, 1988. This work was suported in part by the National Science Council under Grant NSC77-O408-EOO7-O4. C.-W. Ho is with the Institute of Computer and Decision Sciences, National Tsing Hua University, Hsinchu, Taiwan, Republic of China. R. C. T. Lee is with the National Tsing Hua University, Hsinchu, Taiwan and Academia Sinica, Taipei, Taiwan, Republic of China. IEEE Log Number 9034551.",

year = "1990",

month = jun,

doi = "10.1109/12.53610",

language = "???core.languages.en_GB???",

volume = "39",

pages = "848--852",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

number = "6",

}

TY - JOUR

T1 - A Parallel Algorithm for Solving Sparse Triangular Systems

AU - Ho, Chin Wen

AU - Lee, R. C.T.

N1 - Funding Information: To solve this system, Wing and Huang [21] proposed that we may construct a directed graph as Fig. 1. In the diagram, each block Manuscript received September 9, 1987; revised April 19, 1988. This work was suported in part by the National Science Council under Grant NSC77-O408-EOO7-O4. C.-W. Ho is with the Institute of Computer and Decision Sciences, National Tsing Hua University, Hsinchu, Taiwan, Republic of China. R. C. T. Lee is with the National Tsing Hua University, Hsinchu, Taiwan and Academia Sinica, Taipei, Taiwan, Republic of China. IEEE Log Number 9034551.

PY - 1990/6

Y1 - 1990/6

N2 - 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)).

AB - 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)).

KW - CREW PRAM

KW - cyclic reduction

KW - directed graph model

KW - parallel computation

KW - presubstitution

KW - recursive doubling

KW - sparse triangular linear systems

UR - http://www.scopus.com/inward/record.url?scp=0025446876&partnerID=8YFLogxK

U2 - 10.1109/12.53610

DO - 10.1109/12.53610

M3 - 期刊論文

AN - SCOPUS:0025446876

VL - 39

SP - 848

EP - 852

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 6

ER -

A Parallel Algorithm for Solving Sparse Triangular Systems

Abstract

Keywords

Access to Document

Fingerprint

Cite this