Various eigenvalue algorithms

Post here if you have a question about LAPACK performance

Various eigenvalue algorithms

Postby Mvpranav » Tue May 24, 2011 5:31 am

Hi

I'm trying to find all the eigenvalues of a collection of matrices, ranging from 2x2 to some very large matrices of sizes 8000x8000, all of them being Hermitian and real. Initially I tried the geev function without block-diagonalization, but that proved to be extremely slow for the larger matrices. Then I block diagonalized the matrices (largest blocks now being 3000x3000) and switched to the syev function (upper triangular version and without eigenvectors, to be specific). This sped things up, but it's still inching along for the larger matrices (above sizes 2000x2000).

Of course, I could go on experimenting with other functions like the divide-and-conquer algorithm, Hessenberg reduction, shifted-QR, SVD, Schur decomposition etc. but I'm hoping that somebody can recommend which algorithms might be most beneficial for my particular case: that would save me a lot of time and effort. I finally have to go up to matrices of sizes 65000x65000 (largest blocks here being 12870x12870). I'm using the Boost bindings to the LAPACK library.

Any suggestions would be appreciated.

Thanks,
Vipin
Mvpranav
 
Posts: 1
Joined: Tue May 24, 2011 5:09 am

Re: Various eigenvalue algorithms

Postby Julien Langou » Fri May 27, 2011 4:55 am

all of them being Hermitian and real


Hermitian + real = symmetric

Then I block diagonalized the matrices (largest blocks now being 3000x3000) and switched to the syev function (upper triangular version and without eigenvectors, to be specific). This sped things up, but it's still inching along for the larger matrices (above sizes 2000x2000).


You are essentially stucked ...
SYEV is the good subroutine to call when you are looking for eigenvalues only. The subroutine (1) take your dense input matrix A and reduce it to symmetric tridiagonal form (with an orthogonal similarity transformation), then (2) it computes all the eigenvalues of the symmetric tridiagonal matrix using the (symmetric tridiagonal) QR algorithm. Step (2) is O(n^2) and is extremely fast. You can forget about it. The bottleneck is step (1). It's O(n^3) and moreover it's slow (inherently).

There is some interesting developments going from the PLASMA side where they sped up step (1) on multicore machine with a new algorithm. I think the functionality DSYEV for computing eigenvalues only will be available shortly and the speedup will be dramatic. So stay tune on their release website. Or maybe send them an email. (Note: The process is still O(n^3) but is really faster.)

Julien.
Julien Langou
 
Posts: 735
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA

Re: Various eigenvalue algorithms

Postby haidar » Fri May 27, 2011 10:13 am

The next version of PLASMA will have Eigenvalue and SVD included, for computing only the eigenvalue and singular value (resp).
I would like to have a clarification about "matrices of sizes 65000x65000 (largest blocks here being 12870x12870)" .
So if you have independent block of size 12870, than you would call the DSYEV on each of those block independently, thus your matrix size is 12870.
In the next release (probably June, 7), the PLASMA_DSYEV is more than 10 times faster than the existing vendor eigenvalue solver.

Thanks
Azzam
haidar
 
Posts: 1
Joined: Fri May 27, 2011 10:01 am


Return to Performance

Who is online

Users browsing this forum: No registered users and 1 guest