Implementasi algoritma tridiagonal matrix yang efisien

12

Saya memecahkan masalah fisik menggunakan skema numerik implisit. Ini menuntun saya untuk memecahkan persamaan linear dengan matriks tridiagonal. Saya telah memberi kode algoritma ini dari Wikipedia. Saya ingin tahu apakah ada perpustakaan yang efisien yang memungkinkan untuk menyelesaikan persamaan jenis ini dengan cara yang dioptimalkan. Catatan penting adalah bahwa matriks itu sendiri berubah hanya ketika parameter sistem berubah, jadi saya memiliki kesempatan untuk menghitung ulang beberapa langkah algoritma untuk bonus kinerja yang bagus. Saya menggunakan C ++.

linear-algebra libraries c++ gmk
sumber
Seberapa besar sistem itu, apakah perlu paralel?
aterrel
1
Ukuran tergantung pada akurasi yang diperlukan (dari ratusan hingga puluhan ribu nilai). Sekarang saya membuat kode pada komputer satu-inti, tetapi dimungkinkan untuk mendapatkan akses ke superkomputer universitas dengan banyak CPU yang tersedia, sehingga dukungan paralelisme akan lebih baik.
gmk

Jawaban:

15

Anda mungkin harus mulai dengan implementasi LAPACK,? Gtsv, mis., Dgtsv . Jika Anda ingin versi memori terdistribusi, maka Anda mungkin ingin memulai dengan p? Gtsv ScaLAPACK.

EDIT: Karena matriks Anda tidak sering berubah, Anda dapat menghindari memfaktorkan matriks tridiagonal secara berlebihan dengan memecah rutin LAPACK? Gtsv menjadi langkah faktorisasi,? Gttrf, dan tahap penyelesaian,? Gttrs. Demikian pula rutinitas bernama ada di ScaLAPACK yang melayani tujuan yang sama.

Jack Poulson
sumber
Terima kasih, sepertinya ini yang saya butuhkan. Saya akan mencoba sekarang untuk menjalankan rutinitas ini dari kode saya.
gmk
1
Karena Anda memanggilnya dari C ++, pastikan untuk mendeklarasikan prototipe di dalam blok "C" {extern} eksternal. Bergantung pada sistem Anda, Anda mungkin perlu menambahkan garis bawah pada nama rutin.
Jack Poulson
2

Untuk sistem paralel terdistribusi : Saya belum mencoba ScaLAPACK, yang memiliki pemecah tridiagonal paralel, yang tersedia contoh online . Saya telah mencoba dengan sukses beberapa metode yang diusulkan oleh David Moulton dalam publikasi LANL . Pengkodean ini mungkin lebih dari yang ingin Anda lakukan, tetapi dengan menggunakan LAPACK, ia lurus ke depan.

Yann
sumber
1

Saya menemukan algoritma rekursif yang menarik di sini di halaman 975. Kelihatannya menjanjikan, saya bertanya-tanya apa yang dikatakan orang yang lebih berpengalaman tentang hal itu.

tiam
sumber
Resep Numerik memiliki beberapa kesalahan di dalamnya. Dalam hal sumber kode untuk digunakan, ini bukan yang terbaik, meskipun beberapa menganggapnya klasik. Saya akan terkejut jika ScaLAPACK tidak mengimplementasikan algoritma setidaknya seefisien reduksi siklik rekursif.
Geoff Oxberry