infistream

Menu

10.4 pendekatan multigrid

Laju konvergensi dari metode iteratif secara drastis memburuk seiring dengan ukuran sistem aljabar yang meningkat, dengan penurunan laju konvergensi bahkan diamati pada sistem berukuran sedang hingga besar setelah kesalahan awal telah dihilangkan. Ini merupakan batasan serius bagi pemecah sistem iteratif. Untungnya, cepat ditemukan bahwa kombinasi metode multigrid dan metode iteratif dapat secara praktis mengatasi kelemahan ini.

Pengembangan dalam metode multigrid dimulai dengan karya Fedorenko [30] (Multigrid Geometris), Poussin [31] (Multigrid Aljabar), dan Settari dan Azziz [32], dan mendapatkan lebih banyak minat dengan karya teoretis Brandt [33]. Sementara kesalahan frekuensi tinggi atau osilasi dengan mudah dihilangkan dengan pemecah iteratif standar (Jacobi, Gauss-Seidel, ILU), teknik solusi ini tidak dapat dengan mudah menghilangkan komponen kesalahan frekuensi rendah atau halus [34]. Karena itu, teknik solusi ini 

GAMBAR 10.4

Skema mode kesalahan yang berbeda dalam suatu grid satu dimensi.

 

Metode denoised oleh penghalus dalam konteks metode multigrid. Ilustrasi frekuensi kesalahan ditunjukkan pada Gambar 10.4 di mana variasi mode frekuensi kesalahan untuk masalah satu dimensi dipetakan. 

Mode kesalahan yang ditunjukkan di Gambar 10.4 bervariasi dari frekuensi tinggi gelombang pendek k1 hingga frekuensi rendah gelombang panjang k5 dan dipetakan secara bersama-sama di bagian atas gambar. Domain satu dimensi di-discretkan menggunakan grid satu dimensi yang ditunjukkan, dan berbagai mode dipetakan secara terpisah di atas grid yang sama. Seperti yang dapat dilihat, kesalahan frekuensi tinggi muncul berayun di atas suatu elemen dan dengan mudah dirasakan oleh metode iteratif. Seiring dengan penurunan frekuensi kesalahan atau dengan kata lain panjang gelombang ðkÞ meningkat, kesalahan menjadi semakin halus di atas grid karena hanya sebagian kecil panjang gelombang yang terletak di dalam setiap sel. Hal ini semakin memburuk seiring dengan penyempurnaan grid, menyebabkan peningkatan jumlah persamaan dan menjelaskan penurunan laju konvergensi seiring dengan ukuran sistem yang meningkat.

Metode multigrid meningkatkan efisiensi solvers iteratif dengan memastikan bahwa kesalahan frekuensi rendah yang muncul dari aplikasi penghalus pada setiap tingkat grid diubah menjadi kesalahan frekuensi tinggi pada tingkat grid yang lebih kasar. Dengan menggunakan hirarki grid kasar (Gambar 10.5), metode multigrid dapat mengatasi penurunan konvergensi.
Secara umum, mesh kasar dapat dibentuk baik dengan menggunakan topologi dan geometri mesh yang lebih halus, ini mirip dengan menghasilkan mesh baru untuk setiap tingkat kasar di atas mesh tingkat halus atau dengan aglomerasi langsung dari elemen mesh yang lebih halus [35–40]; pendekatan ini juga dikenal sebagai Metode Multigrid Aljabar (AMG).
Pada AMG, tidak diperlukan atau digunakan informasi geometris secara langsung, dan proses aglomerasi bersifat murni aljabar, dengan persamaan pada setiap tingkat kasar direkonstruksi dari persamaan tingkat yang lebih halus, lagi melalui proses aglomerasi. Pendekatan ini dapat digunakan untuk membangun solver linear yang sangat efisien dan kuat

GAMBAR 10.5

Skema dari hierarki sistem grid yang digunakan dengan pendekatan multigrid.

 

Dalam kedua pendekatan tersebut, prosedur siklus multigrid digunakan untuk membimbing perjalanan di berbagai hierarki grid. Setiap perjalanan dari grid halus ke yang kasar melibatkan: (i) prosedur restriksi, (ii) pengaturan atau pembaruan sistem persamaan untuk tingkat grid kasar, dan (iii) aplikasi sejumlah iterasi perata yang lebih halus.

Perjalanan dari grid kasar ke yang lebih halus memerlukan: (i) prosedur prolongasi, (ii) koreksi nilai medan pada tingkat yang lebih halus, dan (iii) aplikasi sejumlah iterasi perata yang lebih halus pada persamaan yang dibangun selama restriksi. Langkah-langkah tersebut dijelaskan selanjutnya.

  1. 10.4.1 Aglomerasi elemen, atau penggumpalan elemen
  2. 10.4.2 Langkah pembatasan (restriction step) dan koefisien pada tingkat kasar 
  3. 10.4.3 Langkah Prolongasi dan Koreksi pada Tingkat Grid Halus
  4. 10.4.4 Strategi Traversal dan Siklus Multigrid Aljabar