On the Forsythe conjecture

Open problem

• The Forsythe conjecture remains largely open after more than 50 years, with published results beyond s = 1 remaining surprisingly limited.Prior work includes proofs for s = 1 and numerical or analytical studies particularly focused on s = 2.Source: §1 · p. 1

Contribution

• The paper generalizes the Forsythe conjecture from symmetric positive definite matrices to symmetric and nonsymmetric matrices using an Arnoldi cross iteration alternating A and A^T.For symmetric matrices, the Arnoldi and Lanczos projection processes provide the corresponding formulation.Source: §1 · p. 2

Generalized conjecture

• The authors conjecture that the Arnoldi cross iteration generally has the same oscillatory limiting behavior as restarted conjugate gradient, although such behavior usually does not occur for nonsymmetric methods using only A.The cross iteration is intended to capture the behavior of the underlying projection process, not ordinarily to solve a linear system or eigenvalue problem.Source: §1 · p. 2

Results

• The paper proves several new limiting-behavior results, including results for s = 1 with symmetric matrices and with orthogonal matrices whose eigenvalues have only positive or only negative real parts.For s = 1 and symmetric A, the iteration reduces to the one studied in, for which the paper gives a simpler alternative proof.Source: §1 · p. 2

Motivation

• The paper presents its modern projection-process formulation as a more transparent basis for motivating further research beyond the original conjecture.The discussion connects the work to related cyclic behavior observed in other restarted Krylov subspace methods, especially for symmetric or normal matrices.Source: §1 · pp. 1–2

Projection formulation

• The s-dimensional search space is the Krylov subspace x0 + K_s(A, r0), where the restarted iterate is selected by A-orthogonality of the error to that space.For s = 1, this reduces to minimizing f along the steepest-descent line x0 + αr0.Source: §2 · pp. 3–4

Method

• The optimum s-gradient method is mathematically equivalent to the s-th iterate of conjugate gradient applied to Ax = b with initial vector x0.Its iterate minimizes the quadratic objective over x0 + K_s(A, r0) and satisfies A-orthogonality of the error to that Krylov subspace.Source: §2 · p. 4

Motivation

• Forsythe’s restarted method converges to x = A^-1b, but the central question is the directions from which its iterates approach that limit.The analysis uses normalized vectors generated from repeated applications of the projection step with restart length s.Source: §2 · p. 4

Known case s = 1

• For s = 1, the normalized even and odd sequences asymptotically alternate between directions determined by eigenvectors associated with the smallest and largest eigenvalues.The resulting asymptotic collinearity explains why the non-normalized restarted error norms can converge to zero only linearly.Source: §2 · p. 4

Forsythe conjecture

• Forsythe’s conjecture states that for 2 ≤ s < d(A), each normalized subsequence {y2k} and {y2k+1} has a single limit vector.The s = 1 case was proved earlier, while numerical evidence motivated the conjecture for general restart lengths.Source: §2 · p. 4

Generalization

• Because the original projection process uses the A-inner product, it requires A to be symmetric positive definite; the paper therefore replaces it with a projection process defined for general A.This broader formulation supports a generalization to symmetric and nonsymmetric matrices.Source: §3 · p. 5

Arnoldi projection

• For ACI(s), the Arnoldi projection is the orthogonalized sth Krylov vector, equivalently w = P_s(A; v)v for a uniquely determined monic polynomial when d(A, v) ≥ s.The projected vector minimizes the norm of A^s v plus a vector from K_s(A,v), and it is zero exactly when d(A,v) ≤ s.Source: §3 · p. 5

Algorithm and motivation

• The Arnoldi cross iteration alternates projections with A and A^T, using the Arnoldi projection process and normalized vectors to generalize the Forsythe framework to nonsymmetric matrices.For symmetric matrices, the A and A^T steps coincide, recovering essentially Forsythe’s algorithm with the Arnoldi or Lanczos projection process.Source: §3 · p. 5

Basic properties

• Under the stated unit-norm and grade assumptions, every ACI(s) step is well defined and its interlacing norms satisfy ||e_wk|| ≤ ||e_vk+1|| ≤ ||e_wk+1|| ≤ ||e_vk+2|| ≤ Φ_s(A) = Φ_s(A^T).Equality characterizes successive normalized vectors that are scalar multiples of one another.Source: §3 · pp. 6–7

Limiting behavior

• The interlacing norm sequences are bounded and converge to the same limit, while the normalized sequences satisfy ||w_k+1 − w_k|| → 0 and ||v_k+1 − v_k|| → 0.Thus the iteration becomes asymptotically stationary in consecutive-vector distance, although this does not by itself establish convergence to one vector.Source: §3 · pp. 7–8

ACI(s) conjecture

• The ACI(s) conjecture asserts that {v_k} has a single limit vector, but the paper proves only that every limit vector is a fixed point of T_A^T ◦ T_A and that isolated multiple limit vectors cannot occur.The fixed-point conclusion follows from continuity, while the exclusion of isolated multiple limits uses the vanishing distance between consecutive vectors.Source: §3 · pp. 8–9

Open issue

• Vanishing distances between consecutive vectors are insufficient for convergence: a bounded sequence can continue moving around a limit set despite ||v_k+1 − v_k|| → 0.This explains why the proven asymptotic stationarity does not settle the single-limit-vector conjecture.Source: §3 · p. 8

Proved cases

• The paper establishes general symmetric-matrix results and proves the ACI(1) conjecture for symmetric matrices and for real orthogonal matrices whose eigenvalues have only positive or only negative real parts.These results extend the known theory, while the general conjecture remains open.Source: §4 · p. 9

4.1. The ACI(s) for symmetric matrices.

• For symmetric A, every limit vector has grade s < d(A, v*) ≤ 2s, and when d(A, v0) = s + 1 all even iterates coincide.The general symmetric-matrix conjecture could follow if the finitely many limit polynomials implied finitely many limit vectors, but this remains unresolved for s = 2.Source: §4.1 · pp. 10–12

4.2. Proof of the ACI(1) conjecture for symmetric matrices.

• The symmetric ACI(1) proof applies after reducing A to a diagonal matrix with distinct eigenvalues and identifying α as the Rayleigh quotient.The paper also notes related proofs by Afanasjew, Eiermann, Ernst, and Güttel [1, Section 3], whose approach gives more information about limiting-vector structure.Source: §4.2 · pp. 12–13
• For symmetric A with s = 1, the even-iterate sequence converges to a single limit vector.The proof reduces limit vectors to finitely many normalized combinations of two eigenvectors after orthogonal diagonalization.Source: §4.2 · pp. 12–13

4.3. On the ACI(1) conjecture for orthogonal matrices.

• For the stated block-diagonal A and any unit initial vector v0 with d(A,v0) ≥ 2, every limit vector v∗ has d(A,v∗) = 2, while α = β equals an eigenvalue’s real part and is independent of the limit vectors.The limit vector lies in the two-dimensional block corresponding to that eigenvalue.Source: §4.3 · pp. 14–15
• For the orthogonal block-diagonal case, the analysis assumes pairwise distinct real parts of non-real eigenvalues, all positive or all negative, and at most one 1×1 block.The displayed results are stated and proved only for the positive case.Source: §4.3 · p. 14
• Under Lemma 4.5’s assumptions, norms of the nonselected orthogonal blocks converge to zero at least linearly after some index k0.This is the next step toward showing that the limit set contains only one uniquely determined vector.Source: §4.3 · p. 16
• Theorem 4.8 proves that {v_k} converges to a single limit vector for specified orthogonal block matrices when d(A,v_0)≥2 and v_0^(1)=0.The matrix has blocks G_j with 0<c_1<⋯<c_m<1, with an optional block.Source: §4.3 · p. 17
• When 0∈F(A), Lemma 4.9 establishes α=β=0 under a block-support condition, but proving linear convergence of α_k to zero remains open.The unresolved step is to show the coefficients α_k converge to zero linearly.Source: §4.3 · pp. 18–19
• An explicit orthogonal example with 0∈F(A) has the constant sequence v_k=v_0 and a unique limit v* satisfying d(A,v*)=4.Here A=diag(G_1,G_2), c_1∈(−1,0), c_2=−c_1, and d(A)=d(A,v_0)=4.Source: §4.3 · p. 19
• For normal matrices, the ideal Arnoldi problem at s=1 is solved by the center of the smallest enclosing eigenvalue disk.For the orthogonal cases, that center is c_1 under Lemma 4.5 assumptions and 0 under Lemma 4.9 assumptions.Source: §4.3 · pp. 19–20
• The resulting limit vector solves the ideal Arnoldi problem for orthogonal A at s=1 under the appropriate initial-vector assumptions, without establishing uniqueness.For the 0-centered case, any v* in the relevant set satisfies the stated residual and norm relations.Source: §4.3 · p. 20

• The authors prove existence of a single limit vector for even iterates when s = 1 and A = A^T, and for all iterates when s = 1 and A is orthogonal with 0 ∉ F(A).They also note that the uniqueness proof in the symmetric case is simpler than previously published proofs.Source: §5 · p. 20
• For s = 1, monotonically increasing norms appear closely related to decreasing residual norms in Rayleigh quotient and two-sided iterations.The paper identifies the exact relations between these iteration families as a subject for further research.Source: §5 · p. 20
• The Forsythe conjecture and its generalization to ACI(s) still remain largely open.Source: §5 · p. 20