Algoritmo paralelo para el sistema propio de una matriz tridiagonal

11

Estoy haciendo una diagonalización de Lanczos de una gran matriz dispersa (~ 2 millones de elementos). Casi todos los pasos del algoritmo de Lanzcos se realizan en paralelo en la GPU, excepto la diagonalización de la matriz de Lanczos para verificar la convergencia. Para eso, he estado usando el algoritmo TQLI de Numerical Recipes. ¿Existen métodos para encontrar el sistema propio de una matriz tridiagonal que sean paralelos o fácilmente paralelizables? ¿Existe una versión paralela de TQLI?

linear-algebra algorithms eigensystem limas
fuente

Respuestas:

4

Sugiero usar una biblioteca como SLEPc , que incluye interfaces para muchos métodos diferentes para resolver sistemas propios en serie o en paralelo. El manual del usuario incluye referencias a varios métodos diferentes para resolver problemas de valores propios.

Geoff Oxberry
fuente
En realidad, ninguna solución propia dispersa existente usa álgebra lineal paralela para el cociente de Rayleigh. Escribí un eigensolver este verano, pero lamentablemente es de código cerrado.
Jack Poulson
9

TQL no puede ser paralelo.

El algoritmo paralelo estándar es el de Cuppen:

JJM Cuppen, Un método de divide y vencerás para el problema propio tridiagonal simétrico, 1980.
http://www.springerlink.com/content/t21365q2gh702714/

ver también:

F. Tisseur, Un algoritmo paralelo de divide y vencerás para el problema simétrico del valor propio en arquitecturas de memoria distribuida, 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
fuente
El enlace Arvo está muy tristemente roto ahora. :(
Geoffrey Irving
@GeoffreyIrving: lo reemplacé por uno funcional, aunque puede que no sea gratis para todos. Y agregué una nueva referencia a un artículo de Tisseur.
Arnold Neumaier
3

O(n2)

Jack Poulson
fuente