PARALLEL SPARSE LU DECOMPOSITION ON A MESH NETWORK OF TRANSPUTERS

A parallel algorithm is presented for the LU decomposition of a genera l sparse matrix on a distributed-memory MIMD multiprocessor with a squ are mesh communication network. In the algorithm, matrix elements are assigned to processors according to the grid distribution. Each proces sor represents the nonzero elements of its part of the matrix by a loc al, ordered, two-dimensional linked-list data structure. The complexit y of important operations on this data structure and on several others is analysed. At each step of the algorithm, a parallel search for a s et of m compatible pivot elements is performed. The Markowitz counts o f the pivot elements are close to minimum, to preserve the sparsity of the matrix. The pivot elements also satisfy a threshold criterion, to ensure numerical stability. The compatibility of the m pivots enables the simultaneous elimination of m pivot rows and m pivot columns in a rank-m update of the reduced matrix. Experimental results on a networ k of 400 transputers are presented for a set of test matrices from the Harwell-Boeing sparse matrix collection.