Precision required for conjugate gradients to attain backward accuracy in n steps
Fix $n \ge 1$, $K \ge 1$ and $0 < \varepsilon < 1/2$. At precision $t \ge 2$ the data are a symmetric positive definite $A \in \mathbb{R}^{n \times n}$ with $\kappa_2(A) \le K$ and a vector $b \in \mathbb{R}^n \setminus \{0\}$, all of whose entries are exactly representable with $t$ significant binary digits and an unbounded exponent; they are used exactly, and the error below is measured against them. Each operation $\circ \in \{+, -, \times, /\}$ returns $\mathrm{fl}(y \circ z) = (y \circ z)(1 + \delta)$ for some $\delta$ with $|\delta| \le u = 2^{-t}$, any such $\delta$ being allowed (divisors nonzero, no underflow or overflow). Products are rounded separately from additions, inner products and the rows of matrix–vector products are accumulated from left to right in index order starting from zero, and copies, sign changes and comparisons are exact. The conjugate gradient method is run without preconditioning, restarts, residual replacement or reorthogonalisation: $x_0 = 0$, $r_0 = p_0 = b$, $\rho_0 = \mathrm{fl}(r_0^T r_0)$ and, for $j = 0, \dots, n - 1$, $$q_j = \mathrm{fl}(Ap_j), \quad d_j = \mathrm{fl}(p_j^T q_j), \quad \alpha_j = \mathrm{fl}(\rho_j / d_j), \quad x_{j+1} = \mathrm{fl}(x_j + \alpha_j p_j), \quad r_{j+1} = \mathrm{fl}(r_j - \alpha_j q_j),$$ followed, if another step is needed, by $$\rho_{j+1} = \mathrm{fl}(r_{j+1}^T r_{j+1}), \quad \beta_j = \mathrm{fl}(\rho_{j+1} / \rho_j), \quad p_{j+1} = \mathrm{fl}(r_{j+1} + \beta_j p_j).$$ The run stops when the computed residual $r_j$ is zero, or before a division by zero. It succeeds if some iterate $x_j$ with $j \le n$ produced before it stops has normwise backward error $$\eta(x_j) = \frac{\|b - Ax_j\|_2}{\|A\|_2 \|x_j\|_2 + \|b\|_2} \le \varepsilon,$$ where $b - Ax_j$ is the true residual, not the computed $r_j$. Let $P_{\mathrm{CG}}(n, K, \varepsilon)$ be the least integer $t_{\min} \ge 2$ such that the run succeeds at every precision $t \ge t_{\min}$, for all such data and every choice of the rounding errors $\delta$, and $\infty$ if there is none. In exact arithmetic the conjugate gradient method reaches the solution in at most $n$ steps (Hestenes and Stiefel). Sinha reports, for essentially this arithmetic model, that $O(n^3\log(2 + nK/\varepsilon))$ bits suffice, and that for $n = 2$ more than $\log_2 K - \log_2(81/8)$ bits are needed.
Problem. Determine, up to universal multiplicative constants, the worst-case dependence of $P_{\mathrm{CG}}(n, K, \varepsilon)$ on $n$, $K$ and $\varepsilon$.
Source: Amsel et al. (2026), Problem 2.17 (Section 2.6, scribed by T. Chen and A. Greenbaum); in this form, with a fixed implementation and arithmetic model, OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- backward errors, conjugate gradient methods, OpenProblemsInNLA, rounding errors
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{amsel2026,
author = {Amsel, Noah and Baumann, Yves and Beckman, Paul and B{\"u}rgisser, Peter and Cama{\~n}o, Chris and Chen, Tyler and Chow, Edmond and Damle, Anil and Derezinski, Michal and Embree, Mark and Epperly, Ethan N. and Falgout, Robert and Fornace, Mark and Greenbaum, Anne and Greif, Chen and Halikias, Diana and Huang, Zhen and Jarlebring, Elias and Koutis, Yiannis and Kressner, Daniel and Kyng, Rasmus and Liesen, J{\"o}rg and Lok, Jackie and Meyer, Raphael A. and Nakatsukasa, Yuji and Pearce, Kate and Peng, Richard and Persson, David and Rebrova, Eliza and Schneider, Ryan and Shah, Rikhav and Solomonik, Edgar and Srivastava, Nikhil and Townsend, Alex and Webber, Robert J. and Williams, Jess},
title = {Linear Systems and Eigenvalue Problems: Open Questions from a {S}imons Workshop},
year = {2026},
eprint = {2602.05394},
archivePrefix = {arXiv},
note = {Version 3, 21 August 2026},
}
@article{hestenes1952,
author = {Hestenes, Magnus R. and Stiefel, Eduard},
title = {Methods of conjugate gradients for solving linear systems},
journal = {J. Research Nat. Bur. Standards},
volume = {49},
number = {6},
year = {1952},
pages = {409--436},
doi = {10.6028/jres.049.044},
}
@misc{sinha2026,
author = {Sinha, Mohit},
title = {Finite-Precision Symmetric {K}rylov Methods: Exact Rounding Examples, Block {P}aige Identities, and a Variable-Block {L}anczos Model},
year = {2026},
eprint = {2609.08066},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ie20,
author = {Townsend, Alex},
title = {{IE-20}: Precision required for conjugate gradients to attain backward accuracy in n steps},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-20/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
We study the fixed CG recurrence and adversarial scalar relative-error envelope of the problem. The scalar threshold is determined exactly by a degree-five rational inequality. In general dimension, set $H=\min\{K,64/\varepsilon^2\}$ and $D=1024H^2$, and let $m$ be the minimum of the dimension, an explicit Chebyshev horizon of order $\sqrt K\log(K/\varepsilon)$, and a backward-error horizon of order $\varepsilon^{-2/3}$. We prove the sufficient …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Exact Scalar Threshold and Extended Precision Bounds v1 recorded from OpenProblemsInNLA @ eb7c9d6, IE-20/report.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00190, "Precision required for conjugate gradients to attain backward accuracy in n steps", clopen.solutions.