MATLAB: Computation time-eigen vectors multiplication

Question

Hello,

I've written a simple for loop to compute the Q matrix shown in the formula attached. For every k(from k=2 to k=N), we multiply the eigen vector z_k with its transpose z_k^T and divide the result by the correspding eigen value mu_k. Here, N is the number of nodes in the network and q is a NxN symmetric matrix.

[x,y]        =size(q);
N            =x;
[V,W]        =eig(q);
Q      =zeros(N);
for i=2:1:N;Q=Q+(((V(:,i))*(V(:,i).'))/(W(i,i)));end

It works fine for small networks(takes roughly 20 secs for N=1200). However, I intend on using it for networks with as many as N=12000 nodes. This seems to take forever.

I'm using R2018a. My license does not include the parallel computing toolbox so I cannot use the parfor function. Is there any other way I can reduce the computation time? Perhaps to a few minutes?

Thank you

Kind Regards,

Sharadhi

Answer 1

Well, disregarding my questions about why in the name of god and little green apples you want to do this, the trivial answer is to use linear algebra.

[x,y] =size(q);
N =x;
[V,W] =eig(q);
w = diag(W);
Q = V(:,2:end)*diag(1./w(2:end))*V(:,2:end).';

We should be able to do it a little faster for large arrays, if you create a sparse diagonal matrix from w. That makes the matrix multiply more efficient.

q = rand(1200,1200); q = q + q';
[V,W] = eig(q);
tic
w = diag(W);
Q = V(:,2:end)*diag(1./w(2:end))*V(:,2:end).';
toc
Elapsed time is 0.204658 seconds.

So instead of 20 seconds, only .2 seconds.

tic
w = diag(W);
Q = V(:,2:end)*spdiags(1./w(2:end),0,N-1,N-1)*V(:,2:end).';
toc
Elapsed time is 0.150572 seconds.

So slightly faster for this relatively small matrix. But when N is much larger, we gain much more, because now those matrix multiplies take a significant amount of time.

N = 12000;
q = rand(N,N); q = q + q';
[V,W] = eig(q);
w = diag(W);
tic
Q = V(:,2:end)*diag(1./w(2:end))*V(:,2:end).';
toc
tic
Q = V(:,2:end)*spdiags(1./w(2:end),0,N-1,N-1)*V(:,2:end).';
toc