The growth factor and efficiency of Gaussian elimination with rook pivoting
type: Item
instance of: scholarly article
title: The growth factor and efficiency of Gaussian elimination with rook pivoting
zbMATH Open document ID: 0903.65021
DOI: 10.1016/S0377-0427(97)00154-4
author: Leslie Foster
published in: Journal of Computational and Applied Mathematics
publication date: 1999-01-05T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 65F05
zbMATH DE Number: 1115931
zbMATH Keywords: LU decomposition
zbMATH Keywords: growth factor
zbMATH Keywords: Gaussian elimination
zbMATH Keywords: rook pivoting
zbMATH Keywords: numerical tests
reviewed by: Mihail M. Konstantinov
describes a project that uses: LAPACK
describes a project that uses: Algorithm 694
describes a project that uses: testmatrix
describes a project that uses: mctoolbox
MaRDI profile type: Publication
cites work: Q4841244
cites work: Accurate Symmetric Indefinite Linear Equation Solvers
cites work: Monitoring the numerical stability of Gaussian elimination
cites work: On the complete pivoting conjecture for a hadamard matrix of order 12
cites work: Factorizing symmetric indefinite matrices
cites work: Gaussian Elimination with Partial Pivoting Can Fail in Practice
cites work: Q3359644
cites work: Algorithm 694
cites work: Q4864704
cites work: Large Growth Factors in Gaussian Elimination with Pivoting
cites work: Matrix Analysis
cites work: A geometric analysis of Gaussian elimination. II
cites work: The Efficient Generation of Random Orthogonal Matrices with an Application to Condition Estimators
cites work: Average-Case Stability of Gaussian Elimination
cites work: Error Analysis of Eigenvalue Techniques Based on Orthogonal Transformations
cites work: Q5674306
cites work: A Collection of Problems for Which Gaussian Elimination with Partial Pivoting is Unstable
full work available at URL: s0377-0427(97)00154-4
OpenAlex ID: W2023689870
Recommended article: Corrigendum: The growth factor and efficiency of Gaussian elimination with rook pivoting
Recommended article: Some features of Gaussian elimination with rook pivoting
Recommended article: On Growth in Gaussian Elimination with Complete Pivoting
Recommended article: Large Growth Factors in Gaussian Elimination with Pivoting
Recommended article: A new pivoting strategy for Gaussian elimination
Recommended article: An upper bound on the growth ratio of Gaussian elimination
Recommended article: On the robustness of Gaussian elimination with partial pivoting
Recommended article: Analysis of Pairwise Pivoting in Gaussian Elimination
Recommended article: On the parallel complexity of Gaussian elimination with pivoting
Recommended article: Growth in Gaussian Elimination
description: scientific article; zbMATH DE number 1115931