The growth factor and efficiency of Gaussian elimination with rook pivoting

[摘要] Gaussian elimination is among the most widely used tools in scientific computing. Gaussian elimination with partial pivoting requires only O(n(2)) comparisons beyond the work required in Gaussian elimination with no pivoting but can, in principle, have error growth that is exponential in the matrix size n. Gaussian elimination with complete pivoting, on the other hand, cannot have exponential error growth but requires O(n(3)) comparisons beyond the work required by Gaussian elimination with no pivoting. Numerical experiments suggest that Gaussian elimination with rook pivoting is between partial pivoting and complete pivoting in terms of efficiency and accuracy. In this paper we prove that rook pivoting cannot have exponential error growth. We also introduce a combination of partial pivoting and rook pivoting which we call Gaussian elimination with partial rook pivoting and we prove the partial rook pivoting cannot have exponential error growth. We include numerical experiments showing that on a serial computer the run times for rook pivoting are almost always close to those of partial pivoting and the run times for partial rook pivoting appear to be the same as those of partial pivoting.

[发布日期] 1997-11-28

[关键词] Gaussian elimination;growth factor;rook pivoting