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
fDate :
6/1/1990 12:00:00 AM
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;
Journal_Title :
Computers, IEEE Transactions on
