4
$\begingroup$

I have a similarity matrix which is symmetric and sparse. How can I parallelize the computation of the eigenvalues of this matrix in MATLAB?

$\endgroup$
  • $\begingroup$ Do you have access to Parallel Computing Toolbox? Otherwise, you can code in Fortran using LAPACK (or whichever library you prefer) and link it to MATLAB using MEX. $\endgroup$ – Inquest Apr 26 '12 at 10:52
  • $\begingroup$ Thanks to Nunixic! I don't know Fortran. I know Parallel Computing Toolbox, but I have no experience . I know the function eig to compute eigenvalues in MATLAB, but I don't know the way to use parallelism for this, or I have to code for computation eigenvalues myself and then parallel it. If you know, please give me some guides. Thanks! $\endgroup$ – HongTu Apr 26 '12 at 11:09
  • $\begingroup$ Hi HongTu. Welcome to SciComp :) I'm curious... are you looking to implement the computation of eigenvalues yourself, or are you looking for a MATLAB routine that already computes them in parallel? Also, do you need all the eigenvalues, or just one in particular (e.g. spectral radius)? $\endgroup$ – Paul Apr 26 '12 at 13:44
  • $\begingroup$ Hi Paul, thanks for your consideration for my problem. I'm really trying to code it myself. But I also look for the already parallelism for this because I haven't more time for my project at university. I don't need all the eigenvalues, just some largest or smallest eigenvalues. I have a similarity matrix of image, so this matrix is very large. So I think parallelism for the computation will get better performance. But I'm new in parallel computation. So I really need some guides. Thanks! $\endgroup$ – HongTu Apr 26 '12 at 14:53
  • $\begingroup$ I haven't worked on MATLAB's PCT much but MATLAB"s newsletter and this article at OSC could be good starting points. Seems like what you need is overloaded functions on codistributed arrays. How do you access the matrix? If you have the MATRIX explicitly available (or you read from file or whatever), writing a parallel eigen solver is sell than 20 lines in FORTRAN when linked to an LAPACK. $\endgroup$ – Inquest Apr 26 '12 at 16:39
5
$\begingroup$

MathWorks doesn't think this is a good idea. Their basic defense for not multithreading eigs is that the MATLAB sparse matrix-vector products will not significantly benefit from multithreading. I recommend that you look into some of the libraries discussed in another answer on scicomp if you are interested in computing eigenvalues more efficiently.

$\endgroup$
  • $\begingroup$ Hi Aron Ahmadia, thanks for your recommendation. This report is quite sufficient and useful which I don’t know before. I didn’t think there are many available libraries such that. $\endgroup$ – HongTu May 3 '12 at 17:19
  • $\begingroup$ I also see that the function eigs doesn't work well with parallelism. I don't know why time of parallel eigs is more than normal eigs? $\endgroup$ – HongTu May 3 '12 at 17:29
2
$\begingroup$

If you only need the largest and smallest eigenvalues, you can use the power and inverse power methods, respectively.

The power method requires a matrix-vector product at every iteration, which can be executed in parallel. If you are using a distributed computer, you can explicity allocate the vector and a certain number of rows of the matrix to each processor and calculate a portion of the resulting vector (this is called row-wise decomposition). These partial results can be combined into a single result using an all-gather operation. Alternatively, if you are using a symmetric computer, Matlab's Parallel Computing Toolbox has a parallel-for loop operation which can allow you do do this wihout altering your sequential code too much.

The inverse method requires a linear system of equations to be solved. Again, you can implement virtually any linear system solver method that you want in parallel. If you choose to use the conjugate gradient method, it too requires a matrix-vector product at every iteration, which can be executed in parallel using Matlab's PCT's parallel for-loop operation.

$\endgroup$
  • $\begingroup$ Hi Paul, thanks for your suggestion. But the Power or Inverse power method just used to find only one largest or smallest eigenvalue and correlative eigenvector, while I need some top eigenvalues and correlative eigenvectors in smallest or largest order. However, I see the Simultaneous Iteration method can find some pairs of eigenvalues and eigenvectors. It also applies the Power method with many initial vectors simultaneously. Is that right for my case? Please give me your comments. $\endgroup$ – HongTu May 3 '12 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.