@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",

}