Chebyshev iteration

In numerical linear algebra, the Chebyshev iteration is an iterative method for determining the solutions of a system of linear equations. The method is named after Russian mathematician Pafnuty Chebyshev.

Chebyshev iteration avoids the computation of inner products as is necessary for the other nonstationary methods. For some distributed-memory architectures these inner products are a bottleneck with respect to efficiency. The price one pays for avoiding inner products is that the method requires enough knowledge about spectrum of the coefficient matrix A, that is an upper estimate for the upper eigenvalue and lower estimate for the lower eigenvalue. There are modifications of the method for nonsymmetric matrices A.

Example code in MatLab

 
function [x] = SolChebyshev002(A, b, x0, iterNum, lMax, lMin)

  d = (lMax + lMin) / 2;
  c = (lMax - lMin) / 2;
  preCond = eye(size(A)); % Preconditioner
  x = x0;
  r = b - A * x;

  for i = 1:iterNum % size(A, 1)
      z = linsolve(preCond, r);
      if (i == 1)
          p = z;
          alpha = 1/d;
      else if (i == 2)
          beta = (1/2) * (c * alpha)^2
          alpha = 1/(d - beta / alpha);
          p = z + beta * p;
      else
          beta = (c * alpha / 2)^2;
          alpha = 1/(d - beta / alpha);
          p = z + beta * p;
      end;

      x = x + alpha * p;
      r = b - A * x; %(= r - alpha * A * p)
      if (norm(r) < 1e-15), break; end; % stop if necessary
  end;
end

Code translated from [1] and .[2]

See also

[3]

References
  • "Chebyshev iteration method", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
  1. Barrett, Richard; Michael, Berry; Tony, Chan; Demmel, James; Donato, June; Dongarra, Jack; Eijkhout, Victor; Pozo, Roldan; Romine, Charles; Van der Vorst, Henk (1993). "Templates for the solution of linear systems: building blocks for iterative methods". 43. SIAM. Cite journal requires |journal= (help)
  2. Gutknecht, Martin; Röllin, Stefan (2002). "The Chebyshev iteration revisited". Parallel Computing. 28 (2): 263–283. doi:10.1016/S0167-8191(01)00139-9.
  3. On the Convergence of Chebyshev’s Method for Multiple Polynomial Zeros
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.