Abstract
Parallel Sparse LU Factorization with Partial Pivoting onDistributed Memory Architectures
by: Cong Fu, Xiangmin Jiao, and Tao Yang
Abstract:
Gaussian elimination based sparse LU factorization with partial pivoting isimportant to many scientific applications, but it is still an open problem todevelop a high performance sparse LU code on distributed memory machines. Themain difficulty is that partial pivoting operations make structures of $L$ and$U$ factors unpredictable beforehand. This paper presents an approach called$S^*$ for parallelizing this problem on distributed memory machines. The $S^*$approach adopts static symbolic factorization to avoid run-time controloverhead, incorporates 2-D L/U supernode partitioning and amalgamationstrategies to improve caching performance, and exploits irregular taskparallelism embedded in sparse LU using asynchronous computation scheduling.The paper discusses and compares the algorithms using 1-D and 2-D data mappingschemes, and presents experimental studies on Cray-T3D and T3E. The megaflopperformance results for a set of nonsymmetric benchmark matrices are veryencouraging.
Keywords:
Sparse LU factorization, Sparse Gaussian Elimination, Partialpivoting, Dense structures, Asynchronous computation scheduling,Irregular parallelism.
Date:
May 1997
Document: 1997-11
