Finite-Precision Symmetric Krylov Methods: Exact Rounding Examples, Block Paige Identities,and a Variable-Block Lanczos Model
Abstract
Short-recurrence Krylov methods that are equivalent in exact arithmetic often diverge in floating-point arithmetic. To illustrate this, we provide an exactly representable two-cycle for steepest descent with a recursively updated residual. A complementary convergence theorem gives a sufficient condition under which the stored residual decreases geometrically. We then show that a second positive definite family yields different outcomes for a Hestenes--Stiefel Conjugate Gradient (CG) implementation and a direct Lanczos--Galerkin approach. CG finds the exact solution after four updates, whereas the two-step projected system becomes inconsistent. Under stated perturbation and transfer hypotheses, a common spectral enclosure gives comparable convergence bounds. For a dense, left-to-right evaluation order, we prove a sufficient precision bound for a prescribed backward error within n updates for an n× n matrix, together with a computable stopping test and specified exponent-range assumptions. We use polynomial estimates and numerical experiments to examine the trade-off between working precision and the number of CG iterations needed to achieve a prescribed backward error. We also compare results on inexact matrix-vector products and preconditioning with the frameworks of Paige and Greenbaum. For block Lanczos, we analyze Householder orthogonalization and singular-value truncation as the block size changes. Under componentwise and normwise error bounds, the computed coefficients satisfy a controlled local recurrence and an exact block Lanczos relation for a nearby symmetric problem in a larger space. A block form of Paige's identity bounds the overlap with a Ritz vector along its residual coordinate direction. An inter-block recurrence describes the evolution of overlap, and a Gram-matrix argument gives a count of additional nearby Ritz values.
Related
- Characteristic identities for orthogonal quantum matrices: examples
- Collision Positivity for Three-Variable Symmetric Monomial Inequalities
- Collision Positivity for Symmetric Orbit-Sum Inequalities in Arbitrary Dimension: A Complete Two-Variable Criterion
- Asymptotic Rounding Laws for Optimal Thresholds in Secretary Problems
- Certified Fourier rounding for the real Grothendieck inequality
BibTeX
@misc{sinha2026finiteprecision,
title = {{Finite-Precision Symmetric Krylov Methods: Exact Rounding Examples, Block Paige Identities,and a Variable-Block Lanczos Model}},
author = {Mohit Sinha},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08066},
eprint = {2609.08066},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08066},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Finite-Precision Symmetric Krylov Methods: Exact Rounding Examples, Block Paige Identities,and a Variable-Block Lanczos Model
AU - Mohit Sinha
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08066
UR - https://arxiv.org/abs/2609.08066
AB - Short-recurrence Krylov methods that are equivalent in exact arithmetic often diverge in floating-point arithmetic. To illustrate this, we provide an exactly representable two-cycle for steepest descent with a recursively updated residual. A complementary convergence theorem gives a sufficient condition under which the stored residual decreases geometrically. We then show that a second positive definite family yields different outcomes for a Hestenes--Stiefel Conjugate Gradient (CG) implementation and a direct Lanczos--Galerkin approach. CG finds the exact solution after four updates, whereas the two-step projected system becomes inconsistent. Under stated perturbation and transfer hypotheses, a common spectral enclosure gives comparable convergence bounds. For a dense, left-to-right evaluation order, we prove a sufficient precision bound for a prescribed backward error within n updates for an n× n matrix, together with a computable stopping test and specified exponent-range assumptions. We use polynomial estimates and numerical experiments to examine the trade-off between working precision and the number of CG iterations needed to achieve a prescribed backward error. We also compare results on inexact matrix-vector products and preconditioning with the frameworks of Paige and Greenbaum. For block Lanczos, we analyze Householder orthogonalization and singular-value truncation as the block size changes. Under componentwise and normwise error bounds, the computed coefficients satisfy a controlled local recurrence and an exact block Lanczos relation for a nearby symmetric problem in a larger space. A block form of Paige's identity bounds the overlap with a Ritz vector along its residual coordinate direction. An inter-block recurrence describes the evolution of overlap, and a Gram-matrix argument gives a count of additional nearby Ritz values.
ER -