Algoritma paralel untuk sistem eigens dari matriks tridiagonal

11

Saya sedang melakukan diagonalisasi Lanczos dari matriks jarang besar (~ 2 juta elemen). Hampir semua langkah dalam algoritma Lanzcos dilakukan secara paralel pada GPU, kecuali untuk mendiagonalisasi matriks Lanczos untuk memeriksa konvergensi. Untuk itu, saya telah menggunakan algoritma TQLI dari Numerical Recipes. Apakah ada metode untuk menemukan sistem eigens dari matriks tridiagonal yang paralel atau mudah diparalelkan? Apakah ada versi paralel TQLI?

linear-algebra algorithms eigensystem jeruk nipis
sumber

Jawaban:

4

Saya sarankan menggunakan perpustakaan seperti SLEPc , yang mencakup antarmuka ke banyak metode berbeda untuk menyelesaikan sistem eigens secara serial atau paralel. The manual termasuk referensi untuk beberapa metode yang berbeda untuk memecahkan eigenvalue masalah.

Geoff Oxberry
sumber
Sebenarnya, tidak ada eigensolver jarang yang ada menggunakan aljabar linier paralel untuk hasil bagi Rayleigh. Saya menulis eigensolver seperti itu musim panas ini, tetapi sayangnya itu adalah sumber tertutup.
Jack Poulson
9

TQL tidak dapat diparalelkan.

Algoritma paralel standar adalah algoritma Cuppen:

JJM Cuppen, Metode membagi dan menaklukkan untuk masalah eigen simetris tridiagonal, 1980.
http://www.springerlink.com/content/t21365q2gh702714/

Lihat juga:

F. Tisseur, Algoritme pembagian dan penaklukan paralel untuk masalah nilai eigen simetris pada arsitektur memori terdistribusi, 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
sumber
Tautan Arvo sangat rusak sekarang. :(
Geoffrey Irving
@ GeoffreyIrving: Saya menggantinya dengan yang berfungsi, meskipun mungkin tidak gratis untuk semua orang. Dan saya menambahkan referensi baru ke kertas oleh Tisseur.
Arnold Neumaier
3

HAI(n2)

Jack Poulson
sumber