DocumentCode :
1364011
Title :
A parallel algorithm for solving sparse triangular systems
Author :
Ho, Chin-wen ; Lee, R.C.T.
Author_Institution :
Inst. of Comput. & Decision Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
Volume :
39
Issue :
6
fYear :
1990
fDate :
6/1/1990 12:00:00 AM
Firstpage :
848
Lastpage :
852
Abstract :
A fast parallel algorithm, which is generalized from the parallel algorithms for solving banded linear systems, is proposed to solve sparse triangular systems. The original problem is transformed 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 the algorithm is O(log(m)×log(n))
Keywords :
computational complexity; directed graphs; parallel algorithms; banded linear systems; coefficient matrix; directed graph; parallel algorithm; sparse triangular systems; triangular banded matrix; worst-case time-complexity; Bandwidth; Computational modeling; Concurrent computing; Equations; Linear systems; Multiprocessing systems; Parallel algorithms; Phase change random access memory; Processor scheduling; Sparse matrices;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.53610
Filename :
53610
Link To Document :
بازگشت