Bagaimana Multigrid yang dipercepat Krylov (menggunakan MG sebagai prasyarat) termotivasi?

Multigrid (MG) dapat digunakan untuk menyelesaikan sistem linier dengan membuat tebakan awal dan mengulangi yang berikut untuk sampai konvergensi: $Ax=b$ $x_0$ $i=0,1..$

Hitung sisa $r_i = b-Ax_i$
Terapkan siklus multigrid untuk mendapatkan aproksimasi , di mana . $\Delta x_i \approx e_i$ $Ae_i = r_i$
Perbarui $x_{i+1} \gets x_i + \Delta x_i$

Siklus multigrid adalah beberapa urutan smoothing, interpolasi, restriksi, dan operasi penyelesaian grid kasar yang diterapkan pada untuk menghasilkan . Ini biasanya siklus-V atau siklus-W. Ini adalah operasi linier jadi kami menulis . $r_i$ $\Delta x_i$ $\Delta x_i = B r_i$

Orang dapat menafsirkan proses ini sebagai iterasi Richardson yang telah dikondisikan. Artinya, kami memperbarui . $x_{i+1} \gets x_i + B r_i$

Iterasi Richardson adalah metode ruang bagian Krylov prototipe, yang menyarankan penggunaan siklus multigrid untuk mengkondisikan metode ruang bagian Krylov lainnya. Ini kadang-kadang disebut "akselerasi" multigrid dengan metode Krylov, atau secara bergantian dapat dilihat sebagai pilihan prekondisi untuk metode Krylov.

Cara lain untuk memperluas algoritma di atas adalah menggunakan Full Multigrid (FMG). Lihat jawaban ini untuk deskripsi singkat.

Dalam situasi apa MG dipercepat Krylov lebih disukai daripada MG atau FMG?

linear-algebra linear-solver multigrid krylov-method Patrick Sanan
sumber

(F) MG cukup sensitif, jika satu mode tidak teredam dengan baik oleh koreksi halus atau dua tingkat, semuanya hang. Metode Krylov dapat membantu meredam mode bermasalah ini. Jadi itu terutama dimotivasi oleh ketahanan sejauh yang saya mengerti.

chris

Jawaban:

$b-Ax$

Namun, dalam banyak kasus praktis, metode multigrid yang optimal atau efektif tidak digunakan. Ini mungkin karena

metode seperti itu tidak diketahui atau tidak tersedia untuk masalah yang diberikan
smoothers dan operator intergrid tidak cukup untuk memberikan konvergensi buku teks
pemecah kisi kasar tidak eksak

$BA$

Perhatikan bahwa pilihan untuk menggunakan metode suboptimal mungkin menghasilkan siklus multigrid yang jauh "lebih murah", sampai pada titik di mana akselerasi Krylov terbayar. Artinya, mungkin ada masalah (dan sistem komputasi) di mana MG yang dipercepat Krylov dapat mengungguli MG. Saya akan tertarik untuk menemukan contoh nyata dari ini.

(Terima kasih kepada @chris di atas dan Matt Knepley yang menyebutkan beberapa hal di atas dalam tutorial)

Patrick Sanan
sumber