BDDC

数値解析において、BDDC (制約によるバランス領域分割)は、有限要素法から生じる大規模な対称正定値線形方程式を解くための領域分割法です。BDDC は、共役勾配法の前処理として使用されます。BDDC の特定のバージョンは、粗い自由度の選択を特徴としており、これはサブドメインの角の値、またはサブドメイン間のインターフェイスのエッジまたは面の平均です。BDDC 前処理の 1 つの適用では、各サブドメイン上のローカル問題の解と、粗い自由度を未知数とするグローバルな粗い問題の解を組み合わせます。異なるサブドメイン上のローカル問題は互いに完全に独立しているため、この方法は並列計算に適しています。粗い自由度 (2D ではコーナー、3D ではコーナーとエッジ、またはコーナーと面) を適切に選択し、サブドメインの形状を規則的にすると、サブドメインの数を増やしてもメソッドの条件数は制限され、サブドメインあたりの要素数の増加とともに非常にゆっくりとしか増加しません。したがって、反復回数も同様に制限され、メソッドは問題のサイズとサブドメインの数に応じて適切にスケーリングされます。

歴史

BDDCは、ほぼ同時期に、すなわちCros ^[1] 、 Dohrmann ^[2]、FragakisとPapadrakakis ^{[3]によって、}Farhatら[4]によるFETI-DP領域分割法の主な代替手段として、異なる著者と異なるアプローチで導入されました。^[^{5]これらがすべて実際にBDDCと同じ方法であることの証明については、}^[6]を参照してください。この方法の名前は、 BDD（バランシング領域分割）法^[8 ]のさらなる発展として理解できるため、MandelとDohrmann ^[7]によって造られました。Mandel 、Dohrmann、およびTezaur ^[9]は、BDDCとFETI-DPの固有値は、BDDCに存在する可能性があるがFETI-DPには存在しない1に等しい固有値を除いて同一であり、したがって反復回数は実質的に同じであることを証明しました。この事実のより単純な証明は、後にLiとWidlund ^[10]とBrennerとSung ^[11]によって得られました。

粗いスペース

BDDCの粗い空間は、粗い自由度の与えられた値を持つエネルギー最小関数から構成されます。これは、プレートとシェルのBDDのバージョンのコーナーに使用されるのと同じ粗い空間です。^[12]違いは、BDDCでは粗い問題が加算的に使用されるのに対し、BDDでは乗法的に使用されることです。

機械的な説明

BDDC 法は、線形弾性の問題を解くためによく使用され、弾性構造の変形の観点から説明するのが最も適切かもしれません。弾性問題とは、規定の変位と力が適用された構造の変形を決定することです。有限要素法を適用すると、線形代数方程式のシステムが得られます。ここで、未知数は要素のノードでの変位であり、右辺は力 (および境界上のゼロ以外の規定変位ですが、簡単にするためにこれらはゼロであると仮定します) から得られます。

前処理子は右辺を取り、近似解を出力します。したがって、重複しないサブ構造に分割された弾性構造があると仮定し、簡単にするために、粗い自由度はサブドメインのコーナーのみであると仮定します。構造に適用される力が与えられていると仮定します。

BDDC 法の最初のステップは内部補正です。これは、サブドメインとその隣接ドメインとのインターフェースを除くサブドメインに適用される力に基づいて、各サブドメインの変形を個別に求めることです。各サブドメインの内部は独立して動き、インターフェースは変形ゼロのままなので、インターフェースにねじれが生じます。ねじれのバランスを保つために必要なインターフェース上の力は、インターフェースにすでに与えられている力に追加されます。次に、インターフェースの力がサブドメインに分配されます (均等に分配されるか、サブドメインの材料の剛性に比例した重み付けで分配され、より剛性の高いサブドメインにより多くの力が加わります)。

2 番目のステップはサブドメイン補正と呼ばれ、サブドメインのコーナーでの変位がゼロであるという条件に従って、各サブドメインでのこれらのインターフェース力の変形を個別に検出します。一般に、インターフェース全体のサブドメイン補正の値は異なることに注意してください。

サブドメイン補正と同時に、粗補正が計算されます。粗補正は、サブドメインのすべてのコーナーでの変位で構成され、サブドメインが力がまったく適用されていない場合と同じ形状を呈するという条件で、各サブドメインのコーナー間で個別に補間されます。次に、サブドメイン補正の場合と同じインターフェース力が適用され、サブドメインコーナーでの粗補正の値が検出されます。このようにして、インターフェース力が平均化され、ガラーキン法によって粗い解が求められます。この場合も、サブドメインインターフェースでの粗補正の値は、一般にインターフェース全体で不連続です。

最後に、サブドメイン補正と粗補正が追加され、その合計がサブドメインインターフェイス全体で平均化されます。このとき、以前にサブドメインに力を分散するために使用されたのと同じ重みが使用されます。これにより、サブドメイン間のインターフェイス上の BDDC の出力値が得られます。次に、サブドメイン内部の BDDC 出力の値は、内部補正を繰り返すことによって得られます。

実際の実装では、反復の右辺と初期近似は、サブドメイン内のすべての力がゼロになるように前処理されます。これは、上記のように内部補正を 1 回適用することで行われます。その後、サブドメイン内の力は共役勾配反復中にゼロのままになるため、BDDC の各適用における最初の内部補正は省略できます。

参考文献

^ J.-M. Cros、「Schur 補集合領域分割法の前処理子」、I. Herrera、DE Keyes、OB Widlund 編著『科学と工学における領域分割法』、メキシコ国立自治大学 (UNAM)、メキシコ、2003 年、373 ～ 380 ページ。第 14 回領域分割法に関する国際会議、メキシコ、ココヨック、2002 年 1 月 6 ～ 12 日。
^ CR Dohrmann、「制約付きエネルギー最小化に基づくサブ構造化の前処理」、SIAM J. Sci. Comput.、25 (2003)、pp. 246–258。
^ Y. Fragakis および M. Papadrakakis、「構造力学のための高性能領域分割法のモザイク: 主法と二重法の定式化、相互関係、数値効率」、Comput. Methods Appl. Mech. Engrg.、192 (2003)、pp. 3799–3830。
^ C. Farhat、M. Lesoinne、P. LeTallec、K. Pierson、および D. Rixen、「FETI-DP: デュアルプライマル統合 FETI 法。I. 2 レベル FETI 法のより高速な代替法」、Internat. J. Numer. Methods Engrg.、50 (2001)、pp. 1523–1544。
^ C. Farhat、M. Lesoinne、および K. Pierson、「スケーラブルなデュアルプライマル領域分割法」、Numer. Linear Algebra Appl.、7 (2000)、pp. 687–714。産業用途における大規模スパース行列問題の前処理手法 (ミネアポリス、ミネソタ州、1999 年)。
^ J. MandelとB. Sousedík、「最小限の仮定の下でのBDDCとFETI-DP」、Computing、81 (2007)、pp. 269–280。
^ J. Mandel および CR Dohrmann、「制約とエネルギー最小化によるバランス領域分割の収束」、Numer. Linear Algebra Appl.、10 (2003)、pp. 639–659。
^ J. Mandel、「ドメイン分割のバランス」、Comm. Numer. Methods Engrg.、9 (1993)、pp. 233–241。
^ J. Mandel、CR Dohrmann、R. Tezaur、「制約による主および二重部分構造化法の代数理論」、Appl. Numer. Math.、54 (2005)、pp. 167–193。
^ J. LiとOB Widlund、「FETI-DP、BDDC、およびブロックコレスキー法」、Internat. J. Numer. Methods Engrg.、66 (2006)、pp. 250–271。
^ SC BrennerとL.-Y. Sung、「行列やベクトルを使用しないBDDCとFETI-DP」、Comput. Methods Appl. Mech. Engrg.、196 (2007)、pp. 1429–1435。
^ ル・タレック、パトリック;ヤン・マンデル。 Vidrascu、Marina、プレートとシェルの問題を解決するための Neumann-Neumann 領域分解アルゴリズム。 サイアム J. ヌマーアナル。 35 (1998)、no. 2、836–867

外部リンク

「制約による主部分構造化法と双対部分構造化法の代数理論」に関する Jan Mandel、Clark Dohrmann、Radek Tezaur へのインタビュー
Olof Widlund 氏と Jing Li 氏による「FETI-DP、BDDC、ブロックコレスキー法」に関するインタビュー

[Cros-2003-PSC-1] J.-M. Cros、「Schur 補集合領域分割法の前処理子」、I. Herrera、DE Keyes、OB Widlund 編著『科学と工学における領域分割法』、メキシコ国立自治大学 (UNAM)、メキシコ、2003 年、373 ～ 380 ページ。第 14 回領域分割法に関する国際会議、メキシコ、ココヨック、2002 年 1 月 6 ～ 12 日。

[Dohrmann-2003-PSC-2] CR Dohrmann、「制約付きエネルギー最小化に基づくサブ構造化の前処理」、SIAM J. Sci. Comput.、25 (2003)、pp. 246–258。

[Fragakis-2003-MHP-3] Y. Fragakis および M. Papadrakakis、「構造力学のための高性能領域分割法のモザイク: 主法と二重法の定式化、相互関係、数値効率」、Comput. Methods Appl. Mech. Engrg.、192 (2003)、pp. 3799–3830。

[Farhat-2001-FDP-4] C. Farhat、M. Lesoinne、P. LeTallec、K. Pierson、および D. Rixen、「FETI-DP: デュアルプライマル統合 FETI 法。I. 2 レベル FETI 法のより高速な代替法」、Internat. J. Numer. Methods Engrg.、50 (2001)、pp. 1523–1544。

[Farhat-2000-SDP-5] C. Farhat、M. Lesoinne、および K. Pierson、「スケーラブルなデュアルプライマル領域分割法」、Numer. Linear Algebra Appl.、7 (2000)、pp. 687–714。産業用途における大規模スパース行列問題の前処理手法 (ミネアポリス、ミネソタ州、1999 年)。

[Mandel-2007-BFM-6] J. MandelとB. Sousedík、「最小限の仮定の下でのBDDCとFETI-DP」、Computing、81 (2007)、pp. 269–280。

[Mandel-2003-CBD-7] J. Mandel および CR Dohrmann、「制約とエネルギー最小化によるバランス領域分割の収束」、Numer. Linear Algebra Appl.、10 (2003)、pp. 639–659。

[Mandel-1993-BDD-8] J. Mandel、「ドメイン分割のバランス」、Comm. Numer. Methods Engrg.、9 (1993)、pp. 233–241。

[Mandel-2005-ATP-9] J. Mandel、CR Dohrmann、R. Tezaur、「制約による主および二重部分構造化法の代数理論」、Appl. Numer. Math.、54 (2005)、pp. 167–193。

[Li-2006-FBB-10] J. LiとOB Widlund、「FETI-DP、BDDC、およびブロックコレスキー法」、Internat. J. Numer. Methods Engrg.、66 (2006)、pp. 250–271。

[Brenner-2007-BFW-11] SC BrennerとL.-Y. Sung、「行列やベクトルを使用しないBDDCとFETI-DP」、Comput. Methods Appl. Mech. Engrg.、196 (2007)、pp. 1429–1435。

[12] ル・タレック、パトリック;ヤン・マンデル。 Vidrascu、Marina、プレートとシェルの問題を解決するための Neumann-Neumann 領域分解アルゴリズム。 サイアム J. ヌマーアナル。 35 (1998)、no. 2、836–867