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

$\endgroup$
3
  • $\begingroup$ Look at black box linear algebra. $\endgroup$ 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
    Aug 2, 2011 at 11:19
  • $\begingroup$ Actually since you're doing PCA, why not try the NIPALS algorithm first? $\endgroup$
    – Gilead
    Aug 2, 2011 at 11:22

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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