Matlab Demos in the Week-5 Lecture

Contents

The effects of amd and symamd on Cholesky factorizing a SPD matrix

% Approximate minimum degree is an efficient method for matrix reordering.
% In this demo, a 7701x7701 SPD matrix is used.
% Two ordering routines amd and symamd are tested.
A = gallery('wathen',50,50); % Content of amd_demo.m.
tic; p = amd(A); toc
tic; s = symamd(A); toc
L = chol(A,'lower');
Lp = chol(A(p,p),'lower');
Ls = chol(A(s,s),'lower');
figure;
subplot(2,3,1);    spy(A);
title('Sparsity structure of A');
subplot(2,3,2); spy(A(p,p));
title('Sparsity structure of AMD ordered A');
subplot(2,3,3); spy(A(s,s));
title('Sparsity structure of SYMAMD ordered A');
subplot(2,3,4); spy(L);
title('Sparsity structure of Cholesky factor of A');
subplot(2,3,5); spy(Lp);
title('Sparsity structure of Cholesky factor of AMD ordered A');
subplot(2,3,6); spy(Ls);
title('Sparsity structure of Cholesky factor of AMD ordered A');
set(gcf,'Position',[100 100 1380 700]);
% The results show amd is faster than symamd.

Elapsed time is 0.003610 seconds.
Elapsed time is 0.011802 seconds.

The effect of colamd for LU factorizing a nonsymmetric matrix

% colamd (column amd) is suitable for reordering a nonsysmmetric matrix.
% In this demo, lu is used to handle the matrices before and after reordering
% with colamd. lu works like GPLU algorithm, which calculates PA=LU, and
% then it feeds L+U to the spy plot.
load west0479         % Content of colamd_demo.m
A = west0479;
p = colamd(A);
figure(2);
subplot(2,2,1), spy(A,4), title('A')
subplot(2,2,2), spy(A(:,p),4), title('A(:,p) with colamd')
subplot(2,2,3), spy(lu(A),4), title('lu(A)')
subplot(2,2,4), spy(lu(A(:,p)),4), title('lu(A(:,p))')

Compare RCM and AMD orderings

% Reverse Cuthill-McKee (RCM) is an ordering which can move the
% nonzeros towards the main diagonal of matrix. It's good for some "long
% and thin" structral problem, and enables the usage of band matrix solver.
% In this demo, we show the effect of performing symrcm ordering, and
% compare it with the symamd ordering. Obviously, the latter makes fewer
% fill-ins.
B = bucky+4*speye(60);  % Content of rcm_amd.m
r = symrcm(B);
p = symamd(B);
R = B(r,r);
S = B(p,p);
figure(3);
subplot(2,2,1), spy(R,4), title('B(r,r)')
subplot(2,2,2), spy(S,4), title('B(s,s)')
subplot(2,2,3), spy(chol(R),4), title('chol(B(r,r))')
subplot(2,2,4), spy(chol(S),4), title('chol(B(s,s))')

Published with MATLAB® 7.14