Çoklu Izgara Yöntemleri
Çoklu ızgara yöntemleri, ayrıklaştırılmış kısmi diferansiyel denklemlerin (KDD) çözümünü, ince ızgaralardaki ucuz düzeltmeyi (smoothing) daha kaba ızgaralarda hesaplanan düzeltmelerle birleştirerek hızlandırmaktadır. Bu yöntemler, hatayı her uzunluk ölçeğinde ele almakta ve ağ boyutundan bağımsız yakınsama oranları elde etmektedir.
Tanım
Çoklu ızgara yöntemi, hatayı farklı çözünürlükteki ızgara hiyerarşisinde temsil eden, ince ızgaralardaki salınımlı hata bileşenlerini gidermek için ucuz gevşetme (relaxation) ve düzgün bileşenleri gidermek için kaba ızgara çözümlerini tüm ölçeklerde özyinelemeli olarak kullanan bir yinelemeli çözücüdür.
Kapsam
Bu konu, basit iterasyonların düzeltme (smoothing) özelliğini, kısıtlama (restriction) ve uzatma (prolongation) yoluyla artıkların (residuals) ve düzeltmelerin ızgaralar arası aktarımını, iki ızgaralı ve V-, W- ve tam çoklu ızgara döngülerini, geometrik ve cebirsel çoklu ızgara karşılaştırmasını ve çoklu ızgarayı eliptik problemler için bir referans çözücü yapan optimal (doğrusal) hesaplama karmaşıklığını kapsamaktadır.
Temel sorular
- Basit iterasyonlar neden salınımlı hatayı hızla azaltırken, düzgün hatayı yavaşça azaltır ve bu durum kaba ızgaraları nasıl motive eder?
- Artıklar kaba ızgaralara nasıl kısıtlanır ve düzeltmeler ince ızgaralara nasıl geri uzatılır?
- Çoklu ızgara döngüleri, ağdan bağımsız yakınsama elde etmek için bu işlemleri nasıl birleştirir?
- Cebirsel çoklu ızgara, temel bir geometrik ızgarası olmayan problemlere bu fikri nasıl genişletir?
Temel kuramlar
- Düzeltme (Smoothing) ve kaba ızgara düzeltmesi
- Gauss-Seidel gibi klasik gevşetmeler, yüksek frekanslı (salınımlı) hatayı hızla bastırırken, düşük frekanslı hataya neredeyse hiç dokunmaz. Çoklu ızgara bu durumu, düzgün, yavaş yakınsayan hatayı, salınımlı göründüğü ve ucuzca azaltıldığı daha kaba ızgaralara aktararak kullanır.
- Ağdan bağımsız optimal karmaşıklık
- V- veya W-döngülerinde düzeltme (smoothing) ve kaba ızgara düzeltmesini özyinelemeli olarak uygulamak, ızgara boyutundan bağımsız olarak sınırlı yakınsama faktörleri sağlar; böylece belirli bir toleransa kadar çözmek için gereken iş, bilinmeyenlerin sayısıyla yalnızca doğrusal olarak artar.
Mekanizmalar
Bir çoklu ızgara döngüsü, hatayı düzeltmek için sistemi ince ızgarada gevşeterek başlar, artığı hesaplar ve artık denkleminin çözüldüğü (özyinelemeli olarak, aynı döngüyle) daha kaba bir ızgaraya kısıtlar. Kaba ızgara düzeltmesi daha sonra geri uzatılır ve ince ızgara yaklaşımına eklenir, ardından daha fazla gevşetme yapılır. Her ızgara seviyesi, en verimli olduğu hata bileşenlerini ele aldığı için, birleşik döngü belirli sayıda taramada tüm ölçeklerdeki hatayı azaltır. Cebirsel çoklu ızgara, ızgara hiyerarşisini ve aktarım operatörlerini doğrudan matris girdilerinden oluşturur, bu nedenle geometrik bir ağa ihtiyaç duyulmaz.
Klinik önem
Çoklu ızgara, eliptik ve parabolik KDD'lerden kaynaklanan büyük seyrek sistemler için en verimli çözücüler arasındadır ve hesaplamalı akışkanlar dinamiği, yapısal mekanik, elektromanyetizma ve görüntü işlemede bir çözücü veya ön koşullandırıcı (preconditioner) olarak kullanılmaktadır; neredeyse optimal ölçeklenebilirliği, paralel süper bilgisayarlardaki aşırı ölçekli simülasyonlar için hayati öneme sahiptir.
Tarihçe
Çoklu ızgara fikri, 1961 civarında Fedorenko tarafından ortaya atılmış ve 1970'lerde Achi Brandt tarafından pratik, geniş çapta uygulanabilir bir yönteme dönüştürülmüştür. Hackbusch'un analizi onu sağlam bir temele oturtmuş, cebirsel çoklu ızgara ise daha sonra erişimini yapılandırılmamış ve geometrik olmayan problemlere genişleterek optimal karmaşıklıkta bir çözücü olarak statüsünü pekiştirmiştir.
Öne çıkan isimler
- Radii Fedorenko
- Achi Brandt
- Wolfgang Hackbusch
- Stephen McCormick
İlgili konular
Temel eserler
- trottenberg2001
- briggs2000
Sıkça sorulan sorular
- Kaba ızgaralar neden faydalıdır?
- İnce ızgara gevşetmesinin yavaşça giderdiği düzgün hata, daha kaba bir ızgarada salınımlı görünür ve gevşetme onu hızlı ve ucuz bir şekilde giderir. Bu nedenle, farklı çözünürlükteki ızgaralar arasında döngü yapmak, her hata bileşenini verimli bir şekilde ortadan kaldırır.
- Geometrik ve cebirsel çoklu ızgara arasındaki fark nedir?
- Geometrik çoklu ızgara, problem geometrisinden elde edilen daha kaba ağların açık bir hiyerarşisini kullanırken, cebirsel çoklu ızgara, kaba seviyeleri ve aktarım operatörlerini matristen otomatik olarak oluşturur; bu da doğal bir ızgara hiyerarşisi olmadığında uygulanabilir olmasını sağlar.