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 | |
State | Published - Jun 1990 |
Keywords
- CREW PRAM
- cyclic reduction
- directed graph model
- parallel computation
- presubstitution
- recursive doubling
- sparse triangular linear systems