TOP > 国内特許検索 > データ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置 > 明細書

明細書 :データ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5066711号 (P5066711)
公開番号 特開2008-186361 (P2008-186361A)
登録日 平成24年8月24日(2012.8.24)
発行日 平成24年11月7日(2012.11.7)
公開日 平成20年8月14日(2008.8.14)
発明の名称または考案の名称 データ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置
国際特許分類 G06F  17/12        (2006.01)
FI G06F 17/12
請求項の数または発明の数 7
全頁数 21
出願番号 特願2007-021230 (P2007-021230)
出願日 平成19年1月31日(2007.1.31)
新規性喪失の例外の表示 特許法第30条第1項適用 1.平成18年7月31日より同年8月2日、社団法人情報処理学会主催の「情報処理学会研究報告2006-HPC-107」において発表 2.平成18年8月24日、社団法人電気学会主催の「静止器回転機合同研究会 電気学会研究会資料」において発表 3.平成18年9月16日より18日、日本応用数理学会主催の「2006年度年会 講演予稿集」において発表 4.平成19年1月17日・18日、社団法人情報処理学会主催の「2007年ハイパフォーマンスコンピューティングと計算科学シンポジウム 論文集」において発表
審査請求日 平成22年1月14日(2010.1.14)
特許権者または実用新案権者 【識別番号】504132272
【氏名又は名称】国立大学法人京都大学
発明者または考案者 【氏名】岩下 武史
【氏名】美舩 健
個別代理人の代理人 【識別番号】100084375、【弁理士】、【氏名又は名称】板谷 康夫
【識別番号】100121692、【弁理士】、【氏名又は名称】田口 勝美
【識別番号】100125221、【弁理士】、【氏名又は名称】水田 愼一
審査官 【審査官】清木 泰
調査した分野 G06F17/12
特許請求の範囲 【請求項1】
コンピュータとマルチグリッド法とを用いて連立一次方程式を解くことにより特定空間領域に分布した未知数データを求めるデータ処理方法であって、
前記特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に前記未知数変数に対する連立一次方程式を生成する式生成工程と、
前記式生成工程によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して1つの連立一次方程式とした大連立方程式を生成する式統合工程と、
前記式統合工程によって生成された大連立方程式を解いて前記未知数を求める解法工程とを備え、
前記式統合工程では、前記粗密度のレベルを整数変数iまたはj(ただし0≦i≦m,0≦j≦m)によって識別し、レベルiのグリッドにおける連立一次方程式の係数行列をAとし、右辺ベクトルをbとし、レベルiのグリッドからレベルi+1のグリッドへの制約演算子をIi+1とし、レベルi+1のグリッドからレベルiのグリッドへの補間演算子をIi+1とし、前記大連立方程式の係数行列をMi,j(0≦i≦m,0≦j≦m)からなるものとし、未知数ベクトルをx(0≦i≦m)からなるものとし、右辺ベクトルをf(0≦i≦m)からなるものとして前記xを求めるとき、前記Mi,jと前記fとが、
i,i=A
i,j=Ai+1i+1i+2・・・Ij-1(ただし、i<jのとき)、
i,j=Ii-1i-1i-2・・・Ij+1(ただし、i>jのとき)、
=Ii-1i-1i-2・・・I(ただし、f=b)、によって与えられることを特徴とするデータ処理方法。
【請求項2】
前記式統合工程では、次の対称性の式、
i+1=(Ii+1(ただし、(*)は行列*の転置行列を表す)、
i+1=Ii+1i+1、を満たすように制約演算子Ii+1と補間演算子Ii+1とを定めることを特徴とする請求項1に記載のデータ処理方法。
【請求項3】
前記解法工程では、前記大連立方程式が反復法によって解かれることを特徴とする請求項1または請求項2に記載のデータ処理方法。
【請求項4】
前記解法工程では、前記大連立方程式が前処理付き反復法によって解かれることを特徴とする請求項1または請求項2に記載のデータ処理方法。
【請求項5】
請求項1乃至請求項4のいずれかに記載のデータ処理方法をコンピュータを用いて実行させるためのプログラム。
【請求項6】
請求項5に記載のプログラムを格納したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項7】
コンピュータとマルチグリッド法とを用いて連立一次方程式を解くことにより特定空間領域に分布した未知数データを求めるデータ処理装置であって、
前記特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に前記未知数変数に対する連立一次方程式を生成する式生成手段と、
前記式生成手段によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して1つの連立一次方程式とした大連立方程式を生成する式統合手段と、
前記式統合手段によって生成された大連立方程式を解いて前記未知数を求める解法手段とを備え、
前記式統合手段では、前記粗密度のレベルを整数変数iまたはj(ただし0≦i≦m,0≦j≦m)によって識別し、レベルiのグリッドにおける連立一次方程式の係数行列をAとし、右辺ベクトルをbとし、レベルiのグリッドからレベルi+1のグリッドへの制約演算子をIi+1とし、レベルi+1のグリッドからレベルiのグリッドへの補間演算子をIi+1とし、前記大連立方程式の係数行列をMi,j(0≦i≦m,0≦j≦m)からなるものとし、未知数ベクトルをx(0≦i≦m)からなるものとし、右辺ベクトルをf(0≦i≦m)からなるものとして前記xを求めるとき、前記Mi,jと前記fとが、
i,i=A
i,j=Ai+1i+1i+2・・・Ij-1(ただし、i<jのとき)、
i,j=Ii-1i-1i-2・・・Ij+1(ただし、i>jのとき)、
=Ii-1i-1i-2・・・I(ただし、f=b)、によって与えられることを特徴とするデータ処理装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、コンピュータとマルチグリッド法とを用いて連立一次方程式の求解を行うデータ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置に関する。
【背景技術】
【0002】
従来から、流体、電磁場、構造(車両、橋梁など)などを対象とする数値シミュレーションや、より一般的に、特定空間領域に分布した未知数データを求める数値計算を行うため、未知数データが現出する空間領域を離散化グリッドによって細分化し、その未知数データの挙動を司る基礎方程式(例えば、物理体系の方程式)を各細分化空間に係る多数の差分方程式に帰着させて解くことが行われている。このような差分方程式は、連立一次方程式とされ、通常、反復法を用いて十分近似された値として近似解が求められる。反復法は、大規模な連立一次方程式を普通に解こうとする場合に計算量が非常に多くなり時間がかかるのを回避するため、近似を繰り返していくことにより速く解を求める手法である。
【0003】
数値計算例として、例えば、有限要素法や境界要素法などがあり、これらの数値解析において、大規模な連立一次方程式が立てられる。このような連立一次方程式を解くプログラムは、しばしばソルバ(solver)と呼ばれる。有限要素法(finite element method)は、構造物の変形や応力などを解析するためによく使われる近似解析手法である。解析の対象となる物体を、三角形や四角形、六角形などの細かい要素に分割し、離散化方程式を生成して全体の挙動を求める。各要素は、単純な形状なので外力が加わった場合の変形などを、反復法を用いて容易にコンピュータで計算できる。
【0004】
反復法に関連する数多くある求解法の中で、現在最も優れている方法の一つがマルチグリッド法である。マルチグリッド法では、最終的に解くべき離散化グリッドに対してより粗いグリッドを構築し、粗密度の異なる複数のグリッドのもとで連立一次方程式の生成を行い、反復求解を繰り返すことにより、近似とその収束とを速めることができる。
【0005】
マルチグリッド法の特徴は、連立一次方程式の単体ソルバとして、また、反復法の前処理として、いずれにも用いられることである。ここで、行列表示したAx=bという連立一次方程式を考える。係数行列Aはn次正方行列であり、解ベクトルx、右辺ベクトルbは、それぞれn次元ベクトルである。マルチグリッド法は、Ax=bの解法として、次の2種類の形態、
(1)マルチグリッド法単体の利用、
(2)マルチグリッド法(前処理の一つとして利用)+反復法、
で用いられる。ここで前処理とは、反復法の収束性を加速する技術であり、マルチグリッド法も前処理用として用いられる。マルチグリッド法によると、解を導出するためのサイクル数が問題のサイズ(未知数の個数)に依存しない性質があり、多くの分野で高速の線形ソルバとして用いられている。
【0006】
マルチグリッド法による求解手順では、細かいグリッドと粗いグリッドの間を行き来しながら、高速に解が求められる。最終的に解くべきグリッド(格子)の他に、より粗いグリッドが準備される。粗いグリッドでは未知数が少ないので、より少ない計算量で連立一次方程式を解くことができる。次々とより粗いグリッドによって解の情報を素早く計算領域全体に伝播させることができるので、元の細かいグリッドで解を求めるのを加速できる。これは、コースグリッドコレクションと呼ばれる。
【0007】
上述のコースグリッドコレクションは、ある物理的な解析領域を対象とした方程式、例えばポアソン方程式を離散化した場合、反復法によって空間的に高周波数成分が効果的に除去されるのに対し、低周波数成分(スムーズな成分)が除去されにくいという性質を改善するものである。
【0008】
つまり、与えられた離散化グリッドに対して、それよりも粗いグリッドを新たに構築し、密なグリッド上で除去されにくい低周波数の誤差成分を粗いグリッド上に写像する。すると、粗いグリッド上からみた場合、これらの誤差成分は高周波数成分として見える。このため、もとの低周波数成分が、反復法によって効果的に除去される。これがコースグリッドコレクションの原理である。
【0009】
与えられたグリッドに対して、粗いグリッドを階層的に構築し、誤差成分をその空間的な波長に応じたグリッド上で除去することにより、与えられた問題の次元数n(未知変数の個数)が増加しても収束までに必要なサイクル数をほとんど増加させることなく解を得ることができる。その結果、理想的な場合には、次元数nの問題に対して、オーダO(n)の計算量で解を求めることができる。
【0010】
上述のような優れたマルチグリッド法の性質から、多くのアプリケーション分野でマルチグリッド法が導入され、数多くの成果を挙げてきた。特にクリロフ部分空間反復法の前処理法としてマルチグリッド法を用いる方法は現時点でもっとも高速な連立一次方程式の解法方法といえる。以下では、コースグリッドコレクションとマルチグリッドサイクルについて詳述する。
【0011】
(コースグリッドコレクション)
解くべきN元連立一次方程式が、次式(1)のように与えられたとする。ここで、AはN次元の正方行列であり、xは解ベクトル、bは右辺ベクトルである。
=b (1)。
【0012】
また、式(1)は、ある領域Ωをグリッド(メッシュ、格子などとも呼ばれる)によって分割し、領域Ωにおける対象とする方程式を離散化して得られるものとする。このグリッドにより離散化された領域をΩと表す。また、Ωや後述のΩなどによってグリッドそのものも表す。係数行列Aは一般に疎行列となる。
【0013】
式(1)をガウス=ザイデル法などの定常反復法で解く場合、以下のような性質が知られている。すなわち、定常反復法では、Ω上の誤差成分のうち空間的に高周波な成分が速く収束するのに対し、空間的に低周波な成分の収束が遅くなる。そこで、上述のように、与えられたグリッドに対してより粗いグリッドを用意し、密なグリッド上で除去しにくい空間的に低周波な誤差成分を粗グリッド上に写像し、コースグリッドコレクションによって、誤差を除去する。
【0014】
具体的なコースグリッドコレクションの手順は以下のように与えられる。まず、なんらかの手段により式(1)の近似解χを得ているとする。このとき、誤差ベクトルe=x-χを定義すると、次式(2)の残差方程式が得られる。ここで、残差r=b-Aχである。
=r (2)。
【0015】
ここで、仮に式(2)が解かれeを得たとすると、x=χ+eのように解ベクトルを修正し、解を得ることができる。ところが、これらの2つの式は同一の係数行列を持ち、両者を解くことは本質的に同じである。そこで、マルチグリッド法では、粗いグリッド上で残差方程式を構築し、それにより得られた誤差ベクトルを用いて解ベクトルを修正する。ここでは簡単のためにΩとΩの2つのグリッドを考える。
【0016】
まず、密なグリッド上の残差rを粗いグリッドΩに写像する。この写像演算子は制約演算子と呼ばれ、Iと表記される。次に、グリッドΩ上で定義される係数行列をAとする。行列Aには任意の行列を用いることが可能であるが、一般的な方法の一つは元の解くべき微分方程式をグリッドΩ上で離散化して得られる方程式の係数行列を用いる方法である。このとき、グリッドΩの残差方程式を次式(3)のように与える。
=b=I (3)。
【0017】
グリッドΩにおける未知変数の個数をNとすると、係数行列AはN次元正方行列で与えられ、制約演算子IはN行N列の行列となる。
【0018】
式(3)を直接法あるいは反復法で解き、eあるいはその近似値εを得た後、この誤差ベクトルをグリッドΩに写像し、解ベクトルの修正値とする。このとき用いられる写像演算子は補間演算子と呼ばれIと表記される。写像演算子Iにより、密なグリッドΩにおける解ベクトルの修正は次式(4)のように表される。
χnew ← χ+Iε (4)。
【0019】
(マルチグリッドサイクル)
実用的なマルチグリッド法では階層的に次第に粗くなる複数のグリッドΩ(n=0,..,k-1)を用意する。ここでkはレベル数と呼ばれる。これらの複数のグリッドに対して、グリッドΩと同様に対象とする方程式を離散化し係数行列A(n=0,..,k-1)を得る。各グリッドレベルnで解かれる方程式を次式(5)のように書く。
=b (n=0,..,k-1) (5)。
【0020】
レベルnで解く方程式はレベルn-1で解かれる方程式の残差方程式をΩ上に写像(マッピング)したものであり、制約演算子In+1(n=0,..,k-1)を用いて右辺ベクトルはbn+1=In+1で与えられる。ここでrはレベルnにおける残差ベクトルである。
【0021】
各レベルnにおいて式(5)によりxの近似値を得るための手段はスムーザと呼ばれ、その操作をスムージングという。スムーザには様々な提案があるが、定常反復法の数反復を用いるのが一般的である。
【0022】
マルチグリッド法ではどのようにレベル間を推移し、誤差を除去していくかで様々な方法がある。最も基本的なVサイクルの場合、1回のマルチグリッドサイクルは以下のように与えられる。
【0023】
今、レベルnにおける解ベクトルの近似値としてχを保持しているとして、その更新を、次式(6)のように表す。
χnew←MV(χ,b) (6)。
【0024】
すると、MV(χ,b)は以下のように再帰的に定義される。
ステップ1:(前置平滑化)A=bに対する平滑化演算によってχを更新、
ステップ2:r=b-Aχを計算、
ステップ3:(リストリクション)bn+1=In+1、更新χn+1=0、
ステップ4:(コースグリッドコレクション)MVn+1(χn+1,bn+1)、
ステップ5:(インタポレーション)更新χ←χ+In+1χn+1
ステップ6:(後置平滑化)A=bに対する平滑化演算によってχを更新。
【0025】
式(6)の表現を使って、1回のマルチグリッドVサイクルはχnew←MV(χ,b)によって表される。
【0026】
上述のように、マルチグリッド法ではマルチグリッドサイクルを繰り返すことにより連立一次方程式の求解を行う。また、マルチグリッド法をクリロフ部分空間反復法の前処理として使用する場合には、前処理としてマルチグリッドサイクルを数回(通常は1回)行う。
【0027】
ここで、マルチグリッド方式を実際に用いる際の改善について述べる。所望の格子上に定義される複数の定義点に対する制約演算/補間演算を用いたマルチグリッド方式における変換操作を容易に行うためにデータ処理方法及びデータ処理装置の提案がなされている。これは、物理体系を表す基礎方程式を細/粗グリッドを用いてコンピュータ内に設定し、当該細/粗グリッドから定義される第1の連立一次元方程式を粗/細グリッドから定義される第2の連立一次元方程式に変換してコンピュータに計算させるマルチグリッド方式を用いたデータ処理を行う際に、細/粗グリッド上の定義点を粗グリッド上の定義点に変換する変換処理を、複数の一次元変換処理に分解し、当該複数の一次元変換処理を一次元ずつ順次行うものである(例えば、特許文献1参照)。
【0028】
また、メッシュ計算に由来する線形行列方程式の解法を高速化するシステムを提供するためのアクセラレータが提案されている。このアクセラレータは、メッシュジェネレータが生成したメッシュに基づいた線形行列方程式を解くアナライザ/ソルバに外部的に接続するライブラリとして使用される。このアクセラレータはN×N線形行列方程式の細密メッシュを受け取り、この細密メッシュに基づいて最適な粗メッシュを算出する。ここでNは細密メッシュにおける結節点の数である。この粗メッシュはアナライザ/ソルバに送られる。アナライザ/ソルバは、N×N線形行列方程式と同等である粗メッシュのM×M線形行列方程式を解く。アクセラレータはM×M線形行列方程式の最初の解を受け取る。すると次にアクセラレータは、粗メッシュの点について解の勾配とヘッセ行列式の最適見積りを用いて、N×N線形行列方程式の第2の解を計算する(例えば、特許文献2参照)。

【特許文献1】特開2006-293488号公報
【特許文献2】特開2002-56038号公報
【発明の開示】
【発明が解決しようとする課題】
【0029】
しかしながら、上述したようなマルチグリッド法に関する技術においては、次のような問題がある。すなわち、マルチグリッド法を単独で用いたり、反復法の前処理法として用いたりする場合、併用できる前処理法が限られたものになっている。マルチグリッド法は、多くの構成要素からなっており、一旦作成したプログラムを変更することは、通常容易でない。一方、世の中には商用またはフリーの前処理付き反復法ライブラリが数多く存在している。このような状況のもとで、マルチグリッド法が、容易に、他の前処理法とともに併用できれば、より有益である。ところが、現状のマルチグリッド法は、反復法の前処理法の一つとして利用することができるものの、他の優れた前処理法との併用が困難である。
【0030】
本発明は、上記課題を解消するものであって、簡単な構成により、他の前処理法との併用を容易に実現できる、マルチグリッド法を用いたデータ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置を提供することを目的とする。
【課題を解決するための手段】
【0031】
上記課題を達成するために、請求項1の発明は、コンピュータとマルチグリッド法とを用いて連立一次方程式を解くことにより特定空間領域に分布した未知数データを求めるデータ処理方法であって、前記特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に前記未知数変数に対する連立一次方程式を生成する式生成工程と、前記式生成工程によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して1つの連立一次方程式とした大連立方程式を生成する式統合工程と、前記式統合工程によって生成された大連立方程式を解いて前記未知数を求める解法工程とを備え、前記式統合工程では、前記粗密度のレベルを整数変数iまたはj(ただし0≦i≦m,0≦j≦m)によって識別し、レベルiのグリッドにおける連立一次方程式の係数行列をAとし、右辺ベクトルをbとし、レベルiのグリッドからレベルi+1のグリッドへの制約演算子をIi+1とし、レベルi+1のグリッドからレベルiのグリッドへの補間演算子をIi+1とし、前記大連立方程式の係数行列をMi,j(0≦i≦m,0≦j≦m)からなるものとし、未知数ベクトルをx(0≦i≦m)からなるものとし、右辺ベクトルをf(0≦i≦m)からなるものとして前記xを求めるとき、前記Mi,jと前記fとが、
i,i=A
i,j=Ai+1i+1i+2・・・Ij-1(ただし、i<jのとき)、
i,j=Ii-1i-1i-2・・・Ij+1(ただし、i>jのとき)、
=Ii-1i-1i-2・・・I(ただし、f=b)、によって与えられるデータ処理方法である。
【0032】
請求項2の発明は、請求項1に記載のデータ処理方法において、前記式統合工程では、次の対称性の式、
i+1=(Ii+1(ただし、(*)は行列*の転置行列を表す)、
i+1=Ii+1i+1、を満たすように制約演算子Ii+1と補間演算子Ii+1とを定めるものである。
【0033】
請求項3の発明は、請求項1または請求項2に記載のデータ処理方法において、前記解法工程では、前記大連立方程式が反復法によって解かれるものである。
【0034】
請求項4の発明は、請求項1または請求項2に記載のデータ処理方法において、前記解法工程では、前記大連立方程式が前処理付き反復法によって解かれるものである。
【0035】
請求項5の発明は、請求項1乃至請求項4のいずれかに記載のデータ処理方法をコンピュータを用いて実行させるためのプログラムである。
【0036】
請求項6の発明は、請求項5に記載のプログラムを格納したコンピュータ読み取り可能な記憶媒体である。
【0037】
請求項7の発明は、コンピュータとマルチグリッド法とを用いて連立一次方程式を解くことにより特定空間領域に分布した未知数データを求めるデータ処理装置であって、前記特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に前記未知数変数に対する連立一次方程式を生成する式生成手段と、前記式生成手段によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して1つの連立一次方程式とした大連立方程式を生成する式統合手段と、前記式統合手段によって生成された大連立方程式を解いて前記未知数を求める解法手段とを備え、前記式統合手段では、前記粗密度のレベルを整数変数iまたはj(ただし0≦i≦m,0≦j≦m)によって識別し、レベルiのグリッドにおける連立一次方程式の係数行列をAとし、右辺ベクトルをbとし、レベルiのグリッドからレベルi+1のグリッドへの制約演算子をIi+1とし、レベルi+1のグリッドからレベルiのグリッドへの補間演算子をIi+1とし、前記大連立方程式の係数行列をMi,j(0≦i≦m,0≦j≦m)からなるものとし、未知数ベクトルをx(0≦i≦m)からなるものとし、右辺ベクトルをf(0≦i≦m)からなるものとして前記xを求めるとき、前記Mi,jと前記fとが、
i,i=A
i,j=Ai+1i+1i+2・・・Ij-1(ただし、i<jのとき)、
i,j=Ii-1i-1i-2・・・Ij+1(ただし、i>jのとき)、
=Ii-1i-1i-2・・・I(ただし、f=b)、によって与えられるデータ処理装置である。
【発明の効果】
【0038】
請求項1の発明によれば、制約演算子と補間演算子とが大連立方程式の中に組み込まれており、補間演算や制約演算を陽的に行わないマルチグリッド法(以下、陰的マルチグリッド法とも呼ぶ)となっているので、様々な前処理法を容易に併用できる。このような前処理法の併用は、従来の補間演算や制約演算を陽的に行っているマルチグリッド法では困難なものであり、この困難を解消できる本発明は、従来のマルチグリッド法の適用範囲を大幅に広げることができる。例えば、マルチグリッド法が組み込まれた大連立方程式を、容易に前処理付きクリロフ部分空間反復法によって解くことができると共に、コースグリッドコレクションの効果を享受できる。すなわち、本発明のデータ処理法に他の前処理法を用いることにより、従来から収束性の点で最も優れた方法であるとされているマルチグリッド法の収束性を、さらに向上できる。
【0039】
また、本発明のデータ処理法によれば、陰的マルチグリッド法による定式化のみでコースグリッドコレクションの効果が組み込まれるので、従来行われているマルチグリッド法におけるサイクル部分の実装の必要がなく、他のソフトウエアライブラリとの連携が容易である。陰的マルチグリッド法では、一旦この手法で定式化すれば、あらゆる前処理付き反復法を適用することが可能となるので、様々な解法を柔軟に試すことができる。これは実用上において大きなメリットとなる。このように、従来のソフトウェアにおけるマルチグリッド法の実装を大幅に簡略化し、かつその適用範囲を大きく広げることができる。また、本発明における大連立方程式において、反復法の収束性に大きく影響する係数行列の固有値分布や条件数が大幅に改善されることが見いだされている。また、本発明のデータ処理法(陰的マルチグリッド)は、ある解析領域において微分方程式の問題を離散化により解く場合に用いられる幾何マルチグリッド法と、この手法を任意の係数行列に対して拡張した代数マルチグリッド(AMG)法のいずれにも適用可能である。
【0040】
請求項2の発明によれば、対称性のある問題に対して計算回数を減らすことができ、データ処理が容易となる。
【0041】
請求項3の発明によれば、様々な実績ある反復法のソフトウエアライブラリを容易かつ安価に入手して用いることができる。
【0042】
請求項4の発明によれば、様々な実績ある前処理法や反復法のソフトウエアライブラリを容易かつ安価に入手して用いることができる。
【0043】
請求項5の発明によれば、本発明のプログラムを用いて種々のコンピュータ上でデータ処理を実行できる。
【0044】
請求項6の発明によれば、本発明の記憶媒体に格納されたプログラムを用いて種々のコンピュータ上でデータ処理を実行できる。
【0045】
請求項7の発明によれば、制約演算子と補間演算子とが大連立方程式の中に組み込まれており、補間演算や制約演算を陽的に行わないマルチグリッド法(以下、陰的マルチグリッド法とも呼ぶ)となっているので、様々な前処理法を容易に併用できる。このような前処理法の併用は、従来の補間演算や制約演算を陽的に行っているマルチグリッド法では困難なものであり、この困難を解消できる本発明は、従来のマルチグリッド法の適用範囲を大幅に広げることができる。例えば、マルチグリッド法が組み込まれた大連立方程式を、容易に前処理付きクリロフ部分空間反復法によって解くことができると共に、コースグリッドコレクションの効果を享受できる。すなわち、本発明のデータ処理法に他の前処理法を用いることにより、従来から収束性の点で最も優れた方法であるとされているマルチグリッド法の収束性を、さらに向上できる。
【0046】
また、本発明のデータ処理装置によれば、陰的マルチグリッド法による定式化のみでコースグリッドコレクションの効果が組み込まれるので、従来行われているマルチグリッド法におけるサイクル部分の実装の必要がなく、他のソフトウエアライブラリとの連携が容易である。陰的マルチグリッド法では、一旦この手法で定式化すれば、あらゆる前処理付き反復法を適用することが可能となるので、様々な解法を柔軟に試すことができる。これは実用上において大きなメリットとなる。このように、従来のソフトウェアにおけるマルチグリッド法の実装を大幅に簡略化し、かつその適用範囲を大きく広げることができる。また、本発明における大連立方程式において、反復法の収束性に大きく影響する係数行列の固有値分布や条件数が大幅に改善されることが見いだされている。また、本発明のデータ処理装置では、ある解析領域において微分方程式の問題を離散化により解く場合に用いられる幾何マルチグリッド法と、この手法を任意の係数行列に対して拡張した代数マルチグリッド(AMG)法のいずれにも対応可能である。
【発明を実施するための最良の形態】
【0047】
以下、本発明の一実施形態に係るデータ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置について、図面を参照して説明する。図1は本発明のデータ処理方法のフローチャートを示し、図2は同データ処理方法における陰的マルチグリッド法の概念を示し、図3(a)(b)(c)は同データ処理方法で用いられる大連立方程式の具体例を示す。
【0048】
本発明のデータ処理方法は、コンピュータと、陰的に包含されたマルチグリッド法とを用いて連立一次方程式を解くことにより、特定空間領域に分布した未知数データを求める方法である。ここで、特定空間領域とは、流体、電磁場、構造(車両、橋梁など)などを対象とする数値シミュレーションや数値解析においては、流体場、電磁場、構造体等が存在する1次元や3次元の実空間の特定領域であり、より一般的な多次元のデータ空間におけるデータ点に対する外乱などへの応答や挙動を調べる場合は、そのデータ空間の特定領域が特定空間領域となる。
【0049】
このデータ処理方法は、図1に示すように、特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に未知数変数に対する連立一次方程式を生成する式生成工程(S1)と、前記式生成工程(S1)によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して1つの連立一次方程式とした大連立方程式を生成する式統合工程(S2)と、前記式統合工程(S2)によって生成された大連立方程式を解いて未知数を求める解法工程(S3)とを備えている。
【0050】
ここで、式統合工程(S2)を説明するために、数学記号を導入する。粗密度のレベルを整数変数iまたはj(ただし0≦i≦m,0≦j≦m)によって識別し、レベルiのグリッドにおける連立一次方程式の係数行列をAとし、右辺ベクトルをbとし、レベルiのグリッドからレベルi+1のグリッドへの制約演算子をIi+1とし、レベルi+1のグリッドからレベルiのグリッドへの補間演算子をIi+1とする。また、大連立方程式の係数行列をMi,j(0≦i≦m,0≦j≦m)からなるものとし、未知数ベクトルをx(0≦i≦m)からなるものとし、右辺ベクトルをf(0≦i≦m)からなるものとする。
【0051】
上述の式統合工程(S2)において、前記大連立方程式のMi,jとfとが、
i,i=A
i,j=Ai+1i+1i+2・・・Ij-1(ただし、i<jのとき)、
i,j=Ii-1i-1i-2・・・Ij+1(ただし、i>jのとき)、
=Ii-1i-1i-2・・・I(ただし、f=b)、によって与えられる。
【0052】
大連立方程式は、上述のMi,j、x、fによって表され、図2に示すように、様々なグリッドレベル(細かいグリッド、粗いグリッド)で立てた各方程式を連立して1つの大きな連立一次方程式(大連立方程式Eq)としたものであり、補間演算子や制約演算子の効果を内部に包含している。従って、この大連立方程式Eqによって定式化された方程式の解法は、補間演算や制約演算を陽的に行わないマルチグリッド法となっている。このような、マルチグリッド法を内包した大連立方程式による解法を、陰的マルチグリッド法と呼ぶことにする。以下、陰的マルチグリッド法についてその詳細を述べる。
【0053】
(陰的マルチグリッド法のフレームワーク)
陰的マルチグリッド法における基本的な考えは、マルチグリッドの各レベルにおける方程式A=b(n=0,..,k-1)を連立し、一つの大きな連立一次方程式として解くことに基づく。この統合化された方程式は、非正則な係数行列を持つ場合があるが、係数行列の値域と右辺ベクトルの間に成り立つ関係から、一般的に、反復法により解を得ることが可能である。
【0054】
まず、ここでは簡単に2レベルの場合について説明する。一般的な2レベルのマルチグリッド法に関する書式とあわせ、レベル0をレベルh(上位レベル)、レベル1をレベルH(下位レベル)と表記し、各ベクトル、行列の上添え字をそれぞれ同様に対応させる。まず、連立して解くべき2つの方程式を次式で与える。
=b (7)、
=b (8)。
【0055】
このままでは、単に2つの方程式を独立に解くことに過ぎないため、これら2つを関連付ける。
【0056】
まず、従来のマルチグリッド法における上位レベルhの解ベクトルの修正について考えると、解ベクトルxはx←x+Iのように修正される。この誤差修正は、式(7)における解として、xではなくx+Iを解として求めることに相当する。そこで、xを導入することにより、式(7)を次式のように書き換えることができる。
+A=b (9)。
【0057】
次に、マルチグリッドの下位レベルHの右辺ベクトルは上位レベルhの残差に制約演算子を施したものであるから、式(8)におけるbは次式のように書ける。
=I(b-A) (10)。
【0058】
これを式(8)に代入し整理すると、次式が得られる。
+A=I (11)。
【0059】
式(9)(11)を連立し、2レベルにおける陰的マルチグリッド法の定式化が、次式のように得られる。
【0060】
【数1】
JP0005066711B2_000002t.gif
(12)。
【0061】
係数行列Aが対称であり、次式(13)(14)が成り立つ場合には、式(12)の係数行列は対称となる。
=(I (13)、
=I (14)。
【0062】
なお、AMG法では式(13)(14)が成り立つように制約演算子と補間演算子とを定めるのが一般的である。
【0063】
次に2以上のグリッドの場合における陰的マルチグリッド法の定式化について説明する。これは帰納的な方法で構築することができる。今、mレベルまでのグリッドを利用した場合の定式化を次式のように表す。ここで、次式(15)の上添え字はマルチグリッドにおける各グリッドのレベルを表す。
【0064】
【数2】
JP0005066711B2_000003t.gif
(15)。
【0065】
ここで、図1に関連して述べたように、粗密度のレベルを整数変数iまたはj(ただし0≦i≦m,0≦j≦m)によって識別し、レベルiのグリッドにおける連立一次方程式の係数行列をAとし、右辺ベクトルをbとし、レベルiのグリッドからレベルi+1のグリッドへの制約演算子をIi+1とし、レベルi+1のグリッドからレベルiのグリッドへの補間演算子をIi+1とする。また、大連立方程式の係数行列をMi,jとし、未知数ベクトルをxとし、右辺ベクトルをfとする。
【0066】
上述のi=0,1,・・・,m、およびj=0,1,・・・,m、は、数字の大きいほど、粗なグリッドに対応し、数字の小さいほど密なグリッドに対応するものとする。この場合、i=0、またはj=0は、最終的に解を求めるためのグリッドであり、最も密なグリッド(細かいグリッド)である。しかしながら、必ずしも、i,jの増加に伴って次第に、一方的に粗なグリッドとなるように決める必要はなく、途中で粗密の度合いが何回か入れ替わるような設定にすることもできる。
【0067】
上述の2レベルにおける定式化から、式(15)について、次式を仮定する。
i,i=A (16)、
i,j=Ai+1i+1i+2・・・Ij-1 (i<j) (17)、
i,j=Ii-1i-1i-2・・・Ij+1 (i>j) (18)、
=Ii-1i-1i-2・・・I (f=b) (19)。
【0068】
このとき、レベルm+1のグリッドが追加された場合を考える。この場合、係数行列にMm+1、m+1,Mi,m+1、およびMm+1、i(但しi=0,1,..,m)が追加され、右辺ベクトルにfm+1の項が追加される。
【0069】
まず、m+1レベルで解く方程式について考えると、係数行列はAm+1で与えられ、右辺ベクトルはmレベルの方程式の残差に制約演算子Im+1を施したものとなる。従って、次式(20)となる。
m+1m+1=Im+1(f-Mm,0-Mm,1・・・-Mm,m) (20)。
【0070】
右辺の括弧内第2項以降を左辺に移項し、式(17)(19)の仮定を使うと、m+1レベルについて次式(21)(22)(23)が得られる。
m+1,m+1=Am+1 (21)、
m+1=Im+1=Im+1m-1・・・I (22)、
m+1,j=Im+1m,j=Im+1m-1・・・Ij+1
(j=0,...,m) (23)。
【0071】
次に、m+1レベルの結果による各レベルの誤差修正について考えると、レベルiにおける解の探索空間がx←x+Ii+1i+1i+2・・・Im+1m+1のように修正されることになる。従って、次式(24)が得られる。
i,m+1=Ai+1i+1i+2・・・Im+1 (i<j)
(i=0,...,m)(24)。
【0072】
式(21)~(24)は式(16)~(19)においてi=m+1としたものに等しく、m=0またはm=1とした場合に式(16)~(19)が成り立つのは式(12)より明らかであるので、帰納的にmレベル陰的マルチグリッド法の定式化が式(15)~(19)により与えられる。
【0073】
上述の統合した連立一次方程式(大連立方程式)の3つの具体例が、図1(a)(b)(c)に示されている。それぞれ順番に、グリッドレベルm=1,2,3について示されている。陰的マルチグリッド法の定式化が、複数のグリッドの場合について帰納的な方法で構築されることが分かる。
【0074】
陰的マルチグリッド法による解法手順は、制約演算子と補間演算子、および各レベルでの係数行列に基づいて式(16)~(19)の各々を計算し、統合化された連立一次方程式(15)を構築した後、これを前処理付き反復法により解くことにより与えられる。
【0075】
なお、上記の手順において制約演算子と補間演算子、および各レベルでの係数行列の生成は幾何マルチグリッド法あるいはAMG法(代数マルチグリッド法)のセットアップ部の手順を用いることができる。AMG法のセットアップ部の手順を用いた場合、ブラックボックス型ソルバとして陰的マルチグリッド法の手法を実装することができる。
【0076】
(陰的マルチグリッド法の効果)
陰的マルチグリッド法では、マルチグリッド法において各レベルで解かれる方程式を統合化し、その統合化した連立一次方程式(大連立方程式)に対して反復法を適用することにより解を得る。通常のマルチグリッド法では明示的にコースグリッドコレクションを行うが、陰的マルチグリッド法では統合化された方程式に対する反復法の残差収束の作用がマルチグリッド法におけるコースグリッドの効果を陰的に含んでいる。
【0077】
予備的な数値実験によると、陰的マルチグリッド法により得られた統合化された係数行列の条件数が元の係数行列と比べて改善されていることが確認された。また、陰的マルチグリッド法において得られる方程式を対称ガウス=ザイデル法で解くことは、その手順が、マルチグリッド法においてプリスムージングとして前進ガウス=ザイデル法を使用し、ポストスムージングとして後退ガウス=ザイデル法を使用したVサイクルの手順と同一であり、解法としても、全く同じになる。
【0078】
従って、陰的マルチグリッド法において定常反復法や定常反復前処理を利用した場合には、マルチグリッド法やマルチグリッド前処理法と同様の効果が得られると考えられる。
【0079】
(電磁場解析とマルチグリッド法)
次に、陰的マルチグリッド法の背景として、電磁場解析とマルチグリッド法の関係について述べる。現在、電磁場解析における主流の解析方法として、磁気ベクトルポテンシャルあるいは電場を未知数とした辺要素有限要素法が挙げられる。特に低周波の電磁場解析では磁気ベクトルポテンシャルを未知変数とした解析が多く用いられる。
【0080】
電磁場解析では、代表的な定式化の手法として、磁気ポテンシャルだけを用いる方法(A法)、および磁気ベクトルポテンシャルと電気スカラポテンシャルを用いる方法(A-φ法)の2つがある。なお、解の一意性のためにはゲージ条件が必要である。また、後者の解法では辺要素と節点要素が併用される。
【0081】
こうした各種の方法の中で、多くの数値解析結果の蓄積から、有限要素法において生ずる連立一次方程式の解法としてICCG法(不完全コレスキー分解前処理付き共役勾配法)を利用した場合、A-φ法による定式化をゲージ条件を科さずに行った場合が最も収束性がよいことが分かってきた。そこで、A-φ定式化が反復法の収束性において有利となる理由について研究が行われている。
【0082】
一方、高周波電磁場解析におけるマルチグリッド法において特殊なスムーザを用いる必要性が示され、具体的にいくつかのスムーザが提案された。例えば、ハイブリッドスムーザや特殊なシュワルツスムーザがその例である。これらのスムーザは辺要素が作る関数空間中において、その離散的な回転が0となるような誤差成分が収束しづらい点に着目し、この誤差成分についてなんらかの対処をする点に特徴がある。
【0083】
一方、この辺要素が作る空間における回転のKernel空間は、電気スカラポテンシャルを節点要素により離散化し、grad演算子を作用させた空間に一致している。つまり、ハイブリッドスムーザやシュワルツスムーザはgradφの空間に属する誤差成分に対してその修正を行う方法であると見做すことができる。
【0084】
そこで、これらの方法の有効性を鑑みると、A-φ定式化はφを導入することで、ベクトルポテンシャルの回転が0となるような誤差成分を除去する効果を内包し、そのことにより収束性の改善を得たのではないかという考えが示された。
【0085】
すなわち、A-φ法の場合には未知変数φを含む連立一次方程式が構築されるが、係数行列のうちφに対応する部分が反復法においてgradφで表現される誤差成分の除去になんらかの寄与をしているという考えである。こうした考えは現時点で未だ定量的な検証に至っていないが、高周波電磁場解析におけるA-φ法の優位性も近年示されてきており、妥当性があると考えられる。
【0086】
(電磁場解析と陰的マルチグリッド法)
上述のような電磁場解析における背景を下に、陰的マルチグリッド法の有効性について述べる。上記において、ベクトルポテンシャルのみを用いて定式化した場合の電磁場解析では、電気スカラポテンシャルのgrad成分に属する誤差が収束しづらく、この成分に対しては別の係数行列を用いることにより全体の収束を加速できることを述べた。
【0087】
ここで、上述の手法で用いられる収束しにくい誤差を別の係数行列により収束させるという概念について考えると、この概念はマルチグリッド法におけるコースグリッドコレクションに類似している。つまり、マルチグリッド法では密なグリッド(元の解くべきグリッド)において除去しにくい誤差成分を、粗いグリッド、すなわち別途生成した係数行列により除去しており、類似性を持っている。
【0088】
通常のマルチグリッド法は、レベル間における誤差の補間、修正を明示的に行うので、上記の考えに沿って電磁場解析に置き換えるとハイブリッドスムーザに相当する。そこで、マルチグリッド法において、電磁場解析におけるA-φ定式化と同様の定式化を試みるのが本提案の陰的マルチグリッド法であり、電磁場解析におけるA-φ定式化の有効性から、この手法もコースグリッドコレクションの効果を内包することが期待される。
【0089】
上述の効果に加え、陰的マルチグリッド法を導入した場合に期待される効果について述べる。従来、マルチグリッド法は単独の線形ソルバあるいは反復法(主にクリロフ部分空間反復法)の前処理法として用いられて効果をあげてきた。特にマルチグリッド法を前処理とする反復法は高速性の点で他の方法を大きく凌駕している。
【0090】
ところが、これらのマルチグリッド法やマルチグリッド前処理法を用いても十分な収束性が得られない場合がある。制約演算子、補間演算子、スムーザ、基本反復法、サイクル形状などに関して多くの選択肢があり、また新たな提案も行われているが十分な成果を挙げていないのが現状である。
【0091】
一方、反復法の前処理技術では、近似逆行列分解前処理、領域分割型前処理など、近年新しい提案が行われているが、マルチグリッド前処理法とこれらの前処理法とを併用することはできない。こうした背景に対して、コースグリッドコレクションを陰的に行う陰的マルチグリッド法では、各グリッドレベルを統合した連立一次方程式(大連立方程式)を解くので、反復法において提案されているあらゆる前処理手法を適用することが可能となる。すなわち、陰的マルチグリッド法の利点は、従来のマルチグリッド法の枠を広げ、数多く提案されている他の前処理手法とコースグリッドコレクションの併用を可能にする点にある。
【0092】
(データ処理装置)
次に、図4を参照して、本発明の他の実施形態に係るデータ処理装置について説明する。データ処理装置1は、コンピュータと、陰的に包含されたマルチグリッド法とを用いて連立一次方程式を解く装置であって、空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に未知数変数に対する連立一次方程式を生成する式生成手段3と、各粗密度のレベル毎に生成された複数の連立一次方程式を統合して1つの連立一次方程式とした大連立方程式を生成する式統合手段4と、生成された大連立方程式を解いて未知数を求める解法手段5とを備えている。
【0093】
データ処理装置1は、さらに、制御手段2と、入出力手段6と、記憶手段7と、を備えている。制御手段2は、入出力手段6を介して入力された問題データや処理条件データを取得し、記憶手段7に記憶し、これらのデータを式生成手段3、式統合手段4、解法手段5に供給すると共に、その動作を制御して未知数を算出させ、その算出結果を入出力手段6から出力する。
【0094】
上述の式生成手段3、式統合手段4、および解法手段5は、前述の図1、図2、図3を参照して説明したデータ処理方法における式生成工程(S1)、式統合工程(S2)、解法工程(S3)の処理を実行する。
【0095】
制御手段2は、通常のコンピュータにおけるCPUやMPUを備えて構成される。入出力手段6は、MO,CD,DVDなどの光媒体や、半導体メモリ媒体に対して読み書きする装置、マウスなどのポインタを用いるGUI、プリンタなどを備えて構成される。
【0096】
式生成手段3、式統合手段4、および解法手段5は、制御手段2が制御するCPUとプログラムメモリとプログラムメモリに取り込まれたソフトウエアなどの総体によって構成される。従って、本データ処理装置1は、CPUやメモリや外部記憶装置や表示装置や入力装置などを備えた一般的な構成を備えた電子計算機、およびその上のプロセス又は機能の集合として構成することができる。
【0097】
(実施例)
次に、陰的マルチグリッド法を用いたデータ処理方法による実施例と比較例とについて説明する。図5に示すように、以下の各式で与えられる2次元ポアソン方程式の境界値問題の差分解析を実施例とし、陰的マルチグリッド法の有効性について述べる。有効性の評価は、収束性によって行う。
(xy領域) 0≦x≦1,0≦y≦1 (25)、
(領域内で) -▽(κ▽u(x,y))=ρ (26)、
(領域境界で) u(x,y)=0 (27)、
(拡散係数) κ=κ (1/4≦x≦3/4 かつ 1/4≦y≦3/4)、
κ=1 (上記以外) (28)。
【0098】
式(26)を5点差分公式により離散化し、得られる連立一次方程式を解く。解析プログラムはMATLABにより記述され、解析はパーソナルコンピュータ上で行われた。
【0099】
(解析結果)
図6乃至図11に解析結果を示す。これらは、解くべき2次元差分格子のサイズと、解析対象の一部領域の拡散係数κと、を変化させた結果である。各図には、6種類の解析手法による結果が示されている。解析手法の識別記号を、次表1に示す。
【0100】
【表1】
JP0005066711B2_000004t.gif

【0101】
CGとICCGは、解くべき差分格子上で得られた連立一次方程式を、それぞれ、CG(共役勾配)法とICCG(不完全コレスキー分解前処理付き共役勾配)法とで解いた結果を示す。
【0102】
iMGと冠されているものは、陰的マルチグリッド定式化を用いた結果である。iMG-SGSは、陰的マルチグリッド法によって統合化された方程式を、対称ガウス=ザイデル法で解くものであり、マルチグリッド法による単体ソルバによる解法と同一である。
【0103】
iMG-CG,iMG-ICCG,iMG-SGSCGは、それぞれ陰的マルチグリッド法によって統合化された方程式を、CG法、ICCG法、対称ガウス=ザイデル前処理付きCG法で解いた結果を示す。
【0104】
図6乃至図9では、一定の拡散係数(κ=1)のもとで、最密のグリッド(解くべき差分格子)のサイズを順番に変えている。それぞれ、図6では15×15、図7では63×63、図8では127×127、図9では255×255としている。
【0105】
図10、図11では、最密のグリッド(解くべき差分格子)のサイズを127×127として、拡散係数を変化させ、図10ではκ=10、図11ではκ=100としている。
【0106】
上述のことから、図6乃至図9におけるx軸の反復回数は、CG,ICCG,iMG-CG,iMG-ICCG,iMG-SGSCGについてはCG法の反復回数を示し、iMG-SGSについては対称ガウス=ザイデル法の反復回数(通常のマルチグリッド単体ソルバにおけるVサイクル数)を示す。また、これらの解法において1反復あたりの計算量は各々異なっていることに留意が必要である。
【0107】
(コースグリッドコレクションの効果)
図6、図7、図8、図9において、CG,ICCGとiMG-CG,iMG-ICCGの結果を比較する。図中において、解くべきグリッドのサイズが増加するにつれて、CG,ICCGの場合には大幅に収束性が悪化している。
【0108】
一方、iMG-CG,iMG-ICCGの場合には、反復回数は多少増加しているものの、CG,ICCGの場合と比較すると収束性はほとんど変わらない。つまり、マルチグリッド法における最も重要な性質であるグリッドサイズによらない収束性、が実現されている。
【0109】
特に、iMG-CGの場合、統合化された方程式をCG法で解いているだけであり、その解法手順には、マルチグリッド法のコースグリッドコレクションに相当する部分が、(陽には)含まれていない。従って、このiMG-CGの結果は、陰的マルチグリッド法の有効性を示すものであり、陰的マルチグリッド法による定式化によって各グリッドレベルの方程式を連立して解くことにより、コースグリッドコレクションの効果が取り入れられることが分かる。
【0110】
(不連続条件)
次に、図9、図10、図11の結果を比較する。これらは、解くべき領域の一部の拡散係数κを変化させた結果である。拡散係数κの増加は、領域内の拡散係数の不連続性の増加を意味し、離散化の結果得られる方程式がより悪条件のもとでの問題となることを意味する。その結果、CG,ICCGの場合だけでなく、元の係数行列を対象とした単体マルチグリッドソルバ(iMG-SGS)においても、収束性が悪化しており、iMG-CGも同様に悪化している。
【0111】
ところが、iMG-ICCGは、拡散係数κを増加した場合においても、高い収束性を維持している。その結果、単体のマルチグリッドソルバとiMG-ICCGとは、図8の条件において同程度の収束性を示していたが、解くべき問題が困難になるに従い、iMG-ICCGの優位性が増している。従って、様々な前処理法との併用が可能な陰的マルチグリッド法は、より悪条件な問題において、単体のマルチグリッドソルバよりも、より高い性能を得ることが可能といえる。
【0112】
(まとめ)
以上に示したように、iMG-SGSCGは、全解析結果を通じて最も優れた収束性を有する。iMG-SGSCGは、その計算手順がMGCG法とほぼ同一であり、その収束特性も同程度と考えられる。MGCG法は、現在、最も高速な連立一次方程式の解法の一つとして知られている。しかし、陰的マルチグリッド法では、前処理法として近似逆行列前処理やILU(k)といったより高度な前処理法を、容易に用いることができるので、これらの前処理法を用いることにより、MGCG法よりも高い収束性を、容易な手順によって、得ることが可能である。
【0113】
また、実装面において、陰的マルチグリッド法には以下のような利点がある。陰的マルチグリッド法では、一旦統合化された方程式(大連立方程式Eq)を構築すれば、解法の対象となるこの方程式は、通常のありふれた連立一次方程式なので、この連立一次方程式に対して、様々な反復法を柔軟に適用することができる。現在、反復法のライブラリ、テンプレートが商用またはフリーのソフトウェアとして利用可能であり、簡単にこれらのリソースを活用することができる。
【0114】
一方、従来のマルチグリッド法においては、例えばスムーザの変更は容易ではない。実際、現在利用可能なマルチグリッドソフトウェアでは、せいぜいいくつかのスムーザのうちから選択できるという機能があるのみであり、より高度なスムーザを実装するのはユーザにとって容易でない。その点、陰的マルチグリッド法では、連立一次方程式を統合化するという形でコースグリッドコレクションを取り込んでおり、コースグリッドコレクションを解法部分から分離できるという点が実用上の大きなメリットとなる。
【0115】
以上、実施形態例を詳述したが、本発明は、例えば、システム、プログラム、または記憶媒体(記録媒体)などとしての実施形態をとることができる。
【0116】
また、本発明のデータ処理方法をコンピュータを用いて実行させるためのプログラムも本発明を実現するものであり、本発明は、プログラムの形態によらずそのプログラムを発明として含む。
【0117】
さらに、本発明のデータ処理方法を実行するために生成した入力用のデータが、既存のコンピュータと既存のソフトウエアによって実行処理されることにより、本発明のデータ処理方法による効果が奏される場合に、当該入力用のデータが本発明のプログラムの一部として本発明に含まれる。
【0118】
本発明は、プログラムを格納したコンピュータ読み取り可能な記憶媒体(記録媒体)も含む。記憶媒体は、例えば、磁気ディスク、光ディスク、光磁気ディスク、磁気テープ、不揮発性のメモリカードなどである。
【0119】
また、コンピュータが読み出したプログラムを実行することによって、上述した実施形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているOSなどが、実際の処理の一部または全部を行い、その処理によっても上述した実施形態の機能が実現される。
【図面の簡単な説明】
【0120】
【図1】本発明の一実施形態に係るデータ処理方法のフローチャート。
【図2】同上データ処理方法における陰的マルチグリッド法の概念説明図。
【図3】(a)(b)(c)は同上データ処理方法で用いられる大連立方程式の具体例の説明図。
【図4】一実施形態に係るデータ処理装置のブロック構成図。
【図5】同上データ処理方法を用いた方程式解法の実施例に関する問題設定の図。
【図6】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較のグラフ。
【図7】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較の他の例におけるグラフ。
【図8】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較のさらに他の例におけるグラフ。
【図9】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較のさらに他の例におけるグラフ。
【図10】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較のさらに他の例におけるグラフ。
【図11】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較のさらに他の例におけるグラフ。
【符号の説明】
【0121】
1 データ処理装置
3 式生成手段
4 式統合手段
5 解法手段
Eq 大連立方程式

図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10