Ich mache eine Lanczos-Diagonalisierung einer großen Matrix mit geringer Dichte (~ 2 Millionen Elemente). Fast alle Schritte im Lanzcos-Algorithmus werden parallel auf der GPU ausgeführt, mit Ausnahme der Diagonalisierung der Lanczos-Matrix, um die Konvergenz zu überprüfen. Dafür habe ich den TQLI-Algorithmus von Numerical Recipes verwendet. Gibt es Methoden, um das Eigensystem einer tridiagonalen Matrix zu finden, die parallel oder leicht parallelisierbar sind? Gibt es eine parallele Version von TQLI?
linear-algebra
algorithms
eigensystem
Zitronen
quelle
quelle
TQL kann nicht parallelisiert werden.
Der Standard-Parallelalgorithmus ist der von Cuppen:
JJM Cuppen, Eine Divide and Conquer-Methode für das symmetrische tridiagonale Eigenproblem, 1980.
http://www.springerlink.com/content/t21365q2gh702714/
siehe auch:
F. Tisseur, Ein paralleler Divide and Conquer-Algorithmus für das symmetrische Eigenwertproblem auf verteilten Speicherarchitekturen, 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
quelle
Ich empfehle die Verwendung von Parallel Multiple Relativ Robust Representations (PMRRR) für die parallele tridiagonale Eigenlösung. Es kann alle Eigenpaare der tridiagonalen Matrix in parallel berechnen . Eine Übersicht über die Methode finden Sie hier . Es besteht auch die Umsetzung in Scalapack, die diskutiert wird hier .O(n2)
quelle