function fig9_9

%  sparse vs non-sparse CGM for solving Ax=b

for isize=1:5
    % A from Laplace's equation
    N=20*isize;
    M=N;
    n=N*M;
    lambda2=1;
    D=2*(1+lambda2)*eye(n,n);
    SD1=diag(-lambda2*ones(n-1,1),-1);
    for i=N+1:N:n-1
        SD1(i,i-1)=0;
    end
    SDM=diag(-ones(n-M,1),-M);
    AA=D+SD1+SD1'+SDM+SDM';

    xe=2*(1-0.5*rand(n,1));
    b=AA*xe;
    dim(isize)=n;

    %%% nonsparse
    tic
    for ic=1:6
        v=cgm(AA,b,xe);
    end
    t_NS=toc;

    %%% sparse version
    A=sparse(AA);
    tic
    for ic=1:6
        v=cgm(A,b,xe);
    end
    time(isize)=toc/t_NS;

end

clf
% get(gcf)
set(gcf,'Position', [25 1115 658 230])
subaxis(1,1,1,1,'MT',0.01,'MB',0.18,'MR',-0.02,'ML',0.06,'P',0.04)
co = [0 0 1;
    0 0.5 0;
    1 0 0;
    0 0.75 0.75;
    0.75 0 0.75;
    0.75 0.75 0;
    0.25 0.25 0.25];
set(groot,'defaultAxesColorOrder',co)

semilogy(dim,time,'--or','LineWidth',1.6,'MarkerSize',9)
hold on

grid on
axis([ 0 10000 0.001 1])
ylabel('Sparse/Non-Sparse')
xlabel('n-axis')
set(gca,'FontSize',16,'FontWeight','bold')
hold off

%exportgraphics(gcf,'/Users/mark/Desktop/times.eps')

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CGM
function x=cgm(A,b,sol)

% set CGM parameters
tol=1000*eps;

n=length(b);
x=zeros(n,1);
% start iteration
r=b-A*x;
d=r;
rr=r'*r;
err=10*tol;
counter=0;
while err>tol
    counter=counter+1;
    q=A*d;
    alpha=rr/(d'*q);
    x=x+alpha*d;
    r=r-alpha*q;
    rr0=rr;
    rr=r'*r;
    beta=rr/rr0;
    d=r+beta*d;
    err=norm(alpha*d,inf);
end

















