Page 501 - Applied Numerical Methods Using MATLAB

490 SPARSE MATRICES
>>flops(0), AsA = As*As; flops %in sparse forms
ans=50
>>flops(0), AfA = Af*Af; flops %in full(regular) forms
ans = 2000
>>b = ones(10,1); flops(0), x = As\b; flops
ans = 160
>>flops(0),x=Af\b; flops
ans = 592
>>flops(0), inv(As); flops
ans = 207
>>flops(0), inv(Af); flops
ans = 592
>>flops(0), [L,U,P] = lu(As); flops
ans=53
>>flops(0), [L,U,P] = lu(Af); flops
ans=92
Additionally, the MATLAB routine speye(n) is used to generate an n × n
identity matrix and the MATLAB routine spy(n) is used to visualize the sparsity
pattern. The computational efficiency of LU factorization can be upgraded if
one pre-orders the sparse matrix by the symmetric minimum degree permutation,
which is cast into the MATLAB routine symmmd().
Interest readers are welcome to run the following program “do_sparse”to
figure out the functions of several sparsity-related MATLAB routines.

%do_sparse
clear, clf
%create a sparse mxn random matrix
m=4;n=5;A1= sprandn(m,n,.2)
%create a sparse symmetric nxn random matrix with non-zero density nzd
nzd = 0.2; A2 = sprandsym(n,nzd)
%create a sparse symmetric random nxn matrix with condition number r
r = 0.1; A3 = sprandsym(n,nzd,r)
%a sparse symmetric random nxn matrix with the set of eigenvalues eigs
eigs = [0.1 0.2 .3 .4 .5]; A4=sprandsym(n,nzd,eigs)
eig(A4)
tic, A1A = A1*A1’, time_sparse = toc
A1f = full(A1); tic, A1Af = A1f*A1f’; time_full = toc
spy(A1A), full(A1A), A1Af
sparse(A1Af)
n = 10; A5 = sprandsym(n,nzd)
tic, [L,U,P] = lu(A5); time_lu = toc
tic, [L,U,P] = lu(full(A5)); time_full = toc
mdo = symmmd(A5); %symmetric minimum degree permutation
tic, [L,U,P] = lu(A5(mdo,mdo)); time_md=toc

(cf) The command ‘flops’ is not available in MATLAB of version 6.x and that is why we
use ‘tic’ and ‘toc’ to count the process time instead of the number of floating-point
operations.