A Complete Resolution of Forsythe's Conjecture for Restarted Conjugate Gradients
Abstract
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 a complete classification by restart length in the original finite-dimensional setting and identify a sharp threshold. For s=2 and s=3, every problem either terminates or has convergent even and odd residual directions. For every s≥4, there is a diagonal positive definite counterexample of dimension s+4 which never terminates and whose even residual directions do not converge. Together with Akaike's theorem for s=1, this shows that the conjectured universal conclusion is true precisely for s∈{1,2,3} and false for every s≥4. The positive results follow from a degree-independent double-orthogonality identity and an analysis of the low-degree fixed-point sets. At restart length four, rational interval arithmetic and Sturm sequences certify a transverse Hopf point of the leading vector field of the rescaled squared-weight map. Analytic periodic-orbit and shadowing arguments yield the counterexample at restart length four, and degree elevation extends the construction to every larger restart length. The classification for all s≥2 is also formally verified in Lean.
Versions
Related
- On bounds for rank growth of iterands in conjugate gradients for Lyapunov equation
- A Complete Solution to the Conjecture on the Inverse Collatz–Sinogowitz Irregularity Problem
- Parametrized Jacobian Problem over ℂn and its Complete Resolution
- A complete solution to the Boots-Royle/Cao-Vince conjecture
- A Complete Proof of the Strong Conjecture about F-Irregular Graphs
BibTeX
@misc{colbrook2026complete,
title = {{A Complete Resolution of Forsythe's Conjecture for Restarted Conjugate Gradients}},
author = {Matthew J. Colbrook and George Stepaniants and Alex Townsend},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04659},
eprint = {2609.04659},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04659},
}
RIS
TY - UNPB
TI - A Complete Resolution of Forsythe's Conjecture for Restarted Conjugate Gradients
AU - Matthew J. Colbrook
AU - George Stepaniants
AU - Alex Townsend
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.04659
UR - https://arxiv.org/abs/2609.04659
AB - 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 a complete classification by restart length in the original finite-dimensional setting and identify a sharp threshold. For s=2 and s=3, every problem either terminates or has convergent even and odd residual directions. For every s≥4, there is a diagonal positive definite counterexample of dimension s+4 which never terminates and whose even residual directions do not converge. Together with Akaike's theorem for s=1, this shows that the conjectured universal conclusion is true precisely for s∈{1,2,3} and false for every s≥4. The positive results follow from a degree-independent double-orthogonality identity and an analysis of the low-degree fixed-point sets. At restart length four, rational interval arithmetic and Sturm sequences certify a transverse Hopf point of the leading vector field of the rescaled squared-weight map. Analytic periodic-orbit and shadowing arguments yield the counterexample at restart length four, and degree elevation extends the construction to every larger restart length. The classification for all s≥2 is also formally verified in Lean.
ER -