High performance two dimensional scalable parallel algorithm for solving sparse triangular systems

Mahesh V. Joshi, Anshul Gupta, George Karypis, Vipin Kumar

Research output: Contribution to conferencePaper

4 Scopus citations

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 formulations have been proposed recently. The common belief in parallelizing this problem is that the parallel formulation utilizing a two dimensional distribution of T is unscalable. In this paper, we propose the first known efficient scalable parallel algorithm which uses a two dimensional block cyclic distribution of T. The algorithm is shown to be applicable to dense as well as sparse triangular solvers. Since most of the known highly scalable algorithms employed in the factorization phase yield a two dimensional distribution of T, our algorithm avoids the redistribution cost incurred by the one dimensional algorithms. We present the parallel 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 triangular solver show that it has good speedup characteristics and yields high performance for a variety of sparse systems.

Original languageEnglish (US)
Pages137-143
Number of pages7
StatePublished - Dec 1 1997
EventProceedings of the 1997 4th International Conference on High Performance Computing, HiPC - Bangalore, India
Duration: Dec 18 1997Dec 21 1997

Other

OtherProceedings of the 1997 4th International Conference on High Performance Computing, HiPC
CityBangalore, India
Period12/18/9712/21/97

Fingerprint Dive into the research topics of 'High performance two dimensional scalable parallel algorithm for solving sparse triangular systems'. Together they form a unique fingerprint.

Cite this