FAS-multigrid lebih lambat daripada koreksi cacat linear?

9

Saya telah menerapkan pemecah multigrid V-Cycle menggunakan koreksi cacat linier (LDC) dan skema aproksimasi penuh (FAS).

Masalah saya adalah sebagai berikut: Menggunakan LDC residual dikurangi dengan faktor ~ 0,03 per siklus. Implementasi FAS memang konvergen dengan faktor linear juga, tetapi faktornya hanya ~ 0,58. Jadi FAS membutuhkan sekitar 20 kali jumlah siklus.

Sebagian besar kode dibagikan, satu-satunya perbedaan adalah perhitungan turun / naik, menggunakan LDC

bawah:uH:=0,bH:=IhH(bhLhuh)

up:uh:=uh+IHhuH

dan penggunaan FAS

bawah: uH:=IhHuh,bH:=IhHbh+LHIhHuhIhHLhuh

up: uh:=uh+IHh(uHIhHuh)

Pengaturan pengujian saya dari Brigg "A Multigrid Tutorial, Second Edition", hal. 64, memiliki solusi analitis

u(x,y)=(x2x4)(y4y2) dengan x,y[0,1]2

dan persamaan adalah Lv=Δu=:b menggunakan khas linear 5-titik stensil sebagai Laplace-operator L . Tebakan awal adalah v=0 .

Mengubah pengaturan tes, misalnya ke u sepele (x, y) = 0u(x,y)=0 menggunakan tebakan awal v=1 menghasilkan faktor konvergensi yang hampir sama.

Karena hanya kode turun / atas yang berbeda, hasil LDC sesuai dengan buku dan FAS setidaknya tampaknya berfungsi juga, saya tidak tahu mengapa jauh lebih lambat dalam pengaturan linier yang sama.

Ada satu perilaku aneh dalam LDC dan FAS yang saya tidak dapat jelaskan tetapi itu hanya terjadi jika tebakan awal buruk (misalnya tetapi juga dalam percobaan multigrid penuh saya di mana interpolasi ke kisi-kisi halus baru meningkatkan residu dari hingga ): Jika saya menambah jumlah relaksasi pasca koreksi ke jumlah yang sangat tinggi sehingga solusinya diselesaikan ke mesin presisi pada grid kasar, ia kehilangan hampir semua digit ketika naik satu langkah ke atas ke kotak halus berikutnya.=01015101

Karena gambar mengatakan lebih dari sekadar kata-kata:

// first cycle, levels 0-4
// DOWN
VCycle top 4, start               res_norm 3.676520e+02 // initial residual
VCycle top 4, cycle 0, current 4, res_norm 3.676520e+02
VCycle top 4, cycle 0, current 4, res_norm 1.520312e+02 // relaxed (2 iterations)
VCycle tau_norm 2.148001e+01 (DEBUG calculation)
VCycle top 4, cycle 0, current 3, res_norm 1.049619e+02 // restricted
VCycle top 4, cycle 0, current 3, res_norm 5.050392e+01 // relaxed (2 iterations)
VCycle top 4, cycle 0, current 2, res_norm 3.518764e+01 // restricted
VCycle top 4, cycle 0, current 2, res_norm 1.759372e+01 // relaxed (2 iterations)
VCycle top 4, cycle 0, current 1, res_norm 1.234398e+01 // restricted
VCycle top 4, cycle 0, current 1, res_norm 4.728777e+00 // relaxed (2 iterations)
VCycle top 4, cycle 0, current 0, res_norm 3.343750e+00 // restricted
// coarsest grid
VCycle top 4, cycle 0, current 0, res_norm 0.000000e+00 // solved
// UP
VCycle top 4, cycle 0, current 1, res_norm 3.738426e+00 // prolonged
VCycle top 4, cycle 0, current 1, res_norm 0.000000e+00 // relaxed (many iterations)
VCycle top 4, cycle 0, current 2, res_norm 1.509429e+01 // prolonged (loosing digits)
VCycle top 4, cycle 0, current 2, res_norm 2.512148e-15 // relaxed (many iterations)
VCycle top 4, cycle 0, current 3, res_norm 4.695979e+01 // prolonged (loosing digits)
VCycle top 4, cycle 0, current 3, res_norm 0.000000e+00 // relaxed (many iterations)
VCycle top 4, cycle 0, current 4, res_norm 1.469312e+02 // prolonged (loosing digits)
VCycle top 4, cycle 0, current 4, res_norm 9.172812e-24 // relaxed (many iterations)

Saya tidak yakin apakah hanya ada beberapa digit yang diperoleh per siklus atau apakah ini menunjukkan kesalahan selama interpolasi ke kisi-kisi halus. Jika ini adalah kasus terakhir, bagaimana LDC dapat mencapai rasio residu sesuai-buku ~ 0,03 saat menggunakan selalu 2 relaksasi?

Silpion
sumber

Jawaban:

7

Saya tidak langsung tahu jawaban Anda karena saya lebih banyak menggunakan FAS daripada koreksi karena saya melakukan multigrid untuk masalah nonlinier, tetapi beberapa pemikiran Anda dapat melihat:

  • Anda menerapkan skema koreksi linier untuk masalah linier, jadi tidak mengejutkan bahwa ia melakukannya dengan sangat baik.

  • Pertimbangkan kondisi batas Anda: pastikan Anda melakukannya dengan benar, dan perhatikan juga bahwa BC yang rumit bisa terlihat sangat berbeda pada grid kasar, membuat koreksi di sana tidak begitu berguna.

  • Periksa kembali perawatan Anda dari istilah sumber; Saya ingat mengacaukan sesuatu dalam tahap perpanjangan yang terkait dengan istilah itu ketika saya menulisnya untuk poisson.

  • Saya belum pernah melihat kebutuhan untuk beralih ke konvergensi di grid paling kasar. Solusi di sana tergantung pada residu kisi halus yang benar, yang mana tidak. Anda mencoba mendorong kesalahan itu keluar dari domain / menghaluskannya. Jika Anda sepenuhnya terkonvergensi pada grid kasar dalam iterasi awal, solusi Anda secara alami cukup jauh dari solusi fine grid yang benar karena residu Anda di sana tidak mutakhir. Ini hampir pasti alasan mengapa Anda melihat residu melompat pada tahap perpanjangan.

  • Juga, cobalah faktor relaksasi untuk operator pembatasan dan perpanjangan, katakanlah 0,75.

Jika ini membantu, inilah yang tampak seperti riwayat residu FAS saya untuk masalah poisson menggunakan kisi tunggal melalui siklus 7V penuh. Saya percaya faktor relaksasi adalah 0,75, dan saya menggunakan skema RK 3-tahap sebagai lebih lancar dengan satu iterasi pada setiap level grid.

riwayat res

Aurelius
sumber
Terima kasih atas balasan Anda, kasing linier dan BC sederhana (batas persegi = 0) hanyalah langkah pertama, menguji kasing nyata akan dilakukan setelah pengaturan "mudah" berfungsi. Saya tidak yakin apakah saya mengerti maksud Anda dengan faktor relaksasi untuk pembatasan dan perpanjangan. Saat ini saya menggunakan interpolasi bilinear untuk perpanjangan dan setengah-bobot untuk pembatasan.
Silpion
Maksud saya relaksasi untuk tahap Perpanjangan Anda ubah ke: mana adalah faktor relaksasi. Secara umum semakin rumit solusinya, semakin rendah faktor ini yang perlu dituju. Dalam solusi dengan banyak diskontinuitas, kadang-kadang saya harus mendorongnya ke sekitar 0,6, tetapi umumnya 0,75-0,85 berfungsi. 0 < α < 1uh:=uh+αIHh(uHIhHuh)0<α<1
Aurelius
Senang mendengarnya. Dalam pengaturan saya ini hanya memperlambat rasio konvergensi dengan tetapi saya akan mengingatnya saat menguji data yang lebih kompleks. (1α)
Silpion
@ Aurelius Anda menyebutkan bahwa konvergensi di grid kasar tidak perlu. Saya setuju dengan alasan Anda, tetapi bukti konvergensi dalam literatur (untuk kasus linier) berasumsi bahwa pemecahan grid kasar adalah tepat. Saya tidak mengetahui adanya referensi (untuk kasus linier atau nonlinier) di mana dinyatakan bahwa penyelesaian grid kasar seharusnya tidak tepat, dan bertanya-tanya apakah Anda dapat mengutip referensi untuk ini? Saya akan sangat tertarik melihat ini sendiri
Keeran Brabazon
@ KeeranBrabazon Saya tidak punya referensi untuk ini juga, dan saya jujur ​​tidak akrab dengan rincian bukti konvergensi untuk multigrid. Saya sarankan mencari literatur awal yang memperkenalkan faktor relaksasi itu. Faktor itu umum untuk semua implementasi multigrid modern yang pernah saya lihat, dan secara intuitif benar bahwa itu tidak diperlukan jika solusi kursus yang tepat diperlukan / diinginkan. Untuk bukti intuitif, saya hanya membayangkan seperti apa kondisi batas untuk grid kasar vs yang terbaik. Mudah membayangkan mereka menciptakan solusi yang sangat berbeda.
Aurelius
6

Jika Anda menggunakan diskresi terpusat-titik, maka pembatasan keadaan harus disuntikkan daripada pembatasan residual berbobot penuh yang tampaknya Anda gunakan. Yaitu, ganti dengan saat membatasi negara. Menggunakan pembatasan full-weighted untuk state menghasilkan aliasing komponen frekuensi tinggi dari state yang setelah menerapkan menghasilkan noise baru pada skala yang sama seperti sebelumnya koreksi kasar (kondisi batas kemungkinan merupakan penyebab utama efek ini). Gunakan injeksi, , dan masalah ini akan hilang.I H h u hu h ( u H - I H h u h ) I H h u hIhHI^hHuhuh(uHIhHuh)I^hHuh

Secara spektral, pembatasan negara hanya membutuhkan tatanan sekunder tinggi (pelestarian akurat frekuensi rendah), tetapi tatanan primer (aliasing frekuensi tinggi) tidak masalah. Injeksi memiliki urutan primer 0 dan urutan sekunder tak terbatas. Sementara itu, pembatasan residual membutuhkan urutan primer dan sekunder untuk menjadi positif (setidaknya). Lihat bagian 4.3 dari Panduan Multigrid Achi Brandt .

Saat merancang metode MG, lebih baik untuk melihat kesalahan daripada residu dan untuk memastikan Anda mempertimbangkan norma dengan tepat.

Jed Brown
sumber
Poin bagus, dan saya gagal menyebutkan sesuatu di sepanjang garis itu. Salah satu aspek penting dari penggunaan praktis multigrid adalah pilihan yang lebih halus: Anda menginginkan yang mengurangi kesalahan frekuensi tinggi secepat mungkin, yang membahas masalah yang Anda uraikan.
Aurelius
@ Aurelius Dari log yang disediakan, Anda dapat melihat bahwa yang lebih halus bukanlah masalahnya. Ingat bahwa Silpion menggunakan MG yang lebih mulus untuk koreksi cacat, yang menyatu dengan benar.
Jed Brown
Terima kasih atas tautannya ke Panduan Multigrid Brandt, saya akan membacanya secara menyeluruh setelah menyelesaikan Tutorial Multigrid Brigg. Saya memecahkan masalah sekarang (lihat jawaban lain) tetapi saya saat ini menggunakan pembobotan penuh untuk pembatasan status dan residual. Menggunakan injeksi tampaknya tidak berfungsi dalam pengaturan saya, rasio residual berubah menjadi dan baik residual dan error L2-norma berhenti berkurang segera. Apakah Anda punya ide mengapa injeksi gagal? >0.8
Silpion
1

Saya diselesaikan dengan masalah sekarang. Saya menyimpan ketika turun selama siklus-V dan menggunakannya kembali nanti diuoldH=IhHuh

uhuh+IHh(uHIhHuh)=uh+IHh(uHuoldH) .

Masalahnya adalah sebelum turun lagi dari ke , santai di tempat . Menyimpan salinan sebelum langkah-langkah relaksasi membantu. Karena hanya diperlukan dalam FAS, itu tidak muncul dalam perhitungan linier.2 H u H o l d u H o l dH2HuoldHuoldH

Silpion
sumber