Cara tercepat untuk menemukan pasangan eigen dari matriks nonsimetrik kecil pada GPU dalam memori bersama

Saya memiliki masalah di mana saya harus menemukan semua positif (seperti dalam nilai eigen positif) pasang eigen dari matriks nonsimetrik kecil (biasanya lebih kecil dari 60x60). Saya bisa berhenti menghitung ketika nilai eigen lebih kecil dari ambang tertentu. Saya tahu bahwa nilai eigennya nyata. Adakah saran tentang algoritma yang dapat saya gunakan untuk mencoba memeras kinerja terbaik? Saya harus melakukan beberapa ribu dekomposisi ini, jadi kecepatan itu penting.

Terima kasih sebelumnya.

EDIT: Saya perlu melakukan ini pada GPU dalam memori bersama. Matriks juga tidak harus berukuran sama. Saya tidak mengetahui ada perpustakaan yang melakukan ini saat ini. Saran algoritma yang cocok untuk masalah akan dihargai.

performance eigensystem gpu Kantoku
sumber

Jika saya benar, Anda memiliki kernel CUDA yang menghitung ribuan matriks kecil dalam memori bersama, dan Anda tidak mau menyalinnya ke memori global. Sebelum mencoba memberikan jawaban, ada beberapa hal yang perlu diklarifikasi. Dalam CUDA memori berbagi pakai terikat untuk memblokir masa pakai: berapa banyak utas yang Anda miliki untuk setiap matriks terurai? Apakah kinerja ekstrem benar-benar penting? (Bagaimana perkiraan waktu ekstraksi nilai eigen dibandingkan dengan waktu pembuatan matriks?) Berdasarkan argumen apa Anda tahu bahwa sistem eigens itu nyata? Bisakah sistem eigens rusak?

Stefano M

Halo Stefano dan terima kasih atas komentar Anda. Untuk saat ini, saya akan memiliki kelipatan terdekat dari ukuran lungsin dengan dimensi matriks yang ingin saya dekomposisi. Waktu pembuatan matriks sangat bervariasi, dan ada kasus di mana waktu pembuatan matriks lebih mahal, tetapi ada banyak situasi di mana waktu pembuatan matriks kurang dari dekomposisi. Saya tahu nilai eigen adalah nyata karena cara matriks dihasilkan. Saya lebih suka tidak masuk ke detail di sini, karena itu akan mengurangi pertanyaan awal. Akhirnya, ya, sistem bisa rusak.

Kantoku

Jawaban:

Tanpa melakukan banyak pencarian, saya sarankan Anda untuk melihat perpustakaan MAGMA . Kode tersedia secara bebas dengan dukungan terus menerus. NVIDIA mengakui MAGMA sebagai "Terobosan dalam Solver untuk Masalah Nilai Eigen".

Ada juga perpustakaan CULA , yang umumnya merupakan produk komersial, meskipun baru-baru ini telah dibuat gratis untuk penggunaan akademis (lihat detailnya di sini ).

Alexander
sumber

Terima kasih atas balasan Anda Alexander. Saya telah melihat kedua perpustakaan sebelumnya, dan sejauh yang saya tahu, fungsinya dipanggil dari host dan memori harus dalam memori global. Saya percaya overhead akan terlalu banyak untuk membenarkan penggunaannya. Semua matriks ini dihasilkan dalam memori bersama, digunakan dalam kernel dan kemudian dibuang. Saya ingin menyimpannya di sana tanpa harus mengembalikannya ke memori global. Bahkan jika saya mendorongnya ke sana, masih akan ada masalah memanggil banyak fungsi kernel dari host (meskipun dalam beberapa aliran).

Kantoku

@ Kanoku, ya, perpustakaan itu lebih umum dan mereka menyimpan seluruh matriks dalam memori global. Jika matriks Anda ada dalam memori bersama, hanya satu SM yang dapat mengerjakannya, bukan? Implementasi EVD dengan demikian harus cukup mudah.

Alexander

Ya saya akan membayangkan begitu, itulah sebabnya saya mencari algoritma yang cocok untuk situasi ini. Saya tidak terlalu terbiasa dengan non simetris evd, jadi saya mencari saran.

Kantoku

@Antoku (dan Alexander). EVD nonsimetris jauh dari mudah, bahkan dalam kasus berurutan. Ini masih merupakan area penelitian aktif.

Jack Poulson

@JackPoulson Ah ya, Anda benar, tapi saya (dan saya berasumsi Alexander juga) berarti bahwa akan mudah untuk menerapkan algoritma yang mapan pada masalah, mengingat ada banyak penyederhanaan yang dapat dilakukan ketika kita mengambil ukuran dan sifat dari matriks menjadi pertimbangan. Masalahnya adalah: algoritma mana.

Kantoku

Gunakan fungsi di LAPACK, tidak mungkin Anda bisa mengalahkan mereka dalam implementasi Anda sendiri.

Wolfgang Bangerth
sumber

Hai Wolfgang. Terima kasih atas jawabannya, tetapi saya bermaksud untuk mengimplementasikan ini pada GPU menggunakan CUDA dan untuk beberapa ribu matriks kecil ini (di mana setiap blok menangani dekomposisi dari satu matriks tunggal), dan matriks tidak selalu memiliki ukuran yang sama, jadi mengimplementasikan sesuatu sendiri yang menggunakan memori bersama tampaknya menjadi satu-satunya pilihan saya. Adakah yang tahu algoritma apa yang paling cocok untuk jenis matriks ini? PS Terima kasih atas kesepakatannya. Kuliah II yang Anda berikan di KAUST semester lalu. Saya menikmatinya :)

Kantoku

@ Kanoku Anda harus menambahkan detail ini dalam pertanyaan Anda, jika tidak maka akan menyesatkan.

Alexander

@Alexander Saya telah memperbarui pertanyaan dengan lebih detail. Terima kasih untuk sarannya!

Kantoku

@ Kanoku: GPU sedikit di luar wilayah saya, tetapi saya yakin sudah ada perpustakaan di luar sana yang melakukan apa yang Anda inginkan (dan sebenarnya saya melihat bahwa jawaban lain sudah terhubung ke mereka). Senang mendengar Anda menyukai kelas saya!

Wolfgang Bangerth