Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences

DOI10.1016/0024-3795(89)90285-1MaRDI QIDQ1114332zbMATH OpenOpenAlexWikidataFDO

Authors Anne Greenbaum

Publication date 1989

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(89)90285-1

zbMATH Keywords

conjugate-gradient methoderror analysisLanczos methodorthogonal polynomialsrate of convergence

Mathematics Subject Classification ID

Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.) (33C45) Computation of special functions and constants, construction of tables (65D20) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Review text

For the Lanczos and conjugate-gradient algorithms it is shown that in the presence of roundoff the computed set of orthogonal polynomials are still orthogonal polynomials but with respect to a slighly different measure. This property is used to obtain information on the approximate eigenvalues computed by the Lanczos method and the rate of convergence of the perturbed conjugate-gradient algorithm.

Recommendations

• Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
• scientific article; zbMATH DE number 592547
• The Lanczos and conjugate gradient algorithms in finite precision arithmetic
• The Lanczos and conjugate gradient algorithms in finite precision arithmetic
• scientific article; zbMATH DE number 766216

Cites work

• A new look at the Lanczos algorithm for solving symmetric systems of linear equations
• Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem
• Comparison of splittings used with the conjugate gradient algorithm
• How to Make the Lanczos Algorithm Converge Slowly
• Methods of conjugate gradients for solving linear systems
• The Lanczos Algorithm with Selective Orthogonalization

Cited in

(68)

• Sensitivity of the Lanczos recurrence to Gaussian quadrature data: how malignant can small weights be?
• The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems
• Conditioning of Stieltjes matrices by S/P consistently ordered approximate factorizations
• On the convergence rate of the conjugate gradients in presence of rounding errors
• Estimates in quadratic formulas
• Algebraic description of the finite Stieltjes moment problem
• On the sensitivity of Lanczos recursions to the spectrum
• Accurate conjugate gradient methods for families of shifted systems
• Maintaining convergence properties of BiCGStab methods in finite precision arithmetic
• Reliable updated residuals in hybrid Bi-CG methods
• An overview of approaches for the stable computation of hybrid BiCG methods
• Peaks, plateaus, numerical instabilities in a Galerkin minimal residual pair of methods for solving \(Ax=b\)
• Large sparse symmetric eigenvalue problems with homogeneous linear constraints: The Lanczos process with inner-outer iterations
• When does the Lanczos algorithm compute exactly?
• Accurate error estimation in CG
• Computable upper error bounds for Krylov approximations to matrix exponentials and associated \(\varphi\)-functions
• An augmented analysis of the perturbed two-sided Lanczos tridiagonalization process
• Error estimation in preconditioned conjugate gradients
• Smoothed analysis for the conjugate gradient algorithm
• The stabilization of weights in the Lanczos and conjugate gradient method
• On the condition number of the critically-scaled Laguerre unitary ensemble
• Sharpness in rates of convergence for the symmetric Lanczos method
• A Lanczos method for approximating composite functions
• Error Analysis of the Lanczos Algorithm for the Nonsymmetric Eigenvalue Problem
• Analysis of the finite precision bi-conjugate gradient algorithm for nonsymmetric linear systems
• The numerical stability analysis of pipelined conjugate gradient methods: historical context and methodology
• Composite convergence bounds based on Chebyshev polynomials and finite precision conjugate gradient computations
• Universal halting times in optimization and machine learning
• Inexact half-quadratic optimization for linear inverse problems
• scientific article; zbMATH DE number 766216 (Why is no real title available?)
• On the cost of iterative computations
• The conjugate gradient algorithm on a general class of spiked covariance matrices
• On the Condition Number of the Shifted Real Ginibre Ensemble
• The short-term rational Lanczos method and applications
• Generalized spectrum of second order differential operators
• Predict-and-Recompute Conjugate Gradient Variants
• The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic
• On the Convergence Rate of Variants of the Conjugate Gradient Algorithm in Finite Precision Arithmetic
• Accuracy of the Lanczos process for the eigenproblem and solution of equations
• Laplacian preconditioning of elliptic PDEs: localization of the eigenvalues of the discretized operator
• Accuracy of the s-Step Lanczos Method for the Symmetric Eigenproblem in Finite Precision
• scientific article; zbMATH DE number 2206822 (Why is no real title available?)
• Analyzing the effect of local rounding error propagation on the maximal attainable accuracy of the pipelined conjugate gradient method
• The Lanczos and Conjugate Gradient Algorithms
• Optimal preconditioners of a given sparsity pattern
• Error Bounds for Lanczos-Based Matrix Function Approximation
• Analysis of the Truncated Conjugate Gradient Method for Linear Matrix Equations
• The behavior of the Gauss-Radau upper bound of the error norm in CG
• Low-Memory Krylov Subspace Methods for Optimal Rational Matrix Function Approximation
• A Simple Formula for the Generalized Spectrum of Second Order Self-Adjoint Differential Operators
• Stability of the Lanczos algorithm on matrices with regular spectral distributions
• Towards understanding CG and GMRES through examples
• A stochastic ADMM algorithm for large-scale ptychography with weighted difference of anisotropic and isotropic total variation
• The appeals of quadratic majorization-minimization
• Estimating error norms in CG-like algorithms for least-squares and least-norm problems
• Conjugate Gradients
• Lanczos Algorithm
• Lanczos algorithm explained in statistics
• Block CG algorithms revisited
• On finite precision block Lanczos computations
• Fast convergence of trust-regions for non-isolated minima via analysis of CG on indefinite matrices
• Monotonicity, bounds and acceleration of block Gauss and Gauss-Radau quadrature for computing B^T (A)B
• Preconditioning without a preconditioner using randomized block Krylov subspace methods
• Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations
• An adaptive \(s\)-step conjugate gradient algorithm with dynamic basis updating.
• On the real convergence rate of the conjugate gradient method
• Computing interior eigenvalues of large matrices
• Abstract perturbed Krylov methods

This page was built for publication: Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114332)