Apakah biasanya tidak ada pemeriksaan konvergensi di Multigrid?

12

Saya baru saja membaca Bab 3 dalam "A Multigrid Tutorial" oleh Briggs / Henson / McCormick, tautan .

Teksnya tentang siklus Multigrid seperti siklus-V, siklus-mu, FMG. Apa yang menarik perhatian saya: Dalam kebanyakan prosedur iteratif seseorang memeriksa apakah ia telah menyatu dengan toleransi / akurasi yang diinginkan dan jika demikian, prosedur itu berhenti. Tetapi Briggs / Henson / McCormick tidak menggunakan pengecekan konvergensi dalam skema yang disajikan. Jumlah iterasi dan rekursi hanya dikodekan dan orang harus percaya bahwa skema tersebut akan bertemu.

Jadi bagaimana ini dilakukan di Multigrid secara normal? Apakah biasanya jumlah iterasi / rekursi hanya dikodekan? Saya benar-benar takut bahwa saya akan membuang banyak waktu perhitungan karena saya terlalu tepat atau di sisi lain, akurasi akan buruk dalam banyak kasus ketika saya memilih jumlah iterasi / rekursi yang lebih rendah.

Michael
sumber
Kurangnya jawaban untuk pertanyaan ini benar-benar mengejutkan bagi saya. Tentunya ada beberapa pengguna yang sangat aktif di sini yang memiliki sedikit pengalaman multigrid dalam penelitian dan / atau lingkungan produksi?
Doug Lipinski
2
Saya pikir masalahnya adalah bahwa multigrid saat ini jarang digunakan sebagai solver dengan sendirinya (karena kurangnya teori konvergensi umum, saya percaya), tetapi lebih sebagai prekondisi untuk metode iteratif yang lebih mapan seperti CG atau GMRES. Dalam konteks ini, tidak ada pemeriksaan konvergensi untuk multigrid diperlukan, karena iterasi luar menanganinya.
Christian Clason

Jawaban:

4

Ya, itu normal untuk tidak memiliki pemeriksaan konvergensi di MG karena beberapa alasan. Pertama, jika Anda menggunakan jumlah iterasi yang berbeda pada setiap pass, maka operator MG tidak lagi linier, dan Anda harus menggunakan sesuatu seperti FGMRES sebagai akselerator yang dapat mengakomodasi preconditioner nonlinear. Kedua, FMG adalah pemecah yang tepat (mengurangi kesalahan di bawah kesalahan diskritisasi) ketika itu bekerja, jadi memeriksa konvergensi memperkenalkan sinkronisasi yang mahal ke dalam algoritma. Anda biasanya akan memeriksa di bagian akhir hanya untuk memverifikasi konvergensi.

Matt Knepley
sumber
Apakah Anda memiliki sumber untuk mendukung ini? Saat ini jawaban Anda dan jawaban yang terpilih lainnya langsung saling bertentangan.
Doug Lipinski
1) Buku Saad adalah referensi terbaik untuk menggunakan FGMRES untuk mengakomodasi perubahan prakondisi: www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf 2) Saya percaya bukti bahwa FMG mengurangi kesalahan di bawah kesalahan diskresi dengan cukup kuat V-cycle ada di Trottenberg dan Osterlee, tapi saya mereproduksi buktinya dalam buku saya: cse.buffalo.edu/~knepley/classes/caam519/CSBook.pdf
Matt Knepley
4

Tentu saja tidak. Untuk mengambil satu contoh, buku Multigrid memiliki plot pada halaman 53 (Gambar 2.10) yang menunjukkan pengurangan residu sebagai fungsi dari jumlah siklus V atau W. Anda akan berhenti bersepeda ketika Anda puas dengan ukuran residu.

Sumber kebingungan Anda mungkin karena beberapa deskripsi hanya menggambarkan satu siklus-V. Dalam beberapa kasus terbatas, karena multigrid adalah teknik yang sangat kuat, ini dapat menghasilkan solusi yang cocok. Multigrid juga dapat digunakan sebagai prasyarat . Dalam hal ini, multigrid hanyalah akselerator, dan pemeriksaan untuk konvergensi terjadi pada tingkat yang lebih tinggi. Tetapi cek harus selalu terjadi di suatu tempat.

Baja Damaskus
sumber
1
Apakah Anda memiliki sumber untuk mendukung ini? Saat ini jawaban Anda dan jawaban yang terpilih lainnya langsung saling bertentangan.
Doug Lipinski
1

Dalam Multigrid digunakan sebagai pemecah , biasanya norma relatif dari residu digunakan sebagai kriteria penghentian. Saat Anda mengurangi rasio ini - keakuratan solusi akan meningkat. Lebih lanjut, pada tingkat yang paling kasar, para peneliti melakukan berbagai hal:

  1. baik memecahkan menggunakan pemecah langsung (tidak ada konvergensi)
  2. gunakan iterasi tetap (tidak ada konvergensi)
  3. gunakan perbedaan berturut - turut antara iterasi sebagai kriteria konvergensi (bukan metode yang baik karena Anda bisa jauh dari solusinya)
  4. Sekali lagi gunakan norma relatif residual sebagai kriteria berhenti.

Metode 2 yang tercantum di atas pada level paling kasar adalah baik ketika Multigrid digunakan sebagai Pra-kondisioner (pakar Multigrid dapat berkomentar - Saya seorang pemula).

Jadi, konvergensi secara umum digunakan .

Gaurav Saxena
sumber