An Improved Algorithm for Parallel Sparse LU Decomposition on a Distributed-Memory Multiprocessor
Jacko Koster, Rob H. Bisseling · 1994
In this paper we present a new parallel algorithm for the LU decomposition of a general sparse matrix. Among its features are matrix redistribution at regular intervals and a dynamic pivot search strategy that adapts itself to the number of pivots produced. Experimental results obtained on a network of 400 transputers show that these features considerably improve the performance. 1 Introduction This paper presents an improved version of the parallel algorithm for the LU decomposition of a general sparse matrix developed by van der Stappen, Bisseling, and van de Vorst [9]. The LU decomposition of a matrix A = (A ij ; 0 i; j ! n) produces a unit lower triangular matrix L, an upper triangular matrix U , a row permutation vector ß and a column permutation vector ae, such that A ß i ;ae j = (LU) ij ; for 0 i; j ! n: (1) We assume that A is sparse and nonsingular and that it has an arbitrary pattern of nonzeros, with all elements having the same (small) probability of being nonzero. A re...