Title :
A high performance sparse Cholesky factorization algorithm for scalable parallel computers
Author :
Karypis, George ; Kumar, Vipin
Author_Institution :
Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA
Abstract :
This paper presents a new parallel algorithm for sparse matrix factorization. This algorithm uses subforest-to-subcube mapping instead of the subtree-to-subcube mapping of another recently introduced scheme by A. Gupta and V. Kumar (1994). Asymptotically, both formulations are equally scalable on a wide range of architectures and a wide variety of problems. But the subtree-to-subcube mapping of the earlier formulation causes significant load imbalance among processors, limiting overall efficiency and speedup. The new mapping largely eliminates the load imbalance among processors. Furthermore, the algorithm has a number of enhancements to improve the overall performance substantially. This new algorithm achieves up to 20GFlops on a 1024-processor Cray T3D for moderately large problems. To our knowledge, this is the highest performance ever obtained on an MPP for sparse Cholesky factorization
Keywords :
matrix algebra; parallel algorithms; parallel processing; performance evaluation; Cray T3D; high performance sparse Cholesky factorization algorithm; load imbalance; parallel algorithm; scalable parallel computers; sparse matrix factorization; subforest-to-subcube mapping; Application software; Computer science; Concurrent computing; Finite element methods; High performance computing; Linear systems; Partitioning algorithms; Robustness; Sparse matrices; Transmission line matrix methods;
Conference_Titel :
Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the
Conference_Location :
McLean, VA
Print_ISBN :
0-8186-6965-9
DOI :
10.1109/FMPC.1995.380454