Clustered matrix approximations: Test 7

Square non-symmetric matrix A

Contents

Load data

clear
% Load partial LiveJournal data
load('lj-partial61clGraclus-cl38')

% Extract largest connected componets
ind = lcc(A);
A = A(ind,ind);
m = size(A,1);

Make matrix symmetric

B = A+A';
[rr,cc,vv] = find(B);
vv = ones(size(vv));
B = sparse(rr,cc,vv,m,m);

Recursive clustering with GRACLUS

% specify max cluster size
maxClusterSize = 8000;
%[prt, ~] = recGraclus(B,maxClusterSize);

% load clustering result in order to suppress numerous graclus outputs for
% publishing purposes.
load test7var

% Reorder vertices
[ind,prtsz,prtc] = reorderVertices(prt);

% Visualize clustering structure of A
spy(A(ind,ind))

Determine and visualise location of dense blocks

threshold = 0.1;
[msk,nnzBlFr,totFrc] = determineDenseBlocks(A,prtc,prtc,threshold);
clf
spy(msk)
nDenseBlocks = nnz(msk);

Plot non-zero fraction in all blocks and threshold value

clf
semilogy(sort(nnzBlFr(:),'descend'))
hold on
semilogy(nDenseBlocks,threshold,'r-o','MarkerSize',10)
grid on
hold off

Plot sorted sizes of dense blocks

% sort and plot block sizes
ssz = sort(prtsz,'descend');
plot(ssz,'r-o')
title('Sorted block sizes')
grid on

Fraction of non-zeros within dense blocks

[nnzBlks, nnzBlFr] = compClustNnzRect(A,prtc,prtc);
bar3custom(nnzBlFr)
title(['Fraction of non-zeros in blocks A_{ij},  ', num2str(totFrc), ...
    ' % in dense blocks '])

% Relative error due to clustering: || A - A_dense || / || A ||
% where A_dense only contains non-zeros from dense blocks.
relerr = compClustRelErrExt(A,prtc,prtc,msk);
fprintf('Fraction of non-zeros in dense blocks  : %8.2f %% \n', totFrc)
fprintf('Relative error in a dense block approx.: %8.2f %% \n', relerr)

Fraction of non-zeros in dense blocks  :    98.28 % 
Relative error in a dense block approx.:    13.13 % 

Compute clustered matrix approximatons

% Specify rank k for approximations of dense blocks
k = 10;
K = ones(size(msk))*k.*msk;

% Compute approximations for diagonal blocks of a square non-sym matrix
[Uc1,Sc1,Vc1] = clustSvds(A,prtc,k,'svds');
SSc1 = compCoreNonsymFull(A,Uc1,Sc1,Vc1,prtc,'diag');

% Compute approximations for all dense blocks of a square non-sym matrix
[Uc2,Sc2,Vc2] = clustSvdsExt(A,K,prtc,'svds');
SSc2 = cell2mat(Sc2);

Compute relative errors in % of clustered matrix approximations

nA  = norm(A,'fro');
relerrCmapp1 = sqrt( nA^2 - norm(SSc1,'fro')^2 )/nA*100;
relerrCmapp2 = sqrt( nA^2 - norm(SSc2,'fro')^2 )/nA*100;

% Compute memory consumption
memCmapp1 = memUsageCmapp(Uc1,SSc1,Vc1,'non-sym');
memCmapp2 = memUsageCmapp(Uc2,SSc2,Vc2,'non-sym');

% Get rank k for a regular matrix approximation with the same memory usage
m = size(A,1);
[memRmapp1,kreg1] = memUsageRmapp(m,m,memCmapp1,'non-sym');
[memRmapp2,kreg2] = memUsageRmapp(m,m,memCmapp2,'non-sym');

[Ur1,Sr1,Vr1] = svds(A,kreg1);
[Ur2,Sr2,Vr2] = svds(A,kreg2);
relerrRmapp1 = sqrt( nA^2 - norm(Sr1,'fro')^2 )/nA*100;
relerrRmapp2 = sqrt( nA^2 - norm(Sr2,'fro')^2 )/nA*100;

% fpns = floating point numbers
disp('-------------------------------------------------------------------')
fprintf('Clustered matrix approximation: relErr   = %10.2f %% (diag) \n', relerrCmapp1)
fprintf('Regular   matrix approximation: relErr   = %10.2f %% \n', relerrRmapp1)
fprintf('Clustered matrix approximation: relErr   = %10.2f %% (non-diag) \n',relerrCmapp2)
fprintf('Regular   matrix approximation: relErr   = %10.2f %% \n', relerrRmapp2)
disp('-------------------------------------------------------------------')
fprintf('Clustered matrix approximation: memUsage = %10.0f fpns (diag) \n', memCmapp1)
fprintf('Regular   matrix approximation: memUsage = %10.0f fpns \n', memRmapp1)
fprintf('Clustered matrix approximation: memUsage = %10.0f fpns (non-diag) \n', memCmapp2)
fprintf('Regular   matrix approximation: memUsage = %10.0f fpns \n', memRmapp2)
disp('-------------------------------------------------------------------')

-------------------------------------------------------------------
Clustered matrix approximation: relErr   =      80.32 % (diag) 
Regular   matrix approximation: relErr   =      85.55 % 
Clustered matrix approximation: relErr   =      79.75 % (non-diag) 
Regular   matrix approximation: relErr   =      83.01 % 
-------------------------------------------------------------------
Clustered matrix approximation: memUsage =    1491100 fpns (diag) 
Regular   matrix approximation: memUsage =    1612061 fpns 
Clustered matrix approximation: memUsage =    3281060 fpns (non-diag) 
Regular   matrix approximation: memUsage =    3370673 fpns 
-------------------------------------------------------------------

Compute SVDs of all dense blocks

[UU,SS,VV] = clustSvdsExtCell(A,K,prtc,'svds');

% Plot singular values for dense blocks
noc = length(prtsz);

for i = 1:noc
    for j = 1:noc
        if K(i,j) > 0
           plot(diag(SS{i,j}),'-x');
           hold on
        end
    end
end
grid on
hold off

Published with MATLAB® R2014b