Forsythe's conjecture beyond restart length two
Let $A \in \mathbb{R}^{n \times n}$ be symmetric positive definite and $b, x_0 \in \mathbb{R}^n$. Restarted conjugate gradients with restart length $s$ performs, in exact arithmetic, $s$ conjugate-gradient steps from the last iterate and then restarts, discarding the previous search directions. Thus, if $x_j$ is the iterate after $j$ restart cycles and $r_j = b - Ax_j$, then $x_{j+1}$ minimises the $A$-norm of the error $x - A^{-1}b$ over $x \in x_j + \operatorname{span}\{r_j, Ar_j, \dots, A^{s-1}r_j\}$; this is Forsythe's $s$-dimensional optimum gradient method. When the iteration never terminates, that is, $r_j \ne 0$ for every $j$, put $y_j = r_j/\|r_j\|_2$. For $s = 1$, steepest descent, $(y_{2j})$ and $(y_{2j+1})$ then both converge (Akaike, 1959); for $s = 2$, proofs were claimed in 2026, independently, by Peng, by Liesen, and by Colbrook, Stepaniants and Townsend (see Amsel et al.).
Problem. Do $(y_{2j})_{j \ge 0}$ and $(y_{2j+1})_{j \ge 0}$ both converge in $\mathbb{R}^n$ for all $n$ and $s$ with $3 \le s < n$, every symmetric positive definite $A \in \mathbb{R}^{n \times n}$ and all $b, x_0 \in \mathbb{R}^n$ for which the iteration never terminates?
Source: Forsythe (1968), p. 66, for every restart length s; in this form, Faber, Liesen and Tichý (2023), Section 2. OpenProblemsInNLA states it for 3 ≤ s < n.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- DS, OC
- Keywords
- conjugate gradient methods, Krylov subspace methods, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{forsythe1968,
author = {Forsythe, George E.},
title = {On the asymptotic directions of the $s$-dimensional optimum gradient method},
journal = {Numer. Math.},
volume = {11},
number = {1},
year = {1968},
pages = {57--76},
doi = {10.1007/BF02165472},
}
@article{faber2023,
author = {Faber, Vance and Liesen, J{\"o}rg and Tich{\'y}, Petr},
title = {On the {F}orsythe conjecture},
journal = {BIT Numer. Math.},
volume = {63},
number = {4},
year = {2023},
pages = {Paper No. 49},
doi = {10.1007/s10543-023-00991-x},
eprint = {2209.14579},
archivePrefix = {arXiv},
}
@article{akaike1959,
author = {Akaike, Hirotugu},
title = {On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method},
journal = {Ann. Inst. Statist. Math.},
volume = {11},
number = {1},
year = {1959},
pages = {1--16},
doi = {10.1007/BF01831719},
}
@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},
}
@misc{colbrook2026forsythe2,
author = {Colbrook, Matthew J. and Stepaniants, George and Townsend, Alex},
title = {A Proof of the {F}orsythe Conjecture for the Two-Step Restarted Conjugate Gradient Method},
year = {2026},
eprint = {2608.02852},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ie01,
author = {Townsend, Alex},
title = {{IE-01}: Forsythe's conjecture beyond restart length two},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-01/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
Forsythe's conjecture, published in 1968, asserts that for each restart length $s$, every exact-arithmetic restarted conjugate-gradient iteration on a real symmetric positive definite problem either terminates or has normalised residuals that converge separately along the even and odd restart subsequences. Apart from the classical steepest-descent case, this asymptotic question remained unresolved in full generality for nearly six decades. We give …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00217, "Forsythe's conjecture beyond restart length two", clopen.solutions.