Top > Search of Japanese Patents > DATA PROCESSING METHOD, PROGRAM FOR IT, RECORDING MEDIUM, AND DATA PROCESSING DEVICE

DATA PROCESSING METHOD, PROGRAM FOR IT, RECORDING MEDIUM, AND DATA PROCESSING DEVICE

Patent code P09A014465
File No. 1409
Posted date May 8, 2009
Application number P2007-021230
Publication number P2008-186361A
Patent number P5066711
Date of filing Jan 31, 2007
Date of publication of application Aug 14, 2008
Date of registration Aug 24, 2012
Inventor
  • (In Japanese)岩下 武史
  • (In Japanese)美舩 健
Applicant
  • (In Japanese)国立大学法人京都大学
Title DATA PROCESSING METHOD, PROGRAM FOR IT, RECORDING MEDIUM, AND DATA PROCESSING DEVICE
Abstract PROBLEM TO BE SOLVED: To allow parallel use with another previous processing method by a simple structure in a data processing method, a program for it, a recording medium and a data processing device using a multigrid method.
SOLUTION: The data processing method, which is a method for solving simultaneous linear equations by using a computer and an implicitly included multigrid method, comprises an equation generation process S1, an equation integration process S2, and a solution process S3. In the equation generation process S1, unknown variables are allocated to respective grids under a plurality of grids mutually different in crude density level defined in a spatial area, and simultaneous linear equations for the unknown variables are generated. In the equation integration process S2, large simultaneous equations are generated by integrating a plurality of sets of simultaneous linear equations generated for each crude density level into a single set of simultaneous linear equations. In the solution process S3, the generated large simultaneous equations are solved to find unknowns. The large simultaneous equations uses the multigrid method, in which no interpolating operation nor constraint operation is carried out explicitly, and solutions can be found by using another previous processing method at the same time.
Outline of related art and contending technology (In Japanese)


従来から、流体、電磁場、構造(車両、橋梁など)などを対象とする数値シミュレーションや、より一般的に、特定空間領域に分布した未知数データを求める数値計算を行うため、未知数データが現出する空間領域を離散化グリッドによって細分化し、その未知数データの挙動を司る基礎方程式(例えば、物理体系の方程式)を各細分化空間に係る多数の差分方程式に帰着させて解くことが行われている。このような差分方程式は、連立一次方程式とされ、通常、反復法を用いて十分近似された値として近似解が求められる。反復法は、大規模な連立一次方程式を普通に解こうとする場合に計算量が非常に多くなり時間がかかるのを回避するため、近似を繰り返していくことにより速く解を求める手法である。



数値計算例として、例えば、有限要素法や境界要素法などがあり、これらの数値解析において、大規模な連立一次方程式が立てられる。このような連立一次方程式を解くプログラムは、しばしばソルバ(solver)と呼ばれる。有限要素法(finite element method)は、構造物の変形や応力などを解析するためによく使われる近似解析手法である。解析の対象となる物体を、三角形や四角形、六角形などの細かい要素に分割し、離散化方程式を生成して全体の挙動を求める。各要素は、単純な形状なので外力が加わった場合の変形などを、反復法を用いて容易にコンピュータで計算できる。



反復法に関連する数多くある求解法の中で、現在最も優れている方法の一つがマルチグリッド法である。マルチグリッド法では、最終的に解くべき離散化グリッドに対してより粗いグリッドを構築し、粗密度の異なる複数のグリッドのもとで連立一次方程式の生成を行い、反復求解を繰り返すことにより、近似とその収束とを速めることができる。



マルチグリッド法の特徴は、連立一次方程式の単体ソルバとして、また、反復法の前処理として、いずれにも用いられることである。ここで、行列表示したAx=bという連立一次方程式を考える。係数行列Aはn次正方行列であり、解ベクトルx、右辺ベクトルbは、それぞれn次元ベクトルである。マルチグリッド法は、Ax=bの解法として、次の2種類の形態、
(1)マルチグリッド法単体の利用、
(2)マルチグリッド法(前処理の一つとして利用)+反復法、
で用いられる。ここで前処理とは、反復法の収束性を加速する技術であり、マルチグリッド法も前処理用として用いられる。マルチグリッド法によると、解を導出するためのサイクル数が問題のサイズ(未知数の個数)に依存しない性質があり、多くの分野で高速の線形ソルバとして用いられている。



マルチグリッド法による求解手順では、細かいグリッドと粗いグリッドの間を行き来しながら、高速に解が求められる。最終的に解くべきグリッド(格子)の他に、より粗いグリッドが準備される。粗いグリッドでは未知数が少ないので、より少ない計算量で連立一次方程式を解くことができる。次々とより粗いグリッドによって解の情報を素早く計算領域全体に伝播させることができるので、元の細かいグリッドで解を求めるのを加速できる。これは、コースグリッドコレクションと呼ばれる。



上述のコースグリッドコレクションは、ある物理的な解析領域を対象とした方程式、例えばポアソン方程式を離散化した場合、反復法によって空間的に高周波数成分が効果的に除去されるのに対し、低周波数成分(スムーズな成分)が除去されにくいという性質を改善するものである。



つまり、与えられた離散化グリッドに対して、それよりも粗いグリッドを新たに構築し、密なグリッド上で除去されにくい低周波数の誤差成分を粗いグリッド上に写像する。すると、粗いグリッド上からみた場合、これらの誤差成分は高周波数成分として見える。このため、もとの低周波数成分が、反復法によって効果的に除去される。これがコースグリッドコレクションの原理である。



与えられたグリッドに対して、粗いグリッドを階層的に構築し、誤差成分をその空間的な波長に応じたグリッド上で除去することにより、与えられた問題の次元数n(未知変数の個数)が増加しても収束までに必要なサイクル数をほとんど増加させることなく解を得ることができる。その結果、理想的な場合には、次元数nの問題に対して、オーダO(n)の計算量で解を求めることができる。



上述のような優れたマルチグリッド法の性質から、多くのアプリケーション分野でマルチグリッド法が導入され、数多くの成果を挙げてきた。特にクリロフ部分空間反復法の前処理法としてマルチグリッド法を用いる方法は現時点でもっとも高速な連立一次方程式の解法方法といえる。以下では、コースグリッドコレクションとマルチグリッドサイクルについて詳述する。



(コースグリッドコレクション)
解くべきN0元連立一次方程式が、次式(1)のように与えられたとする。ここで、A0はN0次元の正方行列であり、x0は解ベクトル、b0は右辺ベクトルである。
A0x0=b0 (1)。



また、式(1)は、ある領域Ωをグリッド(メッシュ、格子などとも呼ばれる)によって分割し、領域Ωにおける対象とする方程式を離散化して得られるものとする。このグリッドにより離散化された領域をΩ0と表す。また、Ω0や後述のΩ1などによってグリッドそのものも表す。係数行列A0は一般に疎行列となる。



式(1)をガウス=ザイデル法などの定常反復法で解く場合、以下のような性質が知られている。すなわち、定常反復法では、Ω0上の誤差成分のうち空間的に高周波な成分が速く収束するのに対し、空間的に低周波な成分の収束が遅くなる。そこで、上述のように、与えられたグリッドに対してより粗いグリッドを用意し、密なグリッド上で除去しにくい空間的に低周波な誤差成分を粗グリッド上に写像し、コースグリッドコレクションによって、誤差を除去する。



具体的なコースグリッドコレクションの手順は以下のように与えられる。まず、なんらかの手段により式(1)の近似解χ0を得ているとする。このとき、誤差ベクトルe0=x0-χ0を定義すると、次式(2)の残差方程式が得られる。ここで、残差r0=b0-A0χ0である。
A0e0=r0 (2)。



ここで、仮に式(2)が解かれe0を得たとすると、x0=χ0+e0のように解ベクトルを修正し、解を得ることができる。ところが、これらの2つの式は同一の係数行列を持ち、両者を解くことは本質的に同じである。そこで、マルチグリッド法では、粗いグリッド上で残差方程式を構築し、それにより得られた誤差ベクトルを用いて解ベクトルを修正する。ここでは簡単のためにΩ0とΩ1の2つのグリッドを考える。



まず、密なグリッド上の残差r0を粗いグリッドΩ1に写像する。この写像演算子は制約演算子と呼ばれ、I10と表記される。次に、グリッドΩ1上で定義される係数行列をA1とする。行列A1には任意の行列を用いることが可能であるが、一般的な方法の一つは元の解くべき微分方程式をグリッドΩ1上で離散化して得られる方程式の係数行列を用いる方法である。このとき、グリッドΩ1の残差方程式を次式(3)のように与える。
A1e1=b1=I10r0 (3)。



グリッドΩ1における未知変数の個数をN1とすると、係数行列A1はN1次元正方行列で与えられ、制約演算子I10はN1行N0列の行列となる。



式(3)を直接法あるいは反復法で解き、e1あるいはその近似値ε1を得た後、この誤差ベクトルをグリッドΩ0に写像し、解ベクトルの修正値とする。このとき用いられる写像演算子は補間演算子と呼ばれI01と表記される。写像演算子I01により、密なグリッドΩ0における解ベクトルの修正は次式(4)のように表される。
χ0new ← χ0+I01ε1 (4)。



(マルチグリッドサイクル)
実用的なマルチグリッド法では階層的に次第に粗くなる複数のグリッドΩn(n=0,..,k-1)を用意する。ここでkはレベル数と呼ばれる。これらの複数のグリッドに対して、グリッドΩ0と同様に対象とする方程式を離散化し係数行列An(n=0,..,k-1)を得る。各グリッドレベルnで解かれる方程式を次式(5)のように書く。
Anxn=bn (n=0,..,k-1) (5)。



レベルnで解く方程式はレベルn-1で解かれる方程式の残差方程式をΩn上に写像(マッピング)したものであり、制約演算子In+1n(n=0,..,k-1)を用いて右辺ベクトルはbn+1=In+1nrnで与えられる。ここでrnはレベルnにおける残差ベクトルである。



各レベルnにおいて式(5)によりxnの近似値を得るための手段はスムーザと呼ばれ、その操作をスムージングという。スムーザには様々な提案があるが、定常反復法の数反復を用いるのが一般的である。



マルチグリッド法ではどのようにレベル間を推移し、誤差を除去していくかで様々な方法がある。最も基本的なVサイクルの場合、1回のマルチグリッドサイクルは以下のように与えられる。



今、レベルnにおける解ベクトルの近似値としてχnを保持しているとして、その更新を、次式(6)のように表す。
χnnew←MVn(χn,bn) (6)。



すると、MVn(χn,bn)は以下のように再帰的に定義される。
ステップ1:(前置平滑化)Anxn=bnに対する平滑化演算によってχnを更新、
ステップ2:rn=bn-Anχnを計算、
ステップ3:(リストリクション)bn+1=In+1nrn、更新χn+1=0、
ステップ4:(コースグリッドコレクション)MVn+1(χn+1,bn+1)、
ステップ5:(インタポレーション)更新χn←χn+Inn+1χn+1
ステップ6:(後置平滑化)Anxn=bnに対する平滑化演算によってχnを更新。



式(6)の表現を使って、1回のマルチグリッドVサイクルはχ0new←MV0(χ0,b0)によって表される。



上述のように、マルチグリッド法ではマルチグリッドサイクルを繰り返すことにより連立一次方程式の求解を行う。また、マルチグリッド法をクリロフ部分空間反復法の前処理として使用する場合には、前処理としてマルチグリッドサイクルを数回(通常は1回)行う。



ここで、マルチグリッド方式を実際に用いる際の改善について述べる。所望の格子上に定義される複数の定義点に対する制約演算/補間演算を用いたマルチグリッド方式における変換操作を容易に行うためにデータ処理方法及びデータ処理装置の提案がなされている。これは、物理体系を表す基礎方程式を細/粗グリッドを用いてコンピュータ内に設定し、当該細/粗グリッドから定義される第1の連立一次元方程式を粗/細グリッドから定義される第2の連立一次元方程式に変換してコンピュータに計算させるマルチグリッド方式を用いたデータ処理を行う際に、細/粗グリッド上の定義点を粗グリッド上の定義点に変換する変換処理を、複数の一次元変換処理に分解し、当該複数の一次元変換処理を一次元ずつ順次行うものである(例えば、特許文献1参照)。



また、メッシュ計算に由来する線形行列方程式の解法を高速化するシステムを提供するためのアクセラレータが提案されている。このアクセラレータは、メッシュジェネレータが生成したメッシュに基づいた線形行列方程式を解くアナライザ/ソルバに外部的に接続するライブラリとして使用される。このアクセラレータはN×N線形行列方程式の細密メッシュを受け取り、この細密メッシュに基づいて最適な粗メッシュを算出する。ここでNは細密メッシュにおける結節点の数である。この粗メッシュはアナライザ/ソルバに送られる。アナライザ/ソルバは、N×N線形行列方程式と同等である粗メッシュのM×M線形行列方程式を解く。アクセラレータはM×M線形行列方程式の最初の解を受け取る。すると次にアクセラレータは、粗メッシュの点について解の勾配とヘッセ行列式の最適見積りを用いて、N×N線形行列方程式の第2の解を計算する(例えば、特許文献2参照)。
【特許文献1】
特開2006-293488号公報
【特許文献2】
特開2002-56038号公報

Field of industrial application (In Japanese)


本発明は、コンピュータとマルチグリッド法とを用いて連立一次方程式の求解を行うデータ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置に関する。

Scope of claims (In Japanese)
【請求項1】
 
コンピュータとマルチグリッド法とを用いて連立一次方程式を解くことにより特定空間領域に分布した未知数データを求めるデータ処理方法であって、
前記特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に前記未知数変数に対する連立一次方程式を生成する式生成工程と、
前記式生成工程によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して1つの連立一次方程式とした大連立方程式を生成する式統合工程と、
前記式統合工程によって生成された大連立方程式を解いて前記未知数を求める解法工程とを備え、
前記式統合工程では、前記粗密度のレベルを整数変数iまたはj(ただし0≦i≦m,0≦j≦m)によって識別し、レベルiのグリッドにおける連立一次方程式の係数行列をAiとし、右辺ベクトルをbiとし、レベルiのグリッドからレベルi+1のグリッドへの制約演算子をIi+1iとし、レベルi+1のグリッドからレベルiのグリッドへの補間演算子をIii+1とし、前記大連立方程式の係数行列をMi,j(0≦i≦m,0≦j≦m)からなるものとし、未知数ベクトルをxi(0≦i≦m)からなるものとし、右辺ベクトルをfi(0≦i≦m)からなるものとして前記xiを求めるとき、前記Mi,jと前記fiとが、
Mi,i=Ai
Mi,j=AiIii+1Ii+1i+2・・・Ij-1j(ただし、i<jのとき)、
Mi,j=Iii-1Ii-1i-2・・・Ij+1jAj(ただし、i>jのとき)、
fi=Iii-1Ii-1i-2・・・I10b0(ただし、f0=b0)、によって与えられることを特徴とするデータ処理方法。

【請求項2】
 
前記式統合工程では、次の対称性の式、
Iii+1=(Iii+1T(ただし、(*)Tは行列*の転置行列を表す)、
Ai+1=Ii+1iAiIii+1、を満たすように制約演算子Ii+1iと補間演算子Iii+1とを定めることを特徴とする請求項1に記載のデータ処理方法。

【請求項3】
 
前記解法工程では、前記大連立方程式が反復法によって解かれることを特徴とする請求項1または請求項2に記載のデータ処理方法。

【請求項4】
 
前記解法工程では、前記大連立方程式が前処理付き反復法によって解かれることを特徴とする請求項1または請求項2に記載のデータ処理方法。

【請求項5】
 
請求項1乃至請求項4のいずれかに記載のデータ処理方法をコンピュータを用いて実行させるためのプログラム。

【請求項6】
 
請求項5に記載のプログラムを格納したことを特徴とするコンピュータ読み取り可能な記憶媒体。

【請求項7】
 
コンピュータとマルチグリッド法とを用いて連立一次方程式を解くことにより特定空間領域に分布した未知数データを求めるデータ処理装置であって、
前記特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に前記未知数変数に対する連立一次方程式を生成する式生成手段と、
前記式生成手段によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して1つの連立一次方程式とした大連立方程式を生成する式統合手段と、
前記式統合手段によって生成された大連立方程式を解いて前記未知数を求める解法手段とを備え、
前記式統合手段では、前記粗密度のレベルを整数変数iまたはj(ただし0≦i≦m,0≦j≦m)によって識別し、レベルiのグリッドにおける連立一次方程式の係数行列をAiとし、右辺ベクトルをbiとし、レベルiのグリッドからレベルi+1のグリッドへの制約演算子をIi+1iとし、レベルi+1のグリッドからレベルiのグリッドへの補間演算子をIii+1とし、前記大連立方程式の係数行列をMi,j(0≦i≦m,0≦j≦m)からなるものとし、未知数ベクトルをxi(0≦i≦m)からなるものとし、右辺ベクトルをfi(0≦i≦m)からなるものとして前記xiを求めるとき、前記Mi,jと前記fiとが、
Mi,i=Ai
Mi,j=AiIii+1Ii+1i+2・・・Ij-1j(ただし、i<jのとき)、
Mi,j=Iii-1Ii-1i-2・・・Ij+1jAj(ただし、i>jのとき)、
fi=Iii-1Ii-1i-2・・・I10b0(ただし、f0=b0)、によって与えられることを特徴とするデータ処理装置。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

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


PAGE TOP

close
close
close
close
close
close
close