Experiments with multicomputer LU-decomposition

Abstract

We present a new concurrent LU‐decomposition algorithm based on implicit pivoting of both rows and columns. This algorithm is, to a large extent, independent of the distribution of the matrix over the concurrent processes. As a result, it can be used in programs with dynamically varying data distributions. Another advantage is that most pivoting strategies are easily incorporated. We also introduce two new, intrinsically concurrent, pivoting strategies: multirow and multicolumn pivoting. With this program, we study the performance of concurrent LU‐decomposition as a function of data distribution and pivoting strategy. We show that LU‐decomposition with some pivoting strategies is both faster and numerically more stable than LU‐decomposition without pivoting. Experimental evidence on the Symult 2010 and the iPSC/2 shows that, for performance considerations, pivoting is equivalent to randomizing the data distribution.