Multigrid pada kisi “not perfect rectangular”

9

Pendahuluan multigrid biasanya menggunakan kotak persegi panjang. Interpolasi nilai kemudian lurus ke depan: Hanya interpolasi secara linear di tepi antara dua node yang berdekatan dari grid kasar untuk menemukan nilai dari node grid halus di tepi itu.

Untuk aplikasi FEM saya memiliki kotak yang "topologis" persegi panjang sehingga koneksi node seperti pada kotak persegi panjang. Namun, node tidak sepenuhnya selaras pada grid tetapi dapat menempuh jarak kecil agar lebih sesuai dengan geometri, sementara masih mempertahankan koneksi seperti pada kotak persegi panjang yang sempurna.

Mesh terlihat seperti itu: Contoh mesh . Anda lihat: Koneksi adalah "persegi panjang biasa", tetapi posisi simpul tidak.

Saya dapat gambar beberapa skema interpolasi geometris "masuk akal" untuk pengaturan seperti itu.

Pertanyaan umum adalah: Apakah multigrid memerlukan kisi-kisi persegi panjang yang disejajarkan dengan sempurna, atau akankah ini juga bekerja dengan situasi yang dijelaskan di atas, selama interpolasi adalah "baik"? Atau lebih baik menggunakan multigrid aljabar dalam kasus itu? (Yang saya tidak suka karena itu tidak intuitif sebagai multigrid geometris.)

Michael
sumber
Saya tidak yakin saya mengerti apa yang Anda maksud dengan grid yang menjadi persegi panjang secara topologi, tetapi di mana node tidak selaras seperti dalam kotak persegi panjang. Apakah kisi tersebut adalah kisi persegi panjang terstruktur? Bisakah Anda menjelaskan ini, mungkin dengan gambar? Apakah masalah bahwa Anda menggunakan elemen persegi panjang yang tidak sejajar seperti yang akan terjadi ketika menggunakan kisi cartesian terstruktur?
James
@ James, saya menafsirkan pertanyaan OP lebih seperti: "Apa yang terjadi jika saya memiliki kotak 'cartesian-ish' di dalam trapesium?".
Bill Barth

Jawaban:

6

Multigrid tidak membutuhkan kisi seragam Cartesian (persegi panjang). Yang dibutuhkan adalah Anda dapat menetapkan level halus dan kasar (mungkin secara rekursif, jika Anda ingin beralih dari skema dua level ke skema multi-level), dan Anda dapat menentukan operator interpolasi di antara level-level ini. Cara termudah untuk menjelaskan ini adalah jika Anda memang memiliki kisi Cartesian, tetapi sebenarnya Anda dapat memulai dengan jaring kasar apa saja, memperbaikinya sekali, dan seperti ini: Anda memiliki jaring yang lebih halus.

Dengan kata lain, paling mudah untuk memikirkan jerat multigrid yang cocok bukan sebagai jerat halus dan bagaimana menemukan jerat kasar, tetapi untuk memulai dengan jerat kasar dari mana Anda mendapatkan tingkat yang lebih baik dengan penyempurnaan seragam (yaitu, setiap segi empat adalah dibagi menjadi empat yang lebih kecil). Karena penyempurnaan seragam selalu memungkinkan, ini siap memberi Anda hierarki. Ini bertentangan dengan pengerasan, yang tidak selalu mungkin jika Anda hanya diberi mesh tertentu, dan karenanya membuat mendefinisikan hierarki mesh jauh lebih rumit. (Itulah sebabnya orang datang dengan metode multigrid aljabar untuk menentukan tingkat kasar berdasarkan hanya pada matriks, tanpa memikirkan kaitan yang mendasarinya dari mana ia dibuat.)

Wolfgang Bangerth
sumber
Saya mengedit contoh gambar ke dalam pertanyaan. Saya akan menganggap pengerasan sangat mudah dalam kasus saya dengan hanya mengambil setiap 2 nd (per dimensi) dan menghitung ulang FEM untuk kisi tersebut untuk mendapatkan matriks / operator kasar. Vektor data kasar dapat diperoleh dengan hanya mengambil setiap nilai 2 node.
Michael
1
Itu mungkin atau mungkin tidak bekerja sebaik yang Anda inginkan (saya kira itu mungkin akan, tetapi saya tidak sepenuhnya yakin). Masalahnya adalah bahwa dalam contoh Anda, sel jala kasar tidak mencakup area yang sama dengan anak-anak, sehingga tidak ada properti bersarang dari ruang elemen hingga: fungsi yang dapat Anda wakili pada jala kasar bukan subset dari fungsi yang dapat Anda wakili pada fine mesh. Joe Pasciak dan Jim Bramble telah menulis makalah tentang kasus-kasus seperti itu, dan saya pikir saya ingat bahwa mereka dapat dibuat berfungsi. Tapi itu tidak segera jelas bagi saya.
Wolfgang Bangerth
4

Katakanlah Anda memiliki kotak berikut yang terdiri dari elemen persegi panjang:

masukkan deskripsi gambar di sini

Sekarang jika Anda melakukan interpolasi Anda dengan asumsi kotak persegi panjang terstruktur yang normal maka Anda akan memperkenalkan kesalahan yang terkait dengan interpolasi yang tidak akurat ini. Dengan kata lain ketika Anda membatasi vektor residual Anda dan ketika Anda memperpanjang vektor kesalahan Anda akan ada kesalahan dari interpolasi.

Sekarang jika kisi Anda "hampir" menjadi kisi cartesian terstruktur normal maka ini mungkin berhasil, setidaknya pada awalnya, tetapi saya menduga salah satu dari dua hal akan terjadi tergantung pada seberapa jauh kisi Anda dari menjadi persegi panjang:

1) Anda mungkin menemukan bahwa multigrid mulai konvergen pada awalnya. Setelah semua awalnya kesalahan Anda adalah besar dan interpolasi "perkiraan" Anda benar-benar hanya berarti bahwa beberapa node sedikit lebih terwakili sementara ada yang sedikit kurang terwakili. Namun Anda mungkin menemukan bahwa konvergensi mandek ketika solusi menjadi lebih akurat dan kesalahan interpolasi menjadi lebih penting.

2) Kemungkinan lain adalah multigrid tersebut akhirnya konvergen, tetapi tidak secepat yang seharusnya jika Anda menggunakan interpolasi yang benar.

Pada dasarnya dengan tidak aktif dengan interpolasi Anda, Anda menimbang pentingnya node tertentu secara tidak akurat. Misalnya dalam 2D ​​jika Anda menimbang simpul yang diberikan sebagai:

[0,250,50,250,51.00,50,250,50,25]

padahal sebenarnya karena grid Anda tidak sepenuhnya kartesius itu seharusnya:

[0,250,550,250,551.00,490,280,520,30]

maka ini akan menghasilkan beberapa kesalahan. Apakah kesalahan ini mencegah convegence kemungkinan akan tergantung pada seberapa jauh grid Anda dari menjadi cartesian.

Sementara AMG lebih sulit untuk memahami / mengimplementasikannya, sepertinya itu adalah metode yang tepat untuk kisi Anda. Menerapkan multigrid geometris ke kotak persegi panjang "perkiraan" mungkin berhasil, tapi saya kira itu adalah solusi pita bantuan terbaik. Semoga ini membantu.

Pembaruan : Saya pikir mungkin ada beberapa kebingungan dalam jawaban saya. Saya tidak mengatakan bahwa geometri multigrid hanya akan bekerja dengan jerat cartesian, tetapi bahwa mendefinisikan interpolasi (dan karenanya pembatasan) pada jerat cartesian itu mudah sedangkan pada jerat non-terstruktur ini mungkin sulit. Sebagai contoh, pertimbangkan kasus bahkan domain 2D sederhana dengan mesh segitiga. Memperbaiki mesh ini mudah - setidaknya secara konseptual - tetapi bagaimana Anda mendefinisikan operator interpolasi antara mesh kasar dan halus? Saya lebih suka AMG hanya karena kinerjanya lebih seperti pemecah "kotak hitam", yaitu tidak memerlukan informasi tentang jaring yang tidak terbuka, namun ini hanya bias orang saya / kekhasan. Multigrid geometris dapat berfungsi selama Anda dapat menyediakan operator interpolasi yang akurat.

James
sumber
Saya dapat membaca ini sebagai "tergantung seberapa baik interpolasi Anda", benar? Jadi, jika saya bisa datang dengan skema interpolasi "sempurna", maka saya harus baik-baik saja?
Michael
1
Saya pikir jawaban ini benar tetapi menyesatkan - dikatakan bahwa jika Anda berpura-pura grid Anda adalah cartesian biasa ketika tidak, Anda akan mendapatkan jawaban yang salah. Itu benar, tetapi Anda bisa mengatakan hal yang sama tentang metode numerik apa pun. Intinya adalah bahwa geometri multigrid akurat pada jerat yang lebih umum bila diterapkan dengan benar .
David Ketcheson
Saya setuju bahwa geometri multigrid dapat digunakan dengan jerat non-cartesian selama dilakukan dengan benar. Saya hanya mengambil pertanyaan OP sebagai menanyakan apakah menggunakan mesh cartesian "kira-kira," sementara menggunakan interpolasi yang dirancang untuk mesh cartesian yang sebenarnya, akan berhasil.
James
@Michael Pada dasarnya Anda perlu beberapa cara untuk mendefinisikan operator interpolasi antara tingkat grid yang berbeda. Dengan jerat cartesian ini mudah. Dengan jerat non-cartesian, ini dapat dengan cepat menjadi lebih sulit tergantung pada seberapa tidak terstrukturnya jerat Anda. Seperti yang dikatakan Wolfgang dalam jawabannya, Anda selalu dapat membuat mesh yang lebih halus dari yang kasar, tetapi mendefinisikan operator interpolasi yang berarti mungkin sulit. Keuntungan dari AMG adalah berperilaku lebih seperti pemecah "kotak hitam" karena Anda tidak perlu data mesh untuk mendefinisikan operator interpolasi. Yang Anda butuhkan adalah matriks
James
@MIchael Jadi untuk menjawab pertanyaan Anda. Ya, jika Anda dapat membuat operator interpolasi yang akurat maka multigrid geometrik akan berfungsi dengan baik. Semoga ini membantu.
James