Accuracy of preconditioned CG-type methods for least squares problems.
type: Item
instance of: scholarly article
title: Accuracy of preconditioned CG-type methods for least squares problems.
zbMATH Open document ID: 1056.65035
DOI: 10.1016/S0898-1221(03)80009-3
author: Laurence T. Yang
publication date: 2003-12-14T00:00:00Z
review text: The conjugate gradient (CG) method with IMGS, an incomplete modified version of Gram-Schmidt orthogonalization to obtain an incomplete orthogonal factorization preconditioner, applied to the normal equations (PCGLS) is often used as the basic iterative method to solve the linear least squares problems. In this paper, a detailed analysis is given for understanding the effect of rounding errors on IMGS and determining the accuracy of computed solutions of PCGLS with IMGS for linear least squares problems in finite precision. It is shown that for a consistent system, the difference between the true residuals and the updated approximate residual vectors generated depends on the machine precision \(\varepsilon\), on the maximum growth in norm of the iterates over their initial values, the norm of the true solution, and the condition number of \(R\) which is affected by the drop set in incomplete Gram-Schmidt factorization. Similar results are obtained for the difference between the true and computed solution for inconsistent systems. Numerical tests are carried out to confirm the theoretical conclusions.
Mathematics Subject Classification ID: 65F20
Mathematics Subject Classification ID: 65F35
Mathematics Subject Classification ID: 65F25
zbMATH DE Number: 2017179
zbMATH Keywords: Least square problems
zbMATH Keywords: Incomplete modified Gram-Schmidt orthogonalization
zbMATH Keywords: conjugate gradient-type method
zbMATH Keywords: Rounding error analysis
zbMATH Keywords: Finite precision arithmetic
zbMATH Keywords: preconditioning
zbMATH Keywords: numerical examples
zbMATH Keywords: incomplete orthogonal factorization
zbMATH Keywords: incomplete Gram-Schmidt factorization
reviewed by: A. Kukush
describes a project that uses: CIMGS
describes a project that uses: CRAIG
describes a project that uses: LSQR
MaRDI profile type: Publication
cites work: Methods of conjugate gradients for solving linear systems
cites work: Iterative Lösung und Fehlerabschätzung in der Ausgleichsrechnung
cites work: Bidiagonalization of Matrices and Solution of Linear Equations
cites work: Calculating the Singular Values and Pseudo-Inverse of a Matrix
cites work: LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
cites work: Estimating the Attainable Accuracy of Recursively Computed Residual Methods
cites work: Solving linear least squares problems by Gram-Schmidt orthogonalization
cites work: Q3361799
cites work: Predicting fill for sparse orthogonal factorization
cites work: Least Squares Computations by Givens Transformations Without Square Roots
cites work: Solution of sparse linear least squares problems using Givens rotations
cites work: Householder reflections versus Givens rotations in sparse orthogonal decomposition
cites work: Row-ordering schemes for sparse Givens transformations. I. Bipartite graph model
cites work: Orthogonal Reduction of Sparse Matrices to Upper Triangular Form Using Householder Transformations
cites work: Extensions and Applications of the Householder Algorithm for Solving Linear Least Squares Problems
cites work: Convergence of a direct-iterative method for large-scale least-squares problems
cites work: Comparison of two pivotal strategies in sparse plane rotations
cites work: Incomplete block matrix factorization preconditioning methods. The ultimate answer?
cites work: Analysis of preconditioners for conjugate gradients through distribution of eigenvalues
cites work: Practical Use of Polynomial Preconditionings for the Conjugate Gradient Method
cites work: Modified Cholesky Factorizations for Sparse Preconditioners
cites work: CIMGS: An Incomplete Orthogonal FactorizationPreconditioner
cites work: Q5674306
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 2017179