Top > Search of Japanese Patents > (In Japanese)並列有限要素法計算システム

(In Japanese)並列有限要素法計算システム achieved

Patent code P110003091
File No. Q98A1-01-1
Posted date Jun 16, 2011
Application number P2002-571598
Patent number P3824582
Date of filing May 13, 2002
Date of registration Jul 7, 2006
International application number JP2002004617
International publication number WO2002093412
Date of international filing May 13, 2002
Date of international publication Nov 21, 2002
Inventor
  • (In Japanese)秋葉 博
  • (In Japanese)大山 知信
  • (In Japanese)鈴木 正文
Applicant
  • (In Japanese)株式会社アライドエンジニアリング
  • (In Japanese)国立研究開発法人科学技術振興機構
Title (In Japanese)並列有限要素法計算システム achieved
Abstract (In Japanese)超大規模構造問題を解く方法として、領域分割法(DDM)、Neumann前処理つきDMM、BDD法、並列CG法が知られているが、発散して解が求まらない、計算時間が極めて長くなるという問題がある。本発明は、自由度が百万以上の超大規模構造問題を解く際、解が発散することなく求まり、しかも短時間の計算時間で解が求まる、計算パーフォンマンスの高い超大規模構造問題を解くシステムを提供するものである。
自由度100万以上の超大規模構造問題を解く並列有限要素法計算システムであって、領域分割をする手段、部分領域を各プロセッサーの担当する部分へ分配する手段、剛性マトリックスを作成する手段、部分領域全体重ね合わせ運動を設定する手段、全自由度の前処理つき射影CG法の初期設定を行う手段、全自由度の前処理つき射影CG法の反復計算をする手段及び変位解を出力する手段を備えたことを特徴とする並列有限要素法計算システムである。また、該システムを機能させるためのプログラム及び該プログラムを記録したコンピュータ読み取り可能な記録媒体を含む。
Outline of related art and contending technology (In Japanese)


構造問題は、通常次のように扱われる。まず、対象となる構造物を連続体として定式化し、連続体の運動方程式(静的問題の場合は釣合い方程式)を定める。この方程式はほとんどの場合厳密に解くことが不可能であり、数値解析的に解かざるを得ない。そのための連続体問題の離散近似的再定式法が必要となる。その方法の一つとして有限要素法(日本機械学会 計算力学ハンドブック(I 有限要素法 構造編)日本機械学会1998)がある。有限要素法では、まず連続体の占める空間領域を複数の要素(有限要素法の要素)に分割し、非ゼロの値をとる領域が各要素に局在した関数(形状関数)を導入して、連続体変位場をそれらの関数の重ね合わせで表現されるものに限定する近似により、連続体の変位場およびその運動方程式(あるいは釣合い方程式)を離散化する。この離散化により、方程式は一つ(静的線形問題の場合)あるいは複数(例えば非線形問題の場合増分ステップ毎、動的問題の場合時間ステップ毎)の線形方程式に帰着される。有限要素法による連続体領域の要素分割の分割数により線形方程式が扱う自由度(次元)数が異なり、一般に近似をよくするために分割数を増やせば自由度数は増加し、対応する線形方程式の求解の難易度が高まる。
微小変形の静的構造問題は有限要素法においては式1のような、有限次元内積ベクトル空間V上の線形問題に帰着される。
【式1】


ここで、Vは許容変位場(変位場の境界条件を満たすベクトル場)の空間、KはVの次元dimV次剛性マトリクス(正定値対称)、


である。Vの次元dimVは問題の自由度数と等しい。Vの中から式1を満たすベクトルuを探し出すことがソルバの課題になる。
先ず、本発明の基盤となる共役射影勾配法(CPG:Conjugate Projected Gradient Algorithm:C.Farhat F.-X.Roux:Implicit Parallel Processing in Structural Mechanics,Computational Mechanics Advances 2,1-124,1994)について説明する。一般に有限次元内積ベクトル空間V上の線型方程式式2
【式2】


を考える。Kは正定値対称線形変換である。Vの部分空間Yを一つ選ぶ。VをYへK-直交射影するK-直交射影子P(Y)


に条件P(Y)+P(a)=1を満たすK-直交射影子P(a)(P(Y)の補射影子),


Y,V(a)へ式3とK-直交直和分解される。
【式3】


また、P(Y)とP(a)のK-直交性をまとめて書けば式4なので、
【式4】


線形方程式式2は
【式5】




いは uのY-成分P(Y)uとV(a)-成分P(a)uは独立に扱えることになる。つまり方程式式2は独立な2つの方程式式6、式7に式8とK-直交直和分離される。便宜のため、以下Yを直接法空間、YのK-直交補空間となる V(a)を反復法空間と称する。
【式6】


【式7】


【式8】


直接法空間Yの部分空間Wを特別に設定することを考える。このWを以下coarse空間と称する。WのK-直交補空間をfine空間と称する。YをWとWのK-直交補空間WcにK-直交直和分解すれば、方程式式6と同様にW上の方程式式9
【式9】


が設定される。ここでP(W)はWへのK-直交射影子である。こ


設定により定義されている場合、式9は具体的に式10と定式化される。
【式10】


ここで、式11と定義する。
【式11】




ることからくる。
K-直交直和分解した方程式のうち式6を直接法で、式7を反復法で解くことを考える。方程式式7に反復法を適用すると第nステップ反復式が式12、式13と書ける。
【式12】


【式13】




【式14】


【式15】


【式16】




∈KV(a)に注意。このように、K-直交直和分解した方程式のうち片方について前処理付きCG法で解く方法を共役射影勾配法(CPG法)と称する。もう片方の方程式を直接法で解くことも含めて、便宜上以下、これを射影CG法と称する。


のものを直接計算することは不可能だが、P(W+a)は計算可能でWの


式17と書けて、
【式17】




grid問題式18に帰着させる。
【式18】


coarse grid問題は式10の手順にしたがって解くことができる。
CGCG法の特徴づけのため、既存の有限要素法並列ソルバアルゴリズムDDM、BDD法、並列CG法を説明する。以下に述べるとおり、領域分割に基づいた既存の有限要素法並列ソルバアルゴリズムDDM、BDD法は、K-直交直和分解法に基づいた射影CG法の一種とみなせる。以下、有限要素法にしたがい定式化された構造問題の全自由度の空間をVとし、解くべき線形方程式を式19とする。
【式19】


ここで、Kは剛性マトリクスと呼ばれる。
超大規模な(自由度が100万程度以上の)問題を効率的に(特に並列処理で)解くことを目的に考案された方法の一つとして領域分割法(DDM:Domain Decomposition Method)がある。有限要素法により分割された各要素を互いに隣接するもの同士で適当にグループ分けする。各グループの占める空間領域を部分領域(subdomain)と称する(第1図参照)。これにより、全領域がまず部分領域へ分割され、次に各部分領域の有限要素へ分割されるという具合に空間が階層的に分割離散化されることになる。これにしたがい、領域全体に関する処理が各部分領域ごとの処理と部分領域間の処理の2段階に分けられる。特に各部分領域ごとの処理は並列に行なうことができる。上記の処理の2段階分離は具体的には、領域全体の変位場を、部分領域内部に働く外力に応答する部分領域内部の変位場と、部分領域間の境界(内部境界と呼ぶ)上に働く外力に応答する残りの変位場に分けて別々に処理することにより実現している。後者の変位場はさらに部分領域内部の変位場と内部境界上の変位場に分けられ、前者は後者の従属変数になる。独立変数である内部境界の自由度についてはCG法により解く。内部境界について解けば、部分領域内部の変位場はその境界上の変位を境界条件とし負荷ゼロの変位場として定まる。


界Γ,部分領域内部全部の合併領域Ωiおよび内部境界Γsに分け


散化の方法により変わる計算の便宜上設定されるものであり、物理


の許容変位場の自由度の空間Viと内部境界Γs上の許容変位場の自由度の空間Vs直交し、全自由度空間Vは式20のようにViとVsに直交直和分解する。
【式20】




とブロック分解されるが、これに基づき式21とブロック対角化する。
【式21】


SはSchurの補元と呼ばれる。射影子P(i),P(s)を式22と定義する。
【式22】


P(s)は内部境界Γs上の変位場を、それを境界条件とし外力を受け


るから、
【式23】


【式24】


式25となり、
【式25】


P(i),P(s)は条件P(i)+P(s)=1を満たすK-直交射影子である。特に、


式26と
【式26】


K-直交直和分解される。(ViVs)と(V(i)V(s))の関係は式27である。
【式27】




上の反力がゼロであるような変位場の空間であることを示している。一方第3式は、V(s)がΓs上の変位場を幾何的境界条件として持つ


ての2つの特徴づけは等価である。また、射影子P(s)の固有値0に属する固有空間すなわちkerP(s)についてkerP(s)=V(i)=ViだからVsとV(s)は線形同型である。したがってP(s)のVsへの制限Vs→V(s)は線形同型であることがわかる。このことは、V(s)が変数空間である場合、代わりにVsを変数空間にとることができることを示している。
空間及び方程式のK-直交直和分解の直接法空間Yと反復法空間V(a)を式28とおき、
【式28】


式14~式16の前処理行列Gを単位行列G=1ととって射影CG法(J.Mandel,M.Brezina:Balancing Domain Decomposition:Theory and Performance in two and Three Dimensions,MGNet,http://casper.cs.yale.edu/mgnet/www/mgnet-papers.html)を適用したも


自由度の空間、V(s)はΓs上の許容変位場とそれを境界条件(正確


由度の空間を表わす。KV(s)はV(s)の変位場に対応する内部境界上の反力の自由度の空間である。通常のDDMアルゴリズムは上記にしたがいV(s)の代わりにVsを変数空間にとる。
単位行列以外のGを設定することにより前処理つきDDMも可能


とき前処理として有効であるといえる。
DDMのCG法に用いる前処理として、Neumann前処理(P.Le.Tallec:Domain decomposition methods in computationalmechanics,Computational Mechanics Advances 1(2)(1994)121-220)がある。これは上記の前処理行列Gを単位行列1ではなくNeumann前処理行列にとったものである。Neumann前処理行列は各部分領域Iの局所剛性マトリクスKIのSchur補元SI(局


するブロック分解表示で式29で定義される。
【式29】


ここで、Iは領域分割による部分領域のインデクス、NIは部分領域Iの自由度を領域全体の自由度へ写像する0-1成分行列、{DII


い可能性がある。


よって部分領域ごとの不定の剛体変位が反復処理ごとに混入する。これは部分領域ごとにばらばらの浮遊運動を生じさせ、反復収束効


原因でもある。BDD法(Balancing Domain Decomposition method,J.Mandel:Balancing Domain Decomposition,Communications on Numerical Methods in Engineering 9(1993)233-341.,J.Mandel,M.Brezina:Balancing Domain Decomposition:Theory and Performance in Two and Three Dimensions,MGNet,http://casper.cs.yale.edu/mgnet/www/mgnet-papers.html,ARASOL An Integrated Programming Environment for Parallel Sparse Matrix Solvers(Project No.20160),Deliverable D 2.4e Final report Domain Decomposition Algorithms for Large Scale Industrial Finite Element Problems,July 30,1999.)はDDMに基づき、内部境界上の変位について前処理つきCG法を用いて解く解法であり、特に線形材料微小変形の静的問題に関しては、内部境界上に働く外力に応答する変位場を部分領域ごとの剛体変位と残りのひずみ変位とに分け、前者の自由度だけ先に直接法で解き、後者の自由度を次の前処理付きCG法で解くものである。つまり、Neumann前処理に、先に解いた部分領域ごとの剛体変位の自由度の混入を排する射影を反復ごとに追加する。もう少し詳しく述べると、この射影は部分領域にでたらめな浮遊運動を生じさせるような外力を削除するという形で行なわれ、K-直交直和分解された方程式式7、式8でいうとF→F(a)の対応、射影CG法アルゴリズムでいえば残差の射影r→r(a)である。このように、Neumann前処理つきDDMを改善して部分領域ごとの浮遊運動を押さえる上記の射影処理をbalancingと称する。
具体的には、DDMにおける部分空間V(s)=P(s)Vsをさらに次のようにK-直交直和分解する。kerSIを含む部分空間のIにわたる和空間、例えば部分領域ごとの剛体変位を部分領域全部について重ね合わせた運動を考え、その自由度の空間をcoarse空間Wとする。WはV(s)の部分空間である。V(s)をWとそのV(s)でのK-直交補空間V(t)にK-直交直和分解する。対応するK-直交射影子のペアをP(W),P(t)とする。式30が成立する。
【式30】


全自由度空間Vは式31、式32とK-直交直和分解される。
【式31】


【式32】


空間及び方程式のK-直交直和分解の直接法空間と反復法空間を式33とし、
【式33】


式14~式16の前処理行列GをNeumann前処理行列にとって射影CG法(J.Mandel,M.Brezina:Balancing Domain Decomposition:Theory and Performance in Two and Three Dimensions,MGNet,http://casper.cs.yale.edu/mgnet/www/mgnet-papers.html)を適用したものがBDD法である。特に、式17、式18に相当する前処理はP(W+a)=P(s)であることから式34、式35となる。
【式34】


【式35】




BDD法の反復法空間V(t)は同時に、後に局所coarse空間のWIの定義のところで一緒に定義されるbalanced空間でもある。


Decomposition,Communications on Numerical Methods in Engineering 9(1993)233-341.,J.Mandel,M.Brezina:Balancing Domain Decomposition:Theory and Performance in Two and Three Dimensions,MGNet,http://casper.cs.yale.edu/mgnet/www/mgnet-papers.html」。BalancingはBDD法に適用した射影CG法のアルゴリズム式14~式16には直接現われず、K-


る。Neumann前処理行列式29はこの条件を満たし、本節冒頭で提示したNeumann前処理つきDDMの問題点が解決する。
並列CG法は領域分割を行なわず、全自由度空間VをそのままCG法で処理する。VのK-直交直和分解も行なわない。直接法空間をY={0}ととることに相当する。問題が大規模で、ベクトル空間Vの次元が大きい場合は、解析対象の空間領域を幾つかに分割し(これを部分(part)と称する)、それに伴なうVの分解(境界の重複した分解)にしたがって各々の部分空間についての自由度を別々のプロセッサが処理する。ベクトルの内積や行列-ベクトル積のように部分空間相互の情報交換が必要な計算を行なうときに限りプロセス間通信が必要になる。
以上、超大規模構造問題を解く方法として、領域分割法(DDM:Domain Decomposition Method)、Neumann前処理法つきDDM、BDD法(Balancing Domain Decomposition Method)、並列CG法の解法について説明した。しかし、これらの方法では、超大規模構造問題を解く場合、発散して解が求まらない、計算時間が極めて長くなるという問題が指摘されている。本発明は、このような状況に鑑みてなされたもので、自由度が100万以上の超大規模構造問題を解く際、解が発散することなく求まり、反復計算の回数が少なく、短時間の計算時間で解が求まる、超大規模構造問題を解くシステムCGCG法を提供しようとするものである。

Field of industrial application (In Japanese)


本発明は、自由度100万以上の超大規模構造問題を効果的に解く、超大規模並列有限要素法ソルバアルゴリズムに関する。並列CGアルゴリズムを基盤とし、領域分割(Domain Decomposition)に基づく共役射影勾配法アルゴリズムを取入れたものである。当該アルゴリズムを「CGCG法」(Coarse Grid CG method,CGCG method)と称する。Kを当該構造問題の剛性行列とし、領域分割による部分領域単位の自由度の空間をcoarse空間、それにK-直交な補空間をfine空間と称する。CGCG法は、射影としてfine空間へのK-直交射影を採用した共役射影勾配(Conjugate Projected Gradient algorithm:以下射影CG法と称する)を並列処理で行なうものである。

Scope of claims (In Japanese)
【請求項】
 








IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2002571598thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close