Loss and Recapture of Orthogonality in the Modified Gram–Schmidt Algorithm
The authors derive some important numerical properties of the \(QR\) factorization of an \(m\times n\) matrix \(A\) via the modified Gram-Schmidt algorithm (\(MGS\)) in the presence of rounding errors. It is shown that the upper triangular matrix \(R\) obtained from \(MGS\) is numerically as good as that obtained from rotations or Householder transformations. The special structure of the product of the Householder transformation is derived, and then used to explain and bound the loss of orthogonality in \(MGS\). This numerical equivalence is used to show how orthogonality in \(MGS\) can be regained in general. This is illustrated by deriving a backward stable algorithm based on \(MGS\) for a class of problems which includes the solution of nonsingular linear systems, the minimum 2-norm solution of undetermined linear systems, and linear least squares problems. In the final part of the paper there are comparisons of \(MGS\) and Householder transformations. It is explained when \(MGS\) may be used in preference to the Householder \(QR\) factorization of \(A\).
- Numerics of Gram-Schmidt orthogonalization
- A Rank-k Update Procedure for Reorthogonalizing the Orthogonal Factor from Modified Gram--Schmidt
- An approach of orthogonalization within the Gram-Schmidt algorithm
- A modified Gram-Schmidt algorithm with iterative orthogonalization and column pivoting
- Error Analysis of the Quasi-Gram--Schmidt Algorithm
- Numerics of Gram-Schmidt orthogonalization
- Rank-k modification methods for recursive least squares problems
- Perturbation analysis of the canonical correlations of matrix pairs
- Solution of augmented linear systems using orthogonal factorizations
- Numerical behaviour of the modified Gram-Schmidt GMRES implementation
- Roundoff error estimates of the modified Gram-Schmidt algorithm with column pivoting
- Symbiosis between linear algebra and optimization
- Enriched spectral methods and applications to problems with weakly singular solutions
- A new stable bidiagonal reduction algorithm
- One-sided reduction to bidiagonal form
- Numerical stability of GMRES
- On the modified Gram-Schmidt algorithm for weighted and constrained linear least squares problems
- Self-scaling fast rotations for stiff and equality-constrained linear least squares problems
- Accurate downdating of a modified Gram-Schmidt QR decomposition
- Ordered modified Gram-Schmidt orthogonalization revised
- Reorthogonalization for the Golub-Kahan-Lanczos bidiagonal reduction
- A modified Gram-Schmidt algorithm with iterative orthogonalization and column pivoting
- Structure in loss of orthogonality
- Block Gram-Schmidt algorithms and their stability properties
- A parallel and streaming dynamic mode decomposition algorithm with finite precision error analysis for large data
- A new projected variant of the deflated block conjugate gradient method
- Efficient implementations of the modified Gram-Schmidt orthogonalization with a non-standard inner product
- On the loss of orthogonality in the second-order Arnoldi process
- Equivalence between modified symplectic Gram-Schmidt and Householder SR algorithms
- An augmented analysis of the perturbed two-sided Lanczos tridiagonalization process
- Rounding error analysis of the classical Gram-Schmidt orthogonalization process
- Improved Gram-Schmidt type downdating methods
- Mixed-precision explicit stabilized Runge-Kutta methods for single- and multi-scale differential equations
- Stability analysis of the two-level orthogonal Arnoldi procedure
- Gram-Schmidt orthogonalization: 100 years and more
- Stability of the MGS-like elimination method for equality constrained least squares problems
- On growth factors of the modified Gram-Schmidt algorithm
- scientific article; zbMATH DE number 125628 (Why is no real title available?)
- scientific article; zbMATH DE number 1138082 (Why is no real title available?)
- A Robust Criterion for the Modified Gram--Schmidt Algorithm with Selective Reorthogonalization
- When modified Gram-Schmidt generates a well-conditioned set of vectors
- A Note on Inexact Inner Products in GMRES
- On iterative solution of the extended normal equations
- On direct elimination methods for solving the equality constrained least squares problem
- Accuracy of the Lanczos process for the eigenproblem and solution of equations
- Block Modified Gram--Schmidt Algorithms and Their Analysis
- Error Analysis of the Quasi-Gram--Schmidt Algorithm
- Computing projections via Householder transformations and Gram–Schmidt orthogonalizations
- Recursive interpolation algorithm: A formalism for solving systems of linear equations. I: Direct methods
- Probabilistic Rounding Error Analysis of Householder QR Factorization
- A novel parallel algorithm based on the Gram-Schmidt method for tridiagonal linear systems of equations
- Modified Gram-Schmidt-based methods for block downdating the Cholesky factorization
- Analyzing vector orthogonalization algorithms
- Probabilistic rounding error analysis of modified Gram-Schmidt
- Backward error analysis of the Lanczos bidiagonalization with reorthogonalization
- Modified Gram-Schmidt
- QR Decomposition via Modified Gram-Schmidt
- Lanczos algorithm explained in statistics
- On the backward stability of s-step GMRES
- An optimal error bound for \textsf{shiftedCholeskyQR3} in oblique inner product
- Theory of Krylov subspace methods based on the Arnoldi process with inexact inner products
- Rounding error analysis of the inverse compact WY modified Gram-Schmidt algorithms
- Co-simulation interface model reduction for large-scale coupled simulations
- An approach of orthogonalization within the Gram-Schmidt algorithm
- A modular framework for the backward error analysis of GMRES
- Component-wise perturbation analysis and error bounds for linear least squares solutions
- The loss of orthogonality in the Gram-Schmidt orthogonalization process
- A note on the error analysis of classical Gram-Schmidt
This page was built for publication: Loss and Recapture of Orthogonality in the Modified Gram–Schmidt Algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3988983)
