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
          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==

  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.
  2. ↑ Gutknecht, Martin; Röllin, Stefan (2002). "The Chebyshev iteration revisited". Parallel Computing 28 (2): 263–283.
  3. ↑ On the Convergence of Chebyshev’s Method for Multiple Polynomial Zeros

External links

This article is issued from Wikipedia - version of the Friday, November 27, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.