Algoritmo paralelo para sistema próprio de uma matriz tridiagonal

11

Estou fazendo uma diagonalização de Lanczos de uma grande matriz esparsa (~ 2 milhões de elementos). Quase todas as etapas do algoritmo Lanzcos são realizadas em paralelo na GPU, exceto na diagonalização da matriz de Lanczos para verificar a convergência. Para isso, tenho usado o algoritmo TQLI da Numerical Recipes. Existem métodos para encontrar o sistema próprio de uma matriz tridiagonal que seja paralela ou facilmente paralelizável? Existe uma versão paralela do TQLI?

linear-algebra algorithms eigensystem limas
fonte

Respostas:

4

Sugiro o uso de uma biblioteca como o SLEPc , que inclui interfaces para muitos métodos diferentes para resolver sistemas auto-gerados em série ou em paralelo. O manual do usuário inclui referências a vários métodos diferentes para resolver problemas de autovalor.

Geoff Oxberry
fonte
Na verdade, nenhum solvente autônomo esparso existente usa álgebra linear paralela para o quociente de Rayleigh. Eu escrevi um eigensolver nesse verão, mas infelizmente é um código fechado.
Jack Poulson
9

TQL não pode ser paralelo.

O algoritmo paralelo padrão é o de Cuppen:

JJM Cuppen, Um método de dividir e conquistar para o problema de eigen tridiagonal simétrico, 1980.
http://www.springerlink.com/content/t21365q2gh702714/

Veja também:

F. Tisseur, Um algoritmo de divisão e conquista paralelo para o problema de autovalor simétrico em arquiteturas de memória distribuída, 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

Arnold Neumaier
fonte
Infelizmente, o link do Arvo está quebrado agora. :(
Geoffrey Irving
@ GeoffreyIrving: substituí-o por um que funcione, embora possa não ser gratuito para todos. E adicionei uma nova referência a um artigo do Tisseur.
Arnold Neumaier 12/08/2012
3

O(n2)

Jack Poulson
fonte