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
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