11
$\begingroup$

I'm doing a Lanczos diagonalization of a large sparse matrix (~2 million elements). Almost all of the steps in the Lanzcos algorithm are done in parallel on the GPU, except for diagonalizing the Lanczos matrix to check for convergence. For that, I've been using the TQLI algorithm from Numerical Recipes. Are there methods for finding the eigensystem of a tridiagonal matrix that are parallel or easily parallelizable? Does a parallel version of TQLI exist?

$\endgroup$
4
$\begingroup$

I suggest using a library like SLEPc, which includes interfaces to many different methods for solving eigensystems in serial or parallel. The user manual includes references to several different methods for solving eigenvalue problems.

$\endgroup$
  • $\begingroup$ Actually, no existing sparse eigensolvers use parallel linear algebra for the Rayleigh quotient. I wrote such an eigensolver this summer, but it is unfortunately closed source. $\endgroup$ – Jack Poulson Aug 12 '12 at 21:22
9
$\begingroup$

TQL cannot be parallelized.

The standard parallel algorithm is that of Cuppen:

JJM Cuppen, A divide and conquer method for the symmetric tridiagonal eigenproblem, 1980.
http://www.springerlink.com/content/t21365q2gh702714/

see also:

F. Tisseur, A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures, 1999
http://eprints.ma.man.ac.uk/981/01/covered/MIMS_ep2007_225.pdf

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.4109&rep=rep1&type=pdf

http://www14.in.tum.de/konferenzen/Jass09/courses/2/Kleine_Albers_paper.pdf

$\endgroup$
  • $\begingroup$ The Arvo link is very sadly broken now. :( $\endgroup$ – Geoffrey Irving Aug 12 '12 at 6:14
  • $\begingroup$ @GeoffreyIrving: I replaced it by a working one, though it may not be free for everyone. And I added a new reference to a paper by Tisseur. $\endgroup$ – Arnold Neumaier Aug 12 '12 at 11:28
3
$\begingroup$

I recommend using Parallel Multiple Relatively Robust Representations (PMRRR) for the parallel tridiagonal eigensolve. It can compute all of the eigenpairs of the tridiagonal matrix in $O(n^2)$ work in parallel. You can find an overview of the method here. There is also the implementation in ScaLAPACK, which is discussed here.

$\endgroup$

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.