Stability of a Pivoting Strategy for Parallel Gaussian Elimination

Gaussian elimination with partial pivoting achieved by adding the pivot row to the kth row at step k, was introduced by Onaga and Takechi in 1986 as means for reducing communications in parallel implementations. In this paper it is shown that the growth factor of this partial pivoting algorithm is bounded above by n <#60; 3 n–1, as compared to 2 n–1 for the standard partial pivoting. This bound n, close to 3 n–2, is attainable for class of near-singular matrices. Moreover, for the same matrices the growth factor is small under partial pivoting.