computation time-eigen vectors multiplication

3 次查看（过去 30 天）
sharadhi
sharadhi 2018-9-24
评论： sharadhi 2018-9-24
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
  2 个评论
John D'Errico
John D'Errico 2018-9-24
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
sharadhi 2018-9-24
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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

John D'Errico
John D'Errico 2018-9-24
编辑：John D'Errico 2018-9-24
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
  1 个评论
sharadhi
sharadhi 2018-9-24
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.

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by