ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A shift near the wanted eigenvalue suppresses its component under repeated implicit restarts

Example

Let $A = diag (1, 2, 3)$ , start from $v = (e_{1} + e_{2} + e_{3}) / \sqrt{3}$ , and seek the largest eigenvalue $3$ . Use an implicit restart from dimension $m = 2$ to $r = 1$ with the fixed shift rule $μ = 29 / 10$ on each cycle, residual tolerance $τ = 0$ , and restart budget at least $t$ when considering $t$ cycles. This shift rule is allowed by the procedure; it is not claimed to be a good selection rule.

Supply the following finite-return projected solver for this example. For a $2 \times 2$ Hermitian matrix $H = (\begin{array}{cc} α & b \\ \overline{b} & δ \end{array})$ , if $b = 0$ , return success with the ordered pairs $(α, e_{1})$ and $(δ, e_{2})$ . If $b \neq 0$ , set $D = \sqrt{(α - δ)^{2} + 4 ∣ b ∣^{2}}, λ_{\pm} = (α + δ \pm D) / 2,$ and return success with the ordered pairs $(λ_{-}, (b, λ_{-} - α)^{T})$ and $(λ_{+}, (b, λ_{+} - α)^{T})$ . Return unavailable on other shapes or non-Hermitian inputs. Each displayed vector is nonzero, direct multiplication verifies its eigenpair equation, and the two factors reproduce the quadratic characteristic polynomial. This supplied finite-dimensional example provider is not a general eigensolver or a new restart method.

Verification

Given: The exact diagonal matrix, starting vector, target, and shift above.

[F1] Exact implicit Arnoldi restart applies its shift polynomial and preserves an Arnoldi residual identity: for $r = 1$ , the exact implicit restart retains the one-dimensional filtered Krylov space generated by $q (A) v$ .

[F2] Eigenvalues, eigenvectors, eigenspaces $E_{λ} (T) = \ker (T - λ I)$ , and the spectrum $σ_{F} (T)$ of an endomorphism: an eigenvector is a nonzero vector satisfying $A u = λ u$ .

1.1givenF1F2algebra

Every projected $H_{2} = V_{2}^{*} A V_{2}$ in this example is Hermitian because $A^{*} = A$ , so the supplied two-dimensional solver returns valid complete projected data in finite exact work. By [F1], $q (A) v = (- 19 e_{1} - 9 e_{2} + e_{3}) / (10 \sqrt{3})$ . The squared component weights are proportional to $361, 81, 1$ , so the Rayleigh quotient of the restarted vector is $(1 \cdot 361 + 2 \cdot 81 + 3 \cdot 1) / (361 + 81 + 1) = 526 / 443 < 2$ , whereas the initial quotient is $(1 + 2 + 3) / 3 = 2$ . The wanted component-to- $e_{1}$ component ratio falls from 1 to 1/19.

2.1givenF1F2step 1.1algebra

Repeating the same exact restart multiplies the $e_{3}$ component by $q (3) = 1 / 10$ and the $e_{1}$ component by $q (1) = - 19 / 10$ at every cycle. Hence after $t$ cycles their magnitude ratio is $(1 / 19)^{t}$ , which tends to zero. This shift choice suppresses the wanted eigendirection and gives no general convergence claim.

3.1givenF1F2step 2.1algebra

For each finite $t$ , the restart vector is proportional to $q (A)^{t} v$ , with all coordinates nonzero because none of $q (1), q (2), q (3)$ vanishes. If a Ritz residual were zero, its lifted vector would satisfy $A u = θ u$ ; the diagonal equations $(λ_{i} - θ) u_{i} = 0$ and distinct $λ_{i}$ force $u$ to be proportional to some $e_{i}$ . No $e_{i}$ lies in $K_{2} (A, q (A)^{t} v)$ : representing one would require $c + d λ_{j} = 0$ for the other two distinct eigenvalues, hence $c = d = 0$ . Also $q (A)^{t} v, A q (A)^{t} v, A^{2} q (A)^{t} v$ are independent because their coordinate determinant is the product of the three nonzero coordinates and the Vandermonde determinant for $1, 2, 3$ . Thus no pair is accepted at tolerance zero and the space is not invariant before each scheduled restart.

4.1givenF1F2algebra∎

In a separate boundary run with shift $μ = 3$ , the filter has $q (3) = 0$ and $q (A) v = (- 2 e_{1} - e_{2}) / \sqrt{3}$ , so the wanted $e_{3}$ component is removed exactly in one filtering step. The filtered vector is still nonzero, so this is not filtered breakdown; it is a shift-selection failure.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

16 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yousef Saad, Numerical Methods for Large Eigenvalue Problems, second edition, §7.3.1 (standard reference, not scraped)
Peter Arbenz, Lecture Notes on Solving Large Scale Eigenvalue Problems, §11.2 (standard reference, not scraped)