function [lamb, y, res, info]=SD(A, x, k, U, nrmA, tol)
%
%  Steep decent method to compute the kth smallest eigenvalue of A
%
%
% RCL 6/27/2009
%---------------------------------------------------------------
%
%  Input
%
%        A     n-by-n Hermitian matrix
%        x     n-vector, initial guess to the kth eigenvector
%        k     index of the desired eigenvalue
%        U     n-by-(k-1) the 1st (k-1) accurate eigenvectors
%        nrmA  An estimate of ||A||
%        tol   tolerance for testing convergence
%
%  Output
%
%        lamb  converged eigenvalue
%        y     corresponding eigenvector
%        res   residual error  ||A y - lamb y||
%        info  the number of SD steps
%
% Note: For the standard symmetric eigenvalue problem, if x'*U=0, then
% r'*U=0, too. But numberically, since x'*U approx 0, it is possible
% after many SD steps x may have nonnegligible commonents in U. Therefore
% it may be necessary to orthogonalize x against U every many SD steps.
%
n=max(size(A));
maxitn=round(0.2*n); 
for i=1:k-1,
    s=U(:,i)'*x; x=x-s*U(:,i);
end
x=(1/norm(x))*x; Ax=A*x; rho=x'*Ax; r=Ax-rho*x; nrmr=norm(r); 
err=nrmr/(nrmA+abs(rho)); itn=0;
while err > tol & itn < maxitn,
    r=(1/nrmr)*r;
    rhos=[rho r'*(A*r)];
    [y, t]=onestep0(Ax,x,r,rhos);
    x=y; 
    for i=1:k-1,
        s=U(:,i)'*x; x=x-s*U(:,i);
    end
    x=(1/norm(x))*x; Ax=A*x; rho=x'*Ax; r=Ax-rho*x; nrmr=norm(r); 
    err=nrmr/(nrmA+abs(rho));
    itn = itn+1;
end
info = itn; y=x; lamb=rho; res=nrmr;
