python-power-iteration-deflation-stagnation
Done. The verified solution is in ~/power_iter/SOLUTION.md, with the runnable program in ~/power_iter/demo.py.
Two compounding errors in the deflation pipeline:
A₂ = A − λ·q qᵀ/(q·q) with q = a raw mid-iteration vector projects onto span(q), not onto the converged v₁. So A₂ v₁ ≠ 0: the already-found direction still has eigenvalue ≈ λ₁ in the deflated operator, and the next power iteration re-amplifies it — the Rayleigh quotient stagnates back at λ₁.v₁ components re-injected by floating point, which grow.A₂ = A − λ·outer(v₁, v₁) (no denominator — ‖v₁‖=1).power_iteration (Gram–Schmidt), not just the seed.np.array(...) to avoid numpy.matrix @-semantics (a csr − dense expression silently returns a matrix and breaks shapes).On a symmetric matrix with spectrum [1, 0.9, 0.81, 0.729]:
| k=1 | k=2 | k=3 | |
|---|---|---|---|
| True λ | 1.000000 | 0.900000 | 0.810000 |
| Buggy | 1.000000 (resid 8e-7) | 0.995615 (resid 4e-2) ← stagnation at λ₁ | −1.923946 (resid 2.0) |
| Fixed | 1.000000 (resid 8e-7) | 0.900000 (resid 1.2e-6) | 0.810000 (resid 1.1e-6) |
Fixed basis is exactly orthonormal (max |vᵢ·vⱼ| = 0.0), and recovers k=1..4 to ~1e-6 residual in ~100–120 iterations each. The exact fix code from the markdown was also run standalone against the matrix and passed for 4 eigenpairs.
# Evidence - Problem class: python-power-iteration-deflation-stagnation - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-25T16:20:37.376Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Power iteration with Hotelling deflation (A -= lambda * v * v^T) is used to extract the top-k eigenpairs of a large sparse symmetric matrix, but after deflating the dominant eigenpair the iteration for the next eigenpair stagnates at the previous Rayleigh quotient instead of converging to the next eigenvector. The root cause: the deflated matrix is built from the stale, un-normalized pre-convergence iterate rather than the converged eigenvector, so the deflation rank-one term is misaligned and the residual keeps a component along the already-found direction. Fix the pipeline to deflate with the fully converged, unit-norm eigenvector and re-orthogonalize each new Krylov iterate against all previously recovered eigenvectors.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-power-iteration-deflation-stagnation", "provider": "openrouter", "solved_at": "2026-08-25T16:20:37.377Z", "version": "3.11"}Done. The verified solution is in ~/power_iter/SOLUTION.md, with the runnable program in ~/power_iter/demo.py.
Two compounding errors in the deflation pipeline:
A₂ = A − λ·q qᵀ/(q·q) with q = a raw mid-iteration vector projects onto span(q), not onto the converged v₁. So A₂ v₁ ≠ 0: the already-found direction still has eigenvalue ≈ λ₁ in the deflated operator, and the next power iteration re-amplifies it — the Rayleigh quotient stagnates back at λ₁.v₁ components re-injected by floating point, which grow.A₂ = A − λ·outer(v₁, v₁) (no denominator — ‖v₁‖=1).power_iteration (Gram–Schmidt), not just the seed.np.array(...) to avoid numpy.matrix @-semantics (a csr − dense expression silently returns a matrix and breaks shapes).On a symmetric matrix with spectrum [1, 0.9, 0.81, 0.729]:
| k=1 | k=2 | k=3 | |
|---|---|---|---|
| True λ | 1.000000 | 0.900000 | 0.810000 |
| Buggy | 1.000000 (resid 8e-7) | 0.995615 (resid 4e-2) ← stagnation at λ₁ | −1.923946 (resid 2.0) |
| Fixed | 1.000000 (resid 8e-7) | 0.900000 (resid 1.2e-6) | 0.810000 (resid 1.1e-6) |
Fixed basis is exactly orthonormal (max |vᵢ·vⱼ| = 0.0), and recovers k=1..4 to ~1e-6 residual in ~100–120 iterations each. The exact fix code from the markdown was also run standalone against the matrix and passed for 4 eigenpairs.
# Evidence - Problem class: python-power-iteration-deflation-stagnation - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-25T16:20:37.376Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Power iteration with Hotelling deflation (A -= lambda * v * v^T) is used to extract the top-k eigenpairs of a large sparse symmetric matrix, but after deflating the dominant eigenpair the iteration for the next eigenpair stagnates at the previous Rayleigh quotient instead of converging to the next eigenvector. The root cause: the deflated matrix is built from the stale, un-normalized pre-convergence iterate rather than the converged eigenvector, so the deflation rank-one term is misaligned and the residual keeps a component along the already-found direction. Fix the pipeline to deflate with the fully converged, unit-norm eigenvector and re-orthogonalize each new Krylov iterate against all previously recovered eigenvectors.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-power-iteration-deflation-stagnation", "provider": "openrouter", "solved_at": "2026-08-25T16:20:37.377Z", "version": "3.11"}