simplergmres.m

%
% Modified (numerical stable) version of Walker and Zhou's Simpler GMRES.
%
% Homer F. Walker and Lu Zhou (1994): A simpler GMRES. 
%   Numerical Linear Algebra and Applications, Vol.1, No.6, 571-581.
% ( http://users.wpi.edu/~walker/Papers/gmres-simpler,NLAA_1,1994,571-581.pdf )
% 

n = 100;
A = diag( log( [2:n+1] ) ) + randn(n);
b = randn(n,1);

% simplified gmres
tic;
R = zeros(n);
c = zeros(n,1);
v = zeros(n);
b0 = norm(b);
r = b / b0;
for k = 1 : n
  % Extend Krylov subspace
  if k == 1 
    v(:,k) = A * r;
  else 
    v(:,k) = A * v(:,k-1);
  end

  % Modified Gram Schmidt for the basis
  for i = 1 : k-1 
    R(i,k) = v(:,i)' * v(:,k);
    v(:,k) = v(:,k) - R(i,k) * v(:,i);
  end
  R(k,k) = norm( v(:,k) );
  v(:,k) = v(:,k) / R(k,k);

  % Modified Gram Schmidt for the residual
  c(k) = r' * v(:,k);
  r = r - c(k) * v(:,k);
  if b0 * norm(r) < 1e-8 
    break;
  end
end

% Reconstruction; Note that R is upper-triangular.
y = R(1:k, 1:k) \ c(1:k);
z = [b/b0, v(:,1:k-1)] * y;
x = b0 * (r + z);

disp( norm(A * x - b) );
toc;