The growth factor and efficiency of Gaussian elimination with rook pivoting (Q1379000)

Let LU\(= PAQ\) be the \(LU\) decomposition of the non-singular \(n\times n\) matrix \(A\), where \(L\) is unit lower triangular, \(U\) is upper triangular and \(P\), \(Q\) are permutation matrices, and \(\rho_n\) be the growth factor for the Gaussian elimination. It is well known that \(\rho_n\leq 2^{n- 1}\) for partial pivoting and \(\rho_n\leq 2\sqrt n n^{\ln(n)/4}\) for complete pivoting. The paper deals with the estimation of \(\rho_n\) for the so-called rook pivoting [see e.g. \textit{L. Neal} and \textit{G. Poole}, Linear Algebra Appl. 173, 239-264 (1992; Zbl 0765.65036)]. It is shown that \(\rho_n\leq r(n)= 1.5n^{3\ln(n)/4}\) for rook pivoting. A similar estimate for \(\rho_n\) in case of partial rook pivoting is also given. Results of large scale numerical tests are reported which give the idea how the rook pivoting (which is intermediate between complete and partial pivoting in terms of efficiency and accuracy) is related to other types of pivoting (including Gaussian elimination without pivoting when the latter exists).