Bagaimana seseorang dapat memparalelkan metode multigrid untuk menyelesaikan sistem persamaan linear?

Seperti yang saya pahami, metode multigrid memecahkan sistem linier dengan menyelesaikan versi yang lebih kasar dari masalah yang sama (di sana dengan menghilangkan kesalahan frekuensi rendah) kemudian memproyeksikan kembali ke jaringan halus untuk meluruskan kesalahan frekuensi tinggi. Untuk sistem yang besar, saya dapat melihat bagaimana metode berulang dapat diimplementasikan secara paralel di setiap tingkat jaringan. Apakah skala pendekatan ini baik secara paralel? Apakah ada sumber konkurensi lain dalam algoritma yang dapat dieksploitasi secara paralel?

Multigrid geometris paralel mudah diterapkan pada grid terstruktur. Aljabar dan multigrid yang tidak terstruktur lebih teknis, lihat jawaban ini untuk tautan ke implementasi.

Dalam metode multiplikatif (mis. Sepeda- ), hanya satu level yang dapat dihitung pada satu waktu. Karena jumlah level adalah mana adalah jumlah derajat kebebasan dan adalah faktor kasar (biasanya sekitar atau dalam dimensi ), istilah logaritmik ini tidak dapat dilepas. Metode aditif mengorbankan beberapa faktor konstan, tetapi dapat menghitung semua tingkatan secara bersamaan, sehingga mengurangi faktor logaritmik ke . Saya belum melihat demonstrasi pada perangkat keras nyata di mana peningkatan konkurensi membenarkan konstanta yang lebih buruk dan mengurangi kekokohan metode aditif.$V$$\log_{c} N$$N$$c$$2^d$$3^d$$d$$\log_2 \log_c N$

Gauss-Seidel adalah pemintal yang sangat populer yang multiplikatif dan tampaknya tidak dapat diparalelkan secara efisien. Untuk diskritisasi sederhana pada grid terstruktur, dan ketika bandwidth memori tidak menjadi perhatian, solusi klasik Gauss-Seidel merah-hitam adalah wajar. Untuk masalah yang lebih kompleks dan pada perangkat keras modern, Adams (2001) menunjukkan algoritma yang jauh lebih efisien. Untuk banyak masalah, pendekatan sederhana menggunakan Gauss-Seidel independen pada setiap subdomain sepenuhnya memuaskan. Alternatif untuk Gauss-Seidel adalah menggunakan Jacobi teredam atau polinomial smoothers, lihat Adams, Brezina, Hu, dan Tuminaro (2003) untuk perbandingan. Model kinerja untuk smoothers ini mirip dengan perhitungan stensil lainnya, dan karenanya memiliki skalabilitas lemah optimal,$\mathcal O (N/P)$ untuk subdomain yang cukup besar untuk menutupi latensi.

Dalam praktiknya, grid kasar dengan cepat mencapai batas skalabilitas yang kuat (di luar itu menambahkan lebih banyak proses meningkatkan run-time), sehingga mereka harus berada pada komunikator MPI yang lebih kecil. Ini menambah sedikit kompleksitas pada implementasinya. Untuk masalah di mana level kasar memiliki terlalu banyak struktur untuk melanjutkan kasar, penyelesaian level kasar dapat menjadi hambatan.

Untuk menguji berbagai metode multigrid paralel, saya sarankan menggunakan perpustakaan seperti PETSc yang memungkinkan Anda untuk menjalankan banyak algoritma yang berbeda dengan kode pengguna yang sangat sedikit.