Clustered matrix approximations: Test 2

Symmetric matrix A, with dense non-diagonal block structure

Contents

Load data

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

Recursive clustering with GRACLUS

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

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

% 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.042;
[msk,nnzBlFr,totFrc] = determineDenseBlocks(A,prtc,prtc,threshold);
clf
spy(msk)
nDenseBlocks = nnz(msk);

Plot non-zero fractions 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  :    96.68 % 
Relative error in a dense block approx.:    18.23 % 

Compute clustered matrix approximatons

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

% Or use different ranks for different dense blocks
% K  = ...

% Compute approximations of dense blocks of a symmetric matrix
[V,DD] = clustEigsExt(A,prtc,K,'eigs');

% if laneig (and lansvd) are available and prefered
%[V,D] = clustEigsExt(A,prtc,k,'laneig');

Compute relative error in % of clustered matrix approximation

nA  = norm(A,'fro');
relerrCmapp = sqrt( nA^2 - norm(DD,'fro')^2 )/nA*100;

% Compute memory consumption
memCmapp = memUsageCmapp(V,DD,[],'sym');

% Get rank k for a regular matrix approximation with = or > memory usage
m = size(A,1);
[memRmapp,kreg] = memUsageRmapp(m,[],memCmapp,'sym');

[Vr,Dr] = eigs(A,kreg);
relerrRmapp = sqrt( nA^2 - norm(Dr,'fro')^2 )/nA*100;

% fpns = floating point numbers
disp('-------------------------------------------------------------------')
fprintf('Clustered matrix approximation: relErr    = %10.2f %% \n', relerrCmapp)
fprintf('Regular   matrix approximation: relErr    = %10.2f %% \n', relerrRmapp)
disp('-------------------------------------------------------------------')
fprintf('Clustered matrix approximation: memUsage  = %10.0f fpns \n', memCmapp)
fprintf('Regular   matrix approximation: memUsage  = %10.0f fpns \n', memRmapp)
disp('-------------------------------------------------------------------')

-------------------------------------------------------------------
Clustered matrix approximation: relErr    =      55.27 % 
Regular   matrix approximation: relErr    =      80.32 % 
-------------------------------------------------------------------
Clustered matrix approximation: memUsage  =     970510 fpns 
Regular   matrix approximation: memUsage  =    1002474 fpns 
-------------------------------------------------------------------

Published with MATLAB® R2014b