computation time-eigen vectors multiplication

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

[John D'Errico]

You are computing a rank N-1 variation of a quasi pseudo-inverse? Not sure why. And why assume the first eigenvalue is always a specific one? That is a REALLY BAD idea, because eig does not insure the order of the eigenvalues.

[sharadhi]

As q here is the Laplacian matrix of a network, by considering only k= 2 to N, I was discarding the zero eigenvalue and corresponding vector.

Answer 1

[John D'Errico]

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

[sharadhi]

It does work well. My overall code only takes 17 minutes now. I can work on the other parts and get it to be lower hopefully. Thanks, John.