%% Reordering and Factorization of Sparse Matrices
% This example shows the effects of reordering and factorization on sparse matrices.
% If you obtain a good column permutation p that reduces fill-in, perhaps from symrcm or colamd, then computing lu(S(:,p)) takes less time and storage than computing lu(S).
% Create a sparse matrix using the Bucky ball example.

B = bucky;

% B has exactly three nonzero elements in each row and column.
%
% Create two permutations, r and m using symrcm and symamd respectively.

r = symrcm(B);
m = symamd(B);

% The two permutations are the symmetric reverse Cuthill-McKee ordering and the symmetric approximate minimum degree ordering.
%
% Create spy plots to show the three adjacency matrices of the Bucky Ball graph with these three different numberings. The local, pentagon-based structure of the original numbering is not evident in the others.

figure
subplot(1,3,1)
spy(B)
title('Original')

subplot(1,3,2)
spy(B(r,r))
title('Reverse Cuthill-McKee')

subplot(1,3,3)
spy(B(m,m))
title('Min Degree')

% The reverse Cuthill-McKee ordering, r, reduces the bandwidth and concentrates all the nonzero elements near the diagonal. The approximate minimum degree ordering, m, produces a fractal-like structure with large blocks of zeros.
%
% To see the fill-in generated in the LU factorization of the Bucky ball, use speye, the sparse identity matrix, to insert -3s on the diagonal of B.

B = B - 3*speye(size(B));

% Since each row sum is now zero, this new B is actually singular, but it is still instructive to compute its LU factorization. When called with only one output argument, lu returns the two triangular factors, L and U, in a single sparse matrix. The number of nonzeros in that matrix is a measure of the time and storage required to solve linear systems involving B.
% Here are the nonzero counts for the three permutations being considered.
% lu(B) (Original): 1022
% lu(B(r,r)) (Reverse Cuthill-McKee): 968
% lu(B(m,m)) (Approximate minimum degree): 636
% Even though this is a small example, the results are typical. The original numbering scheme leads to the most fill-in. The fill-in for the reverse Cuthill-McKee ordering is concentrated within the band, but it is almost as extensive as the first two orderings. For the approximate minimum degree ordering, the relatively large blocks of zeros are preserved during the elimination and the amount of fill-in is significantly less than that generated by the other orderings.
%
% The spy plots below reflect the characteristics of each reordering.

figure
subplot(1,3,1)
spy(lu(B))
title('Original')

subplot(1,3,2)
spy(lu(B(r,r)))
title('Reverse Cuthill-McKee')

subplot(1,3,3)
spy(lu(B(m,m)))
title('Min Degree')

% Copyright 2012 The MathWorks, Inc.