Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Look at black box linear algebra. –  Steve Huntsman Aug 2 '11 at 10:30
2  
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. –  Gilead Aug 2 '11 at 11:19
    
Actually since you're doing PCA, why not try the NIPALS algorithm first? –  Gilead Aug 2 '11 at 11:22
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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