A High Performance Two Dimensional Scalable Parallel Algorithm for Solving Sparse Triangular Systems
| Mahesh Joshi, Anshul Gupta, George Karypis, and Vipin Kumar |
| 4th Intl. Conference on High Performance Computing, pp. 137 - 143, 1997 |
Download Paper  |
| Abstract Solving a system of equations of the form Tx = y, where T is a sparse triangular matrix, is required after the factorization phase in the direct methods of solving systems of linear equations. A few parallel formula- tions have been proposed recently. The common belief in parallelizing this problem is that the parallel formu- lation utilizing a two dimensional distribution of T is unscalable. In this paper, we propose the rst known ecient scalable parallel algorithm which uses a two dimensional block cyclic distribution of T. The algo- rithm is shown to be applicable to dense as well as sparse triangular solvers. Since most of the known highly scalable algorithms employed in the factoriza- tion phase yield a two dimensional distribution of T, our algorithm avoids the redistribution cost incurred by the one dimensional algorithms. We present the paral- lel runtime and scalability analyses of the proposed two dimensional algorithm. The dense triangular solver is shown to be scalable. The sparse triangular solver is shown to be at least as scalable as the dense solver. We also show that it is optimal for one class of sparse systems. The experimental results of the sparse tri- angular solver show that it has good speedup charac- teristics and yields high performance for a variety of sparse systems. |
| Research topics: Parallel processing | PSPASES | Scientific computing |