1
$\begingroup$

Hi all,

A project I'm currently working on requires me to compute the eigenvectors / eigenvalues of sparse symmetric integer matrices. This is needed in the context of Principal Component Analysis. I tried to look around for efficient algorithms but am not 100% sure where to start.

Ideally, I'd like to find the first 10 eigenvectors (e.g. corresponding to the 10 biggest eigen values) of a 10k x 10k matrix in less than 10 seconds.

Is that a crazy objective? What property of the matrices would you leverage? Integer + symmetric screams Smith Normal Form but I'm wondering if there exists better than that...

Any help appreciated! Thanks in advance,

Guillaume

Improve this question
$\endgroup$
3
  • $\begingroup$ Look at black box linear algebra. $\endgroup$
    – Steve Huntsman
    Commented Aug 2, 2011 at 10:30
  • 2
    $\begingroup$ Try the Lanczos algorithm (a power method like the NIPALS algorithm): en.wikipedia.org/wiki/Lanczos_algorithm. 10 eigenvectors in 10 seconds doesn't sound too difficult on modern day machines. $\endgroup$
    – Gilead
    Commented Aug 2, 2011 at 11:19
  • $\begingroup$ Actually since you're doing PCA, why not try the NIPALS algorithm first? $\endgroup$
    – Gilead
    Commented Aug 2, 2011 at 11:22

1 Answer 1

Reset to default
2
$\begingroup$

http://www.caam.rice.edu/software/ARPACK/ is the standard tool. It's Fortran (ouch), but there are libraries to call it from C++, Matlab, Python, and possibly also other languages that I do not know (I'd be surprised if there were no Java adapter around, for instance).

Don't write your restarted Arnoldi implementation from scratch if you have no previous experience in numerical analysis, it might be tricky.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .