Chebyshev bug #375

Activity

1. giordano commented on Sep 14, 2026

   

   giordano

   on Sep 14, 2026

   More actions

   More direct link:

   IterativeSolvers.jl/src/chebyshev.jl

   Line 45 in 36844eb

   cheb.u .= cheb.c .+ β .* cheb.c
2. mkitti commented on Sep 14, 2026

   

   mkitti

   on Sep 14, 2026

   Author

   More actions

   AI evaluation:

   Analysis

   This is a valid bug in the Chebyshev iteration recurrence relation.

   Line 45 contains an error in the search direction update:

   cheb.u .= cheb.c .+ β .* cheb.c  # ❌ WRONG - uses cheb.c twice

   Should be:

   cheb.u .= cheb.c .+ β .* cheb.u  # ✅ CORRECT - blends with previous direction

   Why this matters

   The Chebyshev acceleration method relies on a specific recurrence relation to construct optimal search directions. The update should combine:

   • cheb.c: the current preconditioned residual
   • β * cheb.u: a scaled version of the previous search direction

   The current code incorrectly uses β * cheb.c (the current residual scaled twice), which:

   1. Breaks the mathematical correctness of the Chebyshev recurrence
   2. Destroys the convergence guarantees that depend on the proper recurrence
   3. May cause poor/divergent behavior in actual iterations

   This is a straightforward one-character fix that changes c to u on line 45.

   From Github Copilot.
3. mkitti commented on Sep 14, 2026

   

   mkitti

   on Sep 14, 2026

   Author

   More actions

   AI suggested regression test:

   @testset "Convergence rate" begin
       # Regression test for issue #375: ensures Chebyshev uses correct recurrence u_{k+1} = c + β*u_k
       # (not the buggy c + β*c). This test verifies convergence happens faster than a simple
       # Richardson iteration, which would use c + β*c.
       
       for T in (Float32, Float64)
           # Create a well-conditioned SPD matrix where Chebyshev should converge quickly
           n = 20
           A = Tridiagonal(T.(fill(-1.0, n-1)), T.(fill(2.0, n)), T.(fill(-1.0, n-1)))
           b = ones(T, n)
           x0 = zeros(T, n)
           
           λ_min, λ_max = approx_eigenvalue_bounds(A)
           
           # Run Chebyshev with enough iterations to converge
           x, history = chebyshev!(copy(x0), A, b, λ_min, λ_max, 
                                   reltol=T(1e-6), maxiter=50, log=true, initially_zero=true)
           
           # With the correct recurrence relation, Chebyshev should converge in ~log(1/tol) iterations
           # With the buggy relation (c + β*c), convergence would be much slower
           # For this well-conditioned problem, we expect convergence in roughly 20-30 iterations
           @test niters(history) < 35  # Strict bound to catch regression
           @test history.isconverged
           @test norm(A * x - b) / norm(b) < T(1e-6)
       end
   end
4. haampie commented on Sep 14, 2026

   

   haampie

   on Sep 14, 2026

   Member

   More actions

   I've merged #367, but it looks like more needs to be done.
5. haampie-bot

   added 2 commits that reference this issue on Sep 14, 2026

   Fix the Chebyshev iteration recurrence

   ...

   This issue will close once commit bdaac24 is merged into the 'master' branch.

   bdaac24

   Fix the Chebyshev iteration recurrence

   ...

   This issue will close once commit 51c6e44 is merged into the 'master' branch.

   51c6e44
6. haampie

   closed this as completedin 65fa3e4on Sep 14, 2026