Panduan apa yang harus saya ikuti ketika memilih pemecah sistem linier yang jarang?

Sistem linear yang jarang muncul dengan meningkatnya frekuensi dalam aplikasi. Seseorang memiliki banyak rutinitas untuk dipilih untuk menyelesaikan sistem ini. Pada level tertinggi, ada batas antara metode langsung (mis. Eliminasi Gaussian yang jarang atau dekomposisi Cholesky, dengan algoritma pemesanan khusus, dan metode multirontal) dan iteratif (misalnya metode GMRES, (bi-) konjugat gradien).

Bagaimana cara menentukan apakah akan menggunakan metode langsung atau berulang? Setelah membuat pilihan itu, bagaimana cara memilih algoritma tertentu? Saya sudah tahu tentang eksploitasi simetri (misalnya menggunakan gradien konjugat untuk sistem definitif positif simetris jarang), tetapi apakah ada pertimbangan lain seperti ini yang harus dipertimbangkan dalam memilih metode?

Yang penting ketika memilih pemecah iteratif adalah spektrum operator, lihat makalah ini . Namun, ada begitu banyak hasil negatif, lihat makalah ini di mana tidak ada pemecah iteratif menang untuk semua masalah dan makalah ini di mana mereka membuktikan mereka bisa mendapatkan kurva konvergensi untuk GMRES untuk spektrum apa pun. Dengan demikian, tampaknya tidak mungkin untuk memprediksi perilaku pemecah iteratif kecuali dalam beberapa kasus yang terisolasi, Oleh karena itu, pilihan terbaik Anda adalah mencoba semuanya, menggunakan sistem seperti PETSc , yang juga memiliki pemecah langsung.

Pilihan antara metode langsung dan berulang tergantung pada tujuan dan masalah yang dihadapi.

Untuk metode langsung, kami dapat mencatat:

• The matriks koefisien dari sistem linear perubahan selama perhitungan dan mungkin untuk sistem jarang persyaratan pembuangan memori dan usaha peningkatan kerja karena mengisi-in
• Harus lengkap untuk memberikan hasil yang bermanfaat
• Factorisasi dapat digunakan kembali dalam langkah-langkah selanjutnya jika terdapat banyak sisi kanan
• Dapat digunakan untuk menyelesaikan sistem linier saja.
• Jarang gagal.

Untuk metode berulang, kita dapat mencatat:

• Tujuannya adalah untuk memberikan hasil parsial hanya setelah sejumlah kecil iterasi.
• Upaya penyelesaian harus kurang dari metode langsung untuk masalah yang sama.
• Ekonomis berkenaan dengan penyimpanan (tanpa isi)
• Seringkali mudah diprogram.
• Solusi perkiraan yang diketahui dapat dieksploitasi.
• Terkadang mereka cepat dan terkadang tidak (kadang-kadang bahkan berbeda).
• Untuk masalah yang kompleks, metode berulang jauh kurang kuat dibandingkan dengan metode langsung.

Pedoman kapan harus menggunakan metode langsung atau berulang?

• Metode berulang ketika matriks koefisien jarang dan metode langsung tidak dapat mengeksploitasi sparsity secara efisien (hindari membuat fill-in).
• Metode langsung untuk banyak sisi kanan.
• Metode berulang dapat lebih efisien jika akurasi kurang diperhatikan
• Metode berulang untuk sistem persamaan nonlinier.

Saya sepenuhnya setuju dengan jawaban yang sudah diberikan. Saya ingin menambahkan bahwa semua metode berulang membutuhkan semacam tebakan awal. Kualitas tebakan awal ini seringkali dapat memengaruhi laju konvergensi metode yang Anda pilih. Metode seperti Jacobi, Gauss Seidel, dan Successive Over Relaxation semuanya bekerja untuk "menghaluskan" sebanyak mungkin kesalahan di setiap langkah ( lihat makalah ini untuk detailnya)). Beberapa langkah pertama mengurangi kesalahan frekuensi tinggi agak cepat, tetapi kesalahan frekuensi rendah membutuhkan lebih banyak iterasi untuk menghaluskan. Inilah yang membuat konvergensi lambat untuk metode ini. Dalam kasus seperti ini, kita dapat mempercepat konvergensi dengan menyelesaikan kesalahan frekuensi rendah (misalnya menyelesaikan masalah yang sama pada mesh kasar) terlebih dahulu, kemudian memecahkan kesalahan frekuensi yang lebih tinggi (misalnya pada mesh yang lebih halus). Jika kita menerapkan konsep ini secara rekursif dengan membagi dan menaklukkan, kita mendapatkan apa yang disebut metode Multi-grid. Bahkan jika sistem linear tidak simetris, ada implementasi alternatif metode multi-grid untuk sistem matriks jarang nonsingular (misalnya metode multi-grid aljabar) yang dapat mempercepat konvergensi solver. Skalabilitas mereka pada sistem paralel, bagaimanapun, adalah subjek dari banyak penelitian.

Ada bagian penting dari informasi yang hilang dalam pertanyaan Anda: dari mana asalnya. Struktur masalah yang Anda coba selesaikan memiliki potensi besar untuk menyarankan metode solusi.

Jika matriks Anda berasal dari persamaan diferensial parsial dengan koefisien halus, metode multigrid geometris akan sulit dikalahkan, khususnya dalam tiga dimensi. Jika masalah Anda kurang teratur, multigrid aljabar adalah metode yang baik. Keduanya biasanya dikombinasikan dengan metode ruang-Krylov. Pemecah yang efisien lainnya dapat diturunkan dari metode multipole cepat atau transformasi Fourier cepat.