Algorytm równoległy dla eigensystem matrycy tridiagonalnej

Robię diagonalizację Lanczosa dużej rzadkiej macierzy (~ 2 miliony elementów). Prawie wszystkie kroki w algorytmie Lanzcosa są wykonywane równolegle na GPU, z wyjątkiem diagonalizacji macierzy Lanczosa w celu sprawdzenia zbieżności. W tym celu korzystałem z algorytmu TQLI z receptur numerycznych. Czy istnieją metody znalezienia układu macierzystego macierzy tridiagonalnej, które są równoległe lub łatwo równoległe? Czy istnieje równoległa wersja TQLI?

Sugeruję użycie biblioteki takiej jak SLEPc , która zawiera interfejsy do wielu różnych metod rozwiązywania systemów eigens w trybie szeregowym lub równoległym. Instrukcja użytkownika zawiera odniesienia do kilku różnych metod rozwiązywania problemów z wartością własną.

TQL nie może być zrównoleglony.

Standardowy algorytm równoległy to Cuppen:

JJM Cuppen, Metoda dziel i zwyciężaj dla symetrycznego trójwymiarowego problemu własnego, 1980.
http://www.springerlink.com/content/t21365q2gh702714/

Zobacz też:

F. Tisseur, Równoległy algorytm dzielenia i zdobywania dla symetrycznego problemu wartości własnych w architekturach pamięci rozproszonej, 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

$O(n^2)$