(57)【要約】【課題】マルチグリッド法を用いたデータ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置において、簡単な構成により、他の前処理法との容易な併用を可能とする。【解決手段】データ処理方法は、コンピュータと、陰的に包含されたマルチグリッド法とを用いて連立一次方程式を解く方法であって、空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に未知数変数に対する連立一次方程式を生成する式生成工程（Ｓ１）と、各粗密度のレベル毎に生成された複数の連立一次方程式を統合して１つの連立一次方程式とした大連立方程式を生成する式統合工程（Ｓ２）と、生成された大連立方程式を解いて未知数を求める解法工程（Ｓ３）とを備えている。大連立方程式は、補間演算や制約演算を陽的に行わないマルチグリッド法となっており、他の前処理法を併用して求解を行うことができる。【選択図】図１
2008186361.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータとマルチグリッド法とを用いて連立一次方程式を解くことにより特定空間領域に分布した未知数データを求めるデータ処理方法であって、
前記特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に前記未知数変数に対する連立一次方程式を生成する式生成工程と、
前記式生成工程によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して１つの連立一次方程式とした大連立方程式を生成する式統合工程と、
前記式統合工程によって生成された大連立方程式を解いて前記未知数を求める解法工程とを備え、
前記式統合工程では、前記粗密度のレベルを整数変数ｉまたはｊ（ただし０≦ｉ≦ｍ，０≦ｊ≦ｍ）によって識別し、レベルｉのグリッドにおける連立一次方程式の係数行列をＡｉとし、右辺ベクトルをｂｉとし、レベルｉのグリッドからレベルｉ＋１のグリッドへの制約演算子をＩｉ＋１ｉとし、レベルｉ＋１のグリッドからレベルｉのグリッドへの補間演算子をＩｉｉ＋１とし、前記大連立方程式の係数行列をＭｉ，ｊとし、未知数ベクトルをｘｉとし、右辺ベクトルをｆｉとして前記ｘｉを求めるとき、前記Ｍｉ，ｊと前記ｆｉとが、
Ｍｉ，ｉ＝Ａｉ、
Ｍｉ，ｊ＝ＡｉＩｉｉ＋１Ｉｉ＋１ｉ＋２・・・Ｉｊ−１ｊ（ただし、ｉ＜ｊのとき）、
Ｍｉ，ｊ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉｊ＋１ｊＡｊ（ただし、ｉ＞ｊのとき）、
ｆｉ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉ１０ｂ０（ただし、ｆ０＝ｂ０）、によって与えられることを特徴とするデータ処理方法。
【請求項２】
前記式統合工程では、次の対称性の式、
Ｉｉｉ＋１＝（Ｉｉｉ＋１）Ｔ（ただし、（＊）Ｔは行列＊の転置行列を表す）、
Ａｉ＋１＝Ｉｉ＋１ｉＡｉＩｉｉ＋１、を満たすように制約演算子Ｉｉ＋１ｉと補間演算子Ｉｉｉ＋１とを定めることを特徴とする請求項１に記載のデータ処理方法。
【請求項３】
前記解法工程では、前記大連立方程式が反復法によって解かれることを特徴とする請求項１または請求項２に記載のデータ処理方法。
【請求項４】
前記解法工程では、前記大連立方程式が前処理付き反復法によって解かれることを特徴とする請求項１または請求項２に記載のデータ処理方法。
【請求項５】
請求項１乃至請求項４のいずれかに記載のデータ処理方法をコンピュータを用いて実行させるためのプログラム。
【請求項６】
請求項５に記載のプログラムを格納したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項７】
コンピュータとマルチグリッド法とを用いて連立一次方程式を解くことにより特定空間領域に分布した未知数データを求めるデータ処理装置であって、
前記特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に前記未知数変数に対する連立一次方程式を生成する式生成手段と、
前記式生成手段によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して１つの連立一次方程式とした大連立方程式を生成する式統合手段と、
前記式統合手段によって生成された大連立方程式を解いて前記未知数を求める解法手段とを備え、
前記式統合手段では、前記粗密度のレベルを整数変数ｉまたはｊ（ただし０≦ｉ≦ｍ，０≦ｊ≦ｍ）によって識別し、レベルｉのグリッドにおける連立一次方程式の係数行列をＡｉとし、右辺ベクトルをｂｉとし、レベルｉのグリッドからレベルｉ＋１のグリッドへの制約演算子をＩｉ＋１ｉとし、レベルｉ＋１のグリッドからレベルｉのグリッドへの補間演算子をＩｉｉ＋１とし、前記大連立方程式の係数行列をＭｉ，ｊとし、未知数ベクトルをｘｉとし、右辺ベクトルをｆｉとして前記ｘｉを求めるとき、前記Ｍｉ，ｊと前記ｆｉとが、
Ｍｉ，ｉ＝Ａｉ、
Ｍｉ，ｊ＝ＡｉＩｉｉ＋１Ｉｉ＋１ｉ＋２・・・Ｉｊ−１ｊ（ただし、ｉ＜ｊのとき）、
Ｍｉ，ｊ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉｊ＋１ｊＡｊ（ただし、ｉ＞ｊのとき）、
ｆｉ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉ１０ｂ０（ただし、ｆ０＝ｂ０）、によって与えられることを特徴とするデータ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータとマルチグリッド法とを用いて連立一次方程式の求解を行うデータ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置に関する。
【背景技術】
【０００２】
従来から、流体、電磁場、構造（車両、橋梁など）などを対象とする数値シミュレーションや、より一般的に、特定空間領域に分布した未知数データを求める数値計算を行うため、未知数データが現出する空間領域を離散化グリッドによって細分化し、その未知数データの挙動を司る基礎方程式（例えば、物理体系の方程式）を各細分化空間に係る多数の差分方程式に帰着させて解くことが行われている。このような差分方程式は、連立一次方程式とされ、通常、反復法を用いて十分近似された値として近似解が求められる。反復法は、大規模な連立一次方程式を普通に解こうとする場合に計算量が非常に多くなり時間がかかるのを回避するため、近似を繰り返していくことにより速く解を求める手法である。
【０００３】
数値計算例として、例えば、有限要素法や境界要素法などがあり、これらの数値解析において、大規模な連立一次方程式が立てられる。このような連立一次方程式を解くプログラムは、しばしばソルバ（ｓｏｌｖｅｒ）と呼ばれる。有限要素法（ｆｉｎｉｔｅ  ｅｌｅｍｅｎｔ  ｍｅｔｈｏｄ）は、構造物の変形や応力などを解析するためによく使われる近似解析手法である。解析の対象となる物体を、三角形や四角形、六角形などの細かい要素に分割し、離散化方程式を生成して全体の挙動を求める。各要素は、単純な形状なので外力が加わった場合の変形などを、反復法を用いて容易にコンピュータで計算できる。
【０００４】
反復法に関連する数多くある求解法の中で、現在最も優れている方法の一つがマルチグリッド法である。マルチグリッド法では、最終的に解くべき離散化グリッドに対してより粗いグリッドを構築し、粗密度の異なる複数のグリッドのもとで連立一次方程式の生成を行い、反復求解を繰り返すことにより、近似とその収束とを速めることができる。
【０００５】
マルチグリッド法の特徴は、連立一次方程式の単体ソルバとして、また、反復法の前処理として、いずれにも用いられることである。ここで、行列表示したＡｘ＝ｂという連立一次方程式を考える。係数行列Ａはｎ次正方行列であり、解ベクトルｘ、右辺ベクトルｂは、それぞれｎ次元ベクトルである。マルチグリッド法は、Ａｘ＝ｂの解法として、次の２種類の形態、
（１）マルチグリッド法単体の利用、
（２）マルチグリッド法（前処理の一つとして利用）＋反復法、
で用いられる。ここで前処理とは、反復法の収束性を加速する技術であり、マルチグリッド法も前処理用として用いられる。マルチグリッド法によると、解を導出するためのサイクル数が問題のサイズ（未知数の個数）に依存しない性質があり、多くの分野で高速の線形ソルバとして用いられている。
【０００６】
マルチグリッド法による求解手順では、細かいグリッドと粗いグリッドの間を行き来しながら、高速に解が求められる。最終的に解くべきグリッド（格子）の他に、より粗いグリッドが準備される。粗いグリッドでは未知数が少ないので、より少ない計算量で連立一次方程式を解くことができる。次々とより粗いグリッドによって解の情報を素早く計算領域全体に伝播させることができるので、元の細かいグリッドで解を求めるのを加速できる。これは、コースグリッドコレクションと呼ばれる。
【０００７】
上述のコースグリッドコレクションは、ある物理的な解析領域を対象とした方程式、例えばポアソン方程式を離散化した場合、反復法によって空間的に高周波数成分が効果的に除去されるのに対し、低周波数成分（スムーズな成分）が除去されにくいという性質を改善するものである。
【０００８】
つまり、与えられた離散化グリッドに対して、それよりも粗いグリッドを新たに構築し、密なグリッド上で除去されにくい低周波数の誤差成分を粗いグリッド上に写像する。すると、粗いグリッド上からみた場合、これらの誤差成分は高周波数成分として見える。このため、もとの低周波数成分が、反復法によって効果的に除去される。これがコースグリッドコレクションの原理である。
【０００９】
与えられたグリッドに対して、粗いグリッドを階層的に構築し、誤差成分をその空間的な波長に応じたグリッド上で除去することにより、与えられた問題の次元数ｎ（未知変数の個数）が増加しても収束までに必要なサイクル数をほとんど増加させることなく解を得ることができる。その結果、理想的な場合には、次元数ｎの問題に対して、オーダＯ（ｎ）の計算量で解を求めることができる。
【００１０】
上述のような優れたマルチグリッド法の性質から、多くのアプリケーション分野でマルチグリッド法が導入され、数多くの成果を挙げてきた。特にクリロフ部分空間反復法の前処理法としてマルチグリッド法を用いる方法は現時点でもっとも高速な連立一次方程式の解法方法といえる。以下では、コースグリッドコレクションとマルチグリッドサイクルについて詳述する。
【００１１】
（コースグリッドコレクション）
解くべきＮ０元連立一次方程式が、次式（１）のように与えられたとする。ここで、Ａ０はＮ０次元の正方行列であり、ｘ０は解ベクトル、ｂ０は右辺ベクトルである。
Ａ０ｘ０＝ｂ０  （１）。
【００１２】
また、式（１）は、ある領域Ωをグリッド（メッシュ、格子などとも呼ばれる）によって分割し、領域Ωにおける対象とする方程式を離散化して得られるものとする。このグリッドにより離散化された領域をΩ０と表す。また、Ω０や後述のΩ１などによってグリッドそのものも表す。係数行列Ａ０は一般に疎行列となる。
【００１３】
式（１）をガウス＝ザイデル法などの定常反復法で解く場合、以下のような性質が知られている。すなわち、定常反復法では、Ω０上の誤差成分のうち空間的に高周波な成分が速く収束するのに対し、空間的に低周波な成分の収束が遅くなる。そこで、上述のように、与えられたグリッドに対してより粗いグリッドを用意し、密なグリッド上で除去しにくい空間的に低周波な誤差成分を粗グリッド上に写像し、コースグリッドコレクションによって、誤差を除去する。
【００１４】
具体的なコースグリッドコレクションの手順は以下のように与えられる。まず、なんらかの手段により式（１）の近似解χ０を得ているとする。このとき、誤差ベクトルｅ０＝ｘ０−χ０を定義すると、次式（２）の残差方程式が得られる。ここで、残差ｒ０＝ｂ０−Ａ０χ０である。
Ａ０ｅ０＝ｒ０  （２）。
【００１５】
ここで、仮に式（２）が解かれｅ０を得たとすると、ｘ０＝χ０＋ｅ０のように解ベクトルを修正し、解を得ることができる。ところが、これらの２つの式は同一の係数行列を持ち、両者を解くことは本質的に同じである。そこで、マルチグリッド法では、粗いグリッド上で残差方程式を構築し、それにより得られた誤差ベクトルを用いて解ベクトルを修正する。ここでは簡単のためにΩ０とΩ１の２つのグリッドを考える。
【００１６】
まず、密なグリッド上の残差ｒ０を粗いグリッドΩ１に写像する。この写像演算子は制約演算子と呼ばれ、Ｉ１０と表記される。次に、グリッドΩ１上で定義される係数行列をＡ１とする。行列Ａ１には任意の行列を用いることが可能であるが、一般的な方法の一つは元の解くべき微分方程式をグリッドΩ１上で離散化して得られる方程式の係数行列を用いる方法である。このとき、グリッドΩ１の残差方程式を次式（３）のように与える。
Ａ１ｅ１＝ｂ１＝Ｉ１０ｒ０  （３）。
【００１７】
グリッドΩ１における未知変数の個数をＮ１とすると、係数行列Ａ１はＮ１次元正方行列で与えられ、制約演算子Ｉ１０はＮ１行Ｎ０列の行列となる。
【００１８】
式（３）を直接法あるいは反復法で解き、ｅ１あるいはその近似値ε１を得た後、この誤差ベクトルをグリッドΩ０に写像し、解ベクトルの修正値とする。このとき用いられる写像演算子は補間演算子と呼ばれＩ０１と表記される。写像演算子Ｉ０１により、密なグリッドΩ０における解ベクトルの修正は次式（４）のように表される。
χ０ｎｅｗ  ←  χ０＋Ｉ０１ε１  （４）。
【００１９】
（マルチグリッドサイクル）
実用的なマルチグリッド法では階層的に次第に粗くなる複数のグリッドΩｎ（ｎ＝０，．．，ｋ−１）を用意する。ここでｋはレベル数と呼ばれる。これらの複数のグリッドに対して、グリッドΩ０と同様に対象とする方程式を離散化し係数行列Ａｎ（ｎ＝０，．．，ｋ−１）を得る。各グリッドレベルｎで解かれる方程式を次式（５）のように書く。
Ａｎｘｎ＝ｂｎ    （ｎ＝０，．．，ｋ−１）  （５）。
【００２０】
レベルｎで解く方程式はレベルｎ−１で解かれる方程式の残差方程式をΩｎ上に写像（マッピング）したものであり、制約演算子Ｉｎ＋１ｎ（ｎ＝０，．．，ｋ−１）を用いて右辺ベクトルはｂｎ＋１＝Ｉｎ＋１ｎｒｎで与えられる。ここでｒｎはレベルｎにおける残差ベクトルである。
【００２１】
各レベルｎにおいて式（５）によりｘｎの近似値を得るための手段はスムーザと呼ばれ、その操作をスムージングという。スムーザには様々な提案があるが、定常反復法の数反復を用いるのが一般的である。
【００２２】
マルチグリッド法ではどのようにレベル間を推移し、誤差を除去していくかで様々な方法がある。最も基本的なＶサイクルの場合、１回のマルチグリッドサイクルは以下のように与えられる。
【００２３】
今、レベルｎにおける解ベクトルの近似値としてχｎを保持しているとして、その更新を、次式（６）のように表す。
χｎｎｅｗ←ＭＶｎ（χｎ，ｂｎ）  （６）。
【００２４】
すると、ＭＶｎ（χｎ，ｂｎ）は以下のように再帰的に定義される。
ステップ１：（前置平滑化）Ａｎｘｎ＝ｂｎに対する平滑化演算によってχｎを更新、
ステップ２：ｒｎ＝ｂｎ−Ａｎχｎを計算、
ステップ３：（リストリクション）ｂｎ＋１＝Ｉｎ＋１ｎｒｎ、更新χｎ＋１＝０、
ステップ４：（コースグリッドコレクション）ＭＶｎ＋１（χｎ＋１，ｂｎ＋１）、
ステップ５：（インタポレーション）更新χｎ←χｎ＋Ｉｎｎ＋１χｎ＋１、
ステップ６：（後置平滑化）Ａｎｘｎ＝ｂｎに対する平滑化演算によってχｎを更新。
【００２５】
式（６）の表現を使って、１回のマルチグリッドＶサイクルはχ０ｎｅｗ←ＭＶ０（χ０，ｂ０）によって表される。
【００２６】
上述のように、マルチグリッド法ではマルチグリッドサイクルを繰り返すことにより連立一次方程式の求解を行う。また、マルチグリッド法をクリロフ部分空間反復法の前処理として使用する場合には、前処理としてマルチグリッドサイクルを数回（通常は１回）行う。
【００２７】
ここで、マルチグリッド方式を実際に用いる際の改善について述べる。所望の格子上に定義される複数の定義点に対する制約演算／補間演算を用いたマルチグリッド方式における変換操作を容易に行うためにデータ処理方法及びデータ処理装置の提案がなされている。これは、物理体系を表す基礎方程式を細／粗グリッドを用いてコンピュータ内に設定し、当該細／粗グリッドから定義される第１の連立一次元方程式を粗／細グリッドから定義される第２の連立一次元方程式に変換してコンピュータに計算させるマルチグリッド方式を用いたデータ処理を行う際に、細／粗グリッド上の定義点を粗グリッド上の定義点に変換する変換処理を、複数の一次元変換処理に分解し、当該複数の一次元変換処理を一次元ずつ順次行うものである（例えば、特許文献１参照）。
【００２８】
また、メッシュ計算に由来する線形行列方程式の解法を高速化するシステムを提供するためのアクセラレータが提案されている。このアクセラレータは、メッシュジェネレータが生成したメッシュに基づいた線形行列方程式を解くアナライザ／ソルバに外部的に接続するライブラリとして使用される。このアクセラレータはＮ×Ｎ線形行列方程式の細密メッシュを受け取り、この細密メッシュに基づいて最適な粗メッシュを算出する。ここでＮは細密メッシュにおける結節点の数である。この粗メッシュはアナライザ／ソルバに送られる。アナライザ／ソルバは、Ｎ×Ｎ線形行列方程式と同等である粗メッシュのＭ×Ｍ線形行列方程式を解く。アクセラレータはＭ×Ｍ線形行列方程式の最初の解を受け取る。すると次にアクセラレータは、粗メッシュの点について解の勾配とヘッセ行列式の最適見積りを用いて、Ｎ×Ｎ線形行列方程式の第２の解を計算する（例えば、特許文献２参照）。
【特許文献１】特開２００６−２９３４８８号公報
【特許文献２】特開２００２−５６０３８号公報
【発明の開示】
【発明が解決しようとする課題】
【００２９】
しかしながら、上述したようなマルチグリッド法に関する技術においては、次のような問題がある。すなわち、マルチグリッド法を単独で用いたり、反復法の前処理法として用いたりする場合、併用できる前処理法が限られたものになっている。マルチグリッド法は、多くの構成要素からなっており、一旦作成したプログラムを変更することは、通常容易でない。一方、世の中には商用またはフリーの前処理付き反復法ライブラリが数多く存在している。このような状況のもとで、マルチグリッド法が、容易に、他の前処理法とともに併用できれば、より有益である。ところが、現状のマルチグリッド法は、反復法の前処理法の一つとして利用することができるものの、他の優れた前処理法との併用が困難である。
【００３０】
本発明は、上記課題を解消するものであって、簡単な構成により、他の前処理法との併用を容易に実現できる、マルチグリッド法を用いたデータ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置を提供することを目的とする。
【課題を解決するための手段】
【００３１】
上記課題を達成するために、請求項１の発明は、コンピュータとマルチグリッド法とを用いて連立一次方程式を解くことにより特定空間領域に分布した未知数データを求めるデータ処理方法であって、前記特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に前記未知数変数に対する連立一次方程式を生成する式生成工程と、前記式生成工程によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して１つの連立一次方程式とした大連立方程式を生成する式統合工程と、前記式統合工程によって生成された大連立方程式を解いて前記未知数を求める解法工程とを備え、前記式統合工程では、前記粗密度のレベルを整数変数ｉまたはｊ（ただし０≦ｉ≦ｍ，０≦ｊ≦ｍ）によって識別し、レベルｉのグリッドにおける連立一次方程式の係数行列をＡｉとし、右辺ベクトルをｂｉとし、レベルｉのグリッドからレベルｉ＋１のグリッドへの制約演算子をＩｉ＋１ｉとし、レベルｉ＋１のグリッドからレベルｉのグリッドへの補間演算子をＩｉｉ＋１とし、前記大連立方程式の係数行列をＭｉ，ｊとし、未知数ベクトルをｘｉとし、右辺ベクトルをｆｉとして前記ｘｉを求めるとき、前記Ｍｉ，ｊと前記ｆｉとが、
Ｍｉ，ｉ＝Ａｉ、
Ｍｉ，ｊ＝ＡｉＩｉｉ＋１Ｉｉ＋１ｉ＋２・・・Ｉｊ−１ｊ（ただし、ｉ＜ｊのとき）、
Ｍｉ，ｊ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉｊ＋１ｊＡｊ（ただし、ｉ＞ｊのとき）、
ｆｉ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉ１０ｂ０（ただし、ｆ０＝ｂ０）、によって与えられるデータ処理方法である。
【００３２】
請求項２の発明は、請求項１に記載のデータ処理方法において、前記式統合工程では、次の対称性の式、
Ｉｉｉ＋１＝（Ｉｉｉ＋１）Ｔ（ただし、（＊）Ｔは行列＊の転置行列を表す）、
Ａｉ＋１＝Ｉｉ＋１ｉＡｉＩｉｉ＋１、を満たすように制約演算子Ｉｉ＋１ｉと補間演算子Ｉｉｉ＋１とを定めるものである。
【００３３】
請求項３の発明は、請求項１または請求項２に記載のデータ処理方法において、前記解法工程では、前記大連立方程式が反復法によって解かれるものである。
【００３４】
請求項４の発明は、請求項１または請求項２に記載のデータ処理方法において、前記解法工程では、前記大連立方程式が前処理付き反復法によって解かれるものである。
【００３５】
請求項５の発明は、請求項１乃至請求項４のいずれかに記載のデータ処理方法をコンピュータを用いて実行させるためのプログラムである。
【００３６】
請求項６の発明は、請求項５に記載のプログラムを格納したコンピュータ読み取り可能な記憶媒体である。
【００３７】
請求項７の発明は、コンピュータとマルチグリッド法とを用いて連立一次方程式を解くことにより特定空間領域に分布した未知数データを求めるデータ処理装置であって、前記特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に前記未知数変数に対する連立一次方程式を生成する式生成手段と、前記式生成手段によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して１つの連立一次方程式とした大連立方程式を生成する式統合手段と、前記式統合手段によって生成された大連立方程式を解いて前記未知数を求める解法手段とを備え、前記式統合手段では、前記粗密度のレベルを整数変数ｉまたはｊ（ただし０≦ｉ≦ｍ，０≦ｊ≦ｍ）によって識別し、レベルｉのグリッドにおける連立一次方程式の係数行列をＡｉとし、右辺ベクトルをｂｉとし、レベルｉのグリッドからレベルｉ＋１のグリッドへの制約演算子をＩｉ＋１ｉとし、レベルｉ＋１のグリッドからレベルｉのグリッドへの補間演算子をＩｉｉ＋１とし、前記大連立方程式の係数行列をＭｉ，ｊとし、未知数ベクトルをｘｉとし、右辺ベクトルをｆｉとして前記ｘｉを求めるとき、前記Ｍｉ，ｊと前記ｆｉとが、
Ｍｉ，ｉ＝Ａｉ、
Ｍｉ，ｊ＝ＡｉＩｉｉ＋１Ｉｉ＋１ｉ＋２・・・Ｉｊ−１ｊ（ただし、ｉ＜ｊのとき）、
Ｍｉ，ｊ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉｊ＋１ｊＡｊ（ただし、ｉ＞ｊのとき）、
ｆｉ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉ１０ｂ０（ただし、ｆ０＝ｂ０）、によって与えられるデータ処理装置である。
【発明の効果】
【００３８】
請求項１の発明によれば、制約演算子と補間演算子とが大連立方程式の中に組み込まれており、補間演算や制約演算を陽的に行わないマルチグリッド法（以下、陰的マルチグリッド法とも呼ぶ）となっているので、様々な前処理法を容易に併用できる。このような前処理法の併用は、従来の補間演算や制約演算を陽的に行っているマルチグリッド法では困難なものであり、この困難を解消できる本発明は、従来のマルチグリッド法の適用範囲を大幅に広げることができる。例えば、マルチグリッド法が組み込まれた大連立方程式を、容易に前処理付きクリロフ部分空間反復法によって解くことができると共に、コースグリッドコレクションの効果を享受できる。すなわち、本発明のデータ処理法に他の前処理法を用いることにより、従来から収束性の点で最も優れた方法であるとされているマルチグリッド法の収束性を、さらに向上できる。
【００３９】
また、本発明のデータ処理法によれば、陰的マルチグリッド法による定式化のみでコースグリッドコレクションの効果が組み込まれるので、従来行われているマルチグリッド法におけるサイクル部分の実装の必要がなく、他のソフトウエアライブラリとの連携が容易である。陰的マルチグリッド法では、一旦この手法で定式化すれば、あらゆる前処理付き反復法を適用することが可能となるので、様々な解法を柔軟に試すことができる。これは実用上において大きなメリットとなる。このように、従来のソフトウェアにおけるマルチグリッド法の実装を大幅に簡略化し、かつその適用範囲を大きく広げることができる。また、本発明における大連立方程式において、反復法の収束性に大きく影響する係数行列の固有値分布や条件数が大幅に改善されることが見いだされている。また、本発明のデータ処理法（陰的マルチグリッド）は、ある解析領域において微分方程式の問題を離散化により解く場合に用いられる幾何マルチグリッド法と、この手法を任意の係数行列に対して拡張した代数マルチグリッド（ＡＭＧ）法のいずれにも適用可能である。
【００４０】
請求項２の発明によれば、対称性のある問題に対して計算回数を減らすことができ、データ処理が容易となる。
【００４１】
請求項３の発明によれば、様々な実績ある反復法のソフトウエアライブラリを容易かつ安価に入手して用いることができる。
【００４２】
請求項４の発明によれば、様々な実績ある前処理法や反復法のソフトウエアライブラリを容易かつ安価に入手して用いることができる。
【００４３】
請求項５の発明によれば、本発明のプログラムを用いて種々のコンピュータ上でデータ処理を実行できる。
【００４４】
請求項６の発明によれば、本発明の記憶媒体に格納されたプログラムを用いて種々のコンピュータ上でデータ処理を実行できる。
【００４５】
請求項７の発明によれば、制約演算子と補間演算子とが大連立方程式の中に組み込まれており、補間演算や制約演算を陽的に行わないマルチグリッド法（以下、陰的マルチグリッド法とも呼ぶ）となっているので、様々な前処理法を容易に併用できる。このような前処理法の併用は、従来の補間演算や制約演算を陽的に行っているマルチグリッド法では困難なものであり、この困難を解消できる本発明は、従来のマルチグリッド法の適用範囲を大幅に広げることができる。例えば、マルチグリッド法が組み込まれた大連立方程式を、容易に前処理付きクリロフ部分空間反復法によって解くことができると共に、コースグリッドコレクションの効果を享受できる。すなわち、本発明のデータ処理法に他の前処理法を用いることにより、従来から収束性の点で最も優れた方法であるとされているマルチグリッド法の収束性を、さらに向上できる。
【００４６】
また、本発明のデータ処理装置によれば、陰的マルチグリッド法による定式化のみでコースグリッドコレクションの効果が組み込まれるので、従来行われているマルチグリッド法におけるサイクル部分の実装の必要がなく、他のソフトウエアライブラリとの連携が容易である。陰的マルチグリッド法では、一旦この手法で定式化すれば、あらゆる前処理付き反復法を適用することが可能となるので、様々な解法を柔軟に試すことができる。これは実用上において大きなメリットとなる。このように、従来のソフトウェアにおけるマルチグリッド法の実装を大幅に簡略化し、かつその適用範囲を大きく広げることができる。また、本発明における大連立方程式において、反復法の収束性に大きく影響する係数行列の固有値分布や条件数が大幅に改善されることが見いだされている。また、本発明のデータ処理装置では、ある解析領域において微分方程式の問題を離散化により解く場合に用いられる幾何マルチグリッド法と、この手法を任意の係数行列に対して拡張した代数マルチグリッド（ＡＭＧ）法のいずれにも対応可能である。
【発明を実施するための最良の形態】
【００４７】
以下、本発明の一実施形態に係るデータ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置について、図面を参照して説明する。図１は本発明のデータ処理方法のフローチャートを示し、図２は同データ処理方法における陰的マルチグリッド法の概念を示し、図３（ａ）（ｂ）（ｃ）は同データ処理方法で用いられる大連立方程式の具体例を示す。
【００４８】
本発明のデータ処理方法は、コンピュータと、陰的に包含されたマルチグリッド法とを用いて連立一次方程式を解くことにより、特定空間領域に分布した未知数データを求める方法である。ここで、特定空間領域とは、流体、電磁場、構造（車両、橋梁など）などを対象とする数値シミュレーションや数値解析においては、流体場、電磁場、構造体等が存在する１次元や３次元の実空間の特定領域であり、より一般的な多次元のデータ空間におけるデータ点に対する外乱などへの応答や挙動を調べる場合は、そのデータ空間の特定領域が特定空間領域となる。
【００４９】
このデータ処理方法は、図１に示すように、特定空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に未知数変数に対する連立一次方程式を生成する式生成工程（Ｓ１）と、前記式生成工程（Ｓ１）によって各粗密度のレベル毎に生成された複数の連立一次方程式を統合して１つの連立一次方程式とした大連立方程式を生成する式統合工程（Ｓ２）と、前記式統合工程（Ｓ２）によって生成された大連立方程式を解いて未知数を求める解法工程（Ｓ３）とを備えている。
【００５０】
ここで、式統合工程（Ｓ２）を説明するために、数学記号を導入する。粗密度のレベルを整数変数ｉまたはｊ（ただし０≦ｉ≦ｍ，０≦ｊ≦ｍ）によって識別し、レベルｉのグリッドにおける連立一次方程式の係数行列をＡｉとし、右辺ベクトルをｂｉとし、レベルｉのグリッドからレベルｉ＋１のグリッドへの制約演算子をＩｉ＋１ｉとし、レベルｉ＋１のグリッドからレベルｉのグリッドへの補間演算子をＩｉｉ＋１とする。また、大連立方程式の係数行列をＭｉ，ｊとし、未知数ベクトルをｘｉとし、右辺ベクトルをｆｉとする。
【００５１】
上述の式統合工程（Ｓ２）において、前記大連立方程式のＭｉ，ｊとｆｉとが、
Ｍｉ，ｉ＝Ａｉ、
Ｍｉ，ｊ＝ＡｉＩｉｉ＋１Ｉｉ＋１ｉ＋２・・・Ｉｊ−１ｊ（ただし、ｉ＜ｊのとき）、
Ｍｉ，ｊ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉｊ＋１ｊＡｊ（ただし、ｉ＞ｊのとき）、
ｆｉ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉ１０ｂ０（ただし、ｆ０＝ｂ０）、によって与えられる。
【００５２】
大連立方程式は、上述のＭｉ，ｊ、ｘｉ、ｆｉによって表され、図２に示すように、様々なグリッドレベル（細かいグリッド、粗いグリッド）で立てた各方程式を連立して１つの大きな連立一次方程式（大連立方程式Ｅｑ）としたものであり、補間演算子や制約演算子の効果を内部に包含している。従って、この大連立方程式Ｅｑによって定式化された方程式の解法は、補間演算や制約演算を陽的に行わないマルチグリッド法となっている。このような、マルチグリッド法を内包した大連立方程式による解法を、陰的マルチグリッド法と呼ぶことにする。以下、陰的マルチグリッド法についてその詳細を述べる。
【００５３】
（陰的マルチグリッド法のフレームワーク）
陰的マルチグリッド法における基本的な考えは、マルチグリッドの各レベルにおける方程式Ａｎｘｎ＝ｂｎ（ｎ＝０，．．，ｋ−１）を連立し、一つの大きな連立一次方程式として解くことに基づく。この統合化された方程式は、非正則な係数行列を持つ場合があるが、係数行列の値域と右辺ベクトルの間に成り立つ関係から、一般的に、反復法により解を得ることが可能である。
【００５４】
まず、ここでは簡単に２レベルの場合について説明する。一般的な２レベルのマルチグリッド法に関する書式とあわせ、レベル０をレベルｈ（上位レベル）、レベル１をレベルＨ（下位レベル）と表記し、各ベクトル、行列の上添え字をそれぞれ同様に対応させる。まず、連立して解くべき２つの方程式を次式で与える。
Ａｈｘｈ＝ｂｈ  （７）、
ＡＨｘＨ＝ｂＨ  （８）。
【００５５】
このままでは、単に２つの方程式を独立に解くことに過ぎないため、これら２つを関連付ける。
【００５６】
まず、従来のマルチグリッド法における上位レベルｈの解ベクトルの修正について考えると、解ベクトルｘｈはｘｈ←ｘｈ＋ＩｈＨｘＨのように修正される。この誤差修正は、式（７）における解として、ｘｈではなくｘｈ＋ＩｈＨｘＨを解として求めることに相当する。そこで、ｘＨを導入することにより、式（７）を次式のように書き換えることができる。
Ａｈｘｈ＋ＡｈＩｈＨｘＨ＝ｂｈ  （９）。
【００５７】
次に、マルチグリッドの下位レベルＨの右辺ベクトルは上位レベルｈの残差に制約演算子を施したものであるから、式（８）におけるｂｈは次式のように書ける。
ｂＨ＝ＩＨｈ（ｂｈ−Ａｈｘｈ）  （１０）。
【００５８】
これを式（８）に代入し整理すると、次式が得られる。
ＩＨｈＡｈｘｈ＋ＡＨｘＨ＝ＩＨｈｂｈ  （１１）。
【００５９】
式（９）（１１）を連立し、２レベルにおける陰的マルチグリッド法の定式化が、次式のように得られる。
【００６０】
【数１】
2008186361.tif 000003
（１２）。
【００６１】
係数行列Ａｈが対称であり、次式（１３）（１４）が成り立つ場合には、式（１２）の係数行列は対称となる。
ＩＨｈ＝（ＩｈＨ）Ｔ  （１３）、
ＡＨ＝ＩＨｈＡｈＩｈＨ  （１４）。
【００６２】
なお、ＡＭＧ法では式（１３）（１４）が成り立つように制約演算子と補間演算子とを定めるのが一般的である。
【００６３】
次に２以上のグリッドの場合における陰的マルチグリッド法の定式化について説明する。これは帰納的な方法で構築することができる。今、ｍレベルまでのグリッドを利用した場合の定式化を次式のように表す。ここで、次式（１５）の上添え字はマルチグリッドにおける各グリッドのレベルを表す。
【００６４】
【数２】
2008186361.tif 000004
（１５）。
【００６５】
ここで、図１に関連して述べたように、粗密度のレベルを整数変数ｉまたはｊ（ただし０≦ｉ≦ｍ，０≦ｊ≦ｍ）によって識別し、レベルｉのグリッドにおける連立一次方程式の係数行列をＡｉとし、右辺ベクトルをｂｉとし、レベルｉのグリッドからレベルｉ＋１のグリッドへの制約演算子をＩｉ＋１ｉとし、レベルｉ＋１のグリッドからレベルｉのグリッドへの補間演算子をＩｉｉ＋１とする。また、大連立方程式の係数行列をＭｉ，ｊとし、未知数ベクトルをｘｉとし、右辺ベクトルをｆｉとする。
【００６６】
上述のｉ＝０，１，・・・，ｍ、およびｊ＝０，１，・・・，ｍ、は、数字の大きいほど、粗なグリッドに対応し、数字の小さいほど密なグリッドに対応するものとする。この場合、ｉ＝０、またはｊ＝０は、最終的に解を求めるためのグリッドであり、最も密なグリッド（細かいグリッド）である。しかしながら、必ずしも、ｉ，ｊの増加に伴って次第に、一方的に粗なグリッドとなるように決める必要はなく、途中で粗密の度合いが何回か入れ替わるような設定にすることもできる。
【００６７】
上述の２レベルにおける定式化から、式（１５）について、次式を仮定する。
Ｍｉ，ｉ＝Ａｉ  （１６）、
Ｍｉ，ｊ＝ＡｉＩｉｉ＋１Ｉｉ＋１ｉ＋２・・・Ｉｊ−１ｊ  （ｉ＜ｊ）  （１７）、
Ｍｉ，ｊ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉｊ＋１ｊＡｊ  （ｉ＞ｊ）  （１８）、
ｆｉ＝Ｉｉｉ−１Ｉｉ−１ｉ−２・・・Ｉ１０ｂ０  （ｆ０＝ｂ０）  （１９）。
【００６８】
このとき、レベルｍ＋１のグリッドが追加された場合を考える。この場合、係数行列にＭｍ＋１、ｍ＋１，Ｍｉ，ｍ＋１、およびＭｍ＋１、ｉ（但しｉ＝０，１，．．，ｍ）が追加され、右辺ベクトルにｆｍ＋１の項が追加される。
【００６９】
まず、ｍ＋１レベルで解く方程式について考えると、係数行列はＡｍ＋１で与えられ、右辺ベクトルはｍレベルの方程式の残差に制約演算子Ｉｍ＋１ｍを施したものとなる。従って、次式（２０）となる。
Ａｍ＋１ｘｍ＋１＝Ｉｍ＋１ｍ（ｆｍ−Ｍｍ，０ｘ０−Ｍｍ，１ｘ１・・・−Ｍｍ，ｍｘｍ）  （２０）。
【００７０】
右辺の括弧内第２項以降を左辺に移項し、式（１７）（１９）の仮定を使うと、ｍ＋１レベルについて次式（２１）（２２）（２３）が得られる。
Ｍｍ＋１，ｍ＋１＝Ａｍ＋１  （２１）、
ｆｍ＋１＝Ｉｍ＋１ｍｆｍ＝Ｉｍ＋１ｍＩｍｍ−１・・・Ｉ１０ｂ０  （２２）、
Ｍｍ＋１，ｊ＝Ｉｍ＋１ｍＭｍ，ｊ＝Ｉｍ＋１ｍＩｍｍ−１・・・Ｉｊ＋１ｊＡｊ
（ｊ＝０，．．．，ｍ）  （２３）。
【００７１】
次に、ｍ＋１レベルの結果による各レベルの誤差修正について考えると、レベルｉにおける解の探索空間がｘｉ←ｘｉ＋Ｉｉｉ＋１Ｉｉ＋１ｉ＋２・・・Ｉｍｍ＋１ｘｍ＋１のように修正されることになる。従って、次式（２４）が得られる。
Ｍｉ，ｍ＋１＝ＡｉＩｉｉ＋１Ｉｉ＋１ｉ＋２・・・Ｉｍｍ＋１  （ｉ＜ｊ）
（ｉ＝０，．．．，ｍ）（２４）。
【００７２】
式（２１）〜（２４）は式（１６）〜（１９）においてｉ＝ｍ＋１としたものに等しく、ｍ＝０またはｍ＝１とした場合に式（１６）〜（１９）が成り立つのは式（１２）より明らかであるので、帰納的にｍレベル陰的マルチグリッド法の定式化が式（１５）〜（１９）により与えられる。
【００７３】
上述の統合した連立一次方程式（大連立方程式）の３つの具体例が、図１（ａ）（ｂ）（ｃ）に示されている。それぞれ順番に、グリッドレベルｍ＝１，２，３について示されている。陰的マルチグリッド法の定式化が、複数のグリッドの場合について帰納的な方法で構築されることが分かる。
【００７４】
陰的マルチグリッド法による解法手順は、制約演算子と補間演算子、および各レベルでの係数行列に基づいて式（１６）〜（１９）の各々を計算し、統合化された連立一次方程式（１５）を構築した後、これを前処理付き反復法により解くことにより与えられる。
【００７５】
なお、上記の手順において制約演算子と補間演算子、および各レベルでの係数行列の生成は幾何マルチグリッド法あるいはＡＭＧ法（代数マルチグリッド法）のセットアップ部の手順を用いることができる。ＡＭＧ法のセットアップ部の手順を用いた場合、ブラックボックス型ソルバとして陰的マルチグリッド法の手法を実装することができる。
【００７６】
（陰的マルチグリッド法の効果）
陰的マルチグリッド法では、マルチグリッド法において各レベルで解かれる方程式を統合化し、その統合化した連立一次方程式（大連立方程式）に対して反復法を適用することにより解を得る。通常のマルチグリッド法では明示的にコースグリッドコレクションを行うが、陰的マルチグリッド法では統合化された方程式に対する反復法の残差収束の作用がマルチグリッド法におけるコースグリッドの効果を陰的に含んでいる。
【００７７】
予備的な数値実験によると、陰的マルチグリッド法により得られた統合化された係数行列の条件数が元の係数行列と比べて改善されていることが確認された。また、陰的マルチグリッド法において得られる方程式を対称ガウス＝ザイデル法で解くことは、その手順が、マルチグリッド法においてプリスムージングとして前進ガウス＝ザイデル法を使用し、ポストスムージングとして後退ガウス＝ザイデル法を使用したＶサイクルの手順と同一であり、解法としても、全く同じになる。
【００７８】
従って、陰的マルチグリッド法において定常反復法や定常反復前処理を利用した場合には、マルチグリッド法やマルチグリッド前処理法と同様の効果が得られると考えられる。
【００７９】
（電磁場解析とマルチグリッド法）
次に、陰的マルチグリッド法の背景として、電磁場解析とマルチグリッド法の関係について述べる。現在、電磁場解析における主流の解析方法として、磁気ベクトルポテンシャルあるいは電場を未知数とした辺要素有限要素法が挙げられる。特に低周波の電磁場解析では磁気ベクトルポテンシャルを未知変数とした解析が多く用いられる。
【００８０】
電磁場解析では、代表的な定式化の手法として、磁気ポテンシャルだけを用いる方法（Ａ法）、および磁気ベクトルポテンシャルと電気スカラポテンシャルを用いる方法（Ａ−φ法）の２つがある。なお、解の一意性のためにはゲージ条件が必要である。また、後者の解法では辺要素と節点要素が併用される。
【００８１】
こうした各種の方法の中で、多くの数値解析結果の蓄積から、有限要素法において生ずる連立一次方程式の解法としてＩＣＣＧ法（不完全コレスキー分解前処理付き共役勾配法）を利用した場合、Ａ−φ法による定式化をゲージ条件を科さずに行った場合が最も収束性がよいことが分かってきた。そこで、Ａ−φ定式化が反復法の収束性において有利となる理由について研究が行われている。
【００８２】
一方、高周波電磁場解析におけるマルチグリッド法において特殊なスムーザを用いる必要性が示され、具体的にいくつかのスムーザが提案された。例えば、ハイブリッドスムーザや特殊なシュワルツスムーザがその例である。これらのスムーザは辺要素が作る関数空間中において、その離散的な回転が０となるような誤差成分が収束しづらい点に着目し、この誤差成分についてなんらかの対処をする点に特徴がある。
【００８３】
一方、この辺要素が作る空間における回転のＫｅｒｎｅｌ空間は、電気スカラポテンシャルを節点要素により離散化し、ｇｒａｄ演算子を作用させた空間に一致している。つまり、ハイブリッドスムーザやシュワルツスムーザはｇｒａｄφの空間に属する誤差成分に対してその修正を行う方法であると見做すことができる。
【００８４】
そこで、これらの方法の有効性を鑑みると、Ａ−φ定式化はφを導入することで、ベクトルポテンシャルの回転が０となるような誤差成分を除去する効果を内包し、そのことにより収束性の改善を得たのではないかという考えが示された。
【００８５】
すなわち、Ａ−φ法の場合には未知変数φを含む連立一次方程式が構築されるが、係数行列のうちφに対応する部分が反復法においてｇｒａｄφで表現される誤差成分の除去になんらかの寄与をしているという考えである。こうした考えは現時点で未だ定量的な検証に至っていないが、高周波電磁場解析におけるＡ−φ法の優位性も近年示されてきており、妥当性があると考えられる。
【００８６】
（電磁場解析と陰的マルチグリッド法）
上述のような電磁場解析における背景を下に、陰的マルチグリッド法の有効性について述べる。上記において、ベクトルポテンシャルのみを用いて定式化した場合の電磁場解析では、電気スカラポテンシャルのｇｒａｄ成分に属する誤差が収束しづらく、この成分に対しては別の係数行列を用いることにより全体の収束を加速できることを述べた。
【００８７】
ここで、上述の手法で用いられる収束しにくい誤差を別の係数行列により収束させるという概念について考えると、この概念はマルチグリッド法におけるコースグリッドコレクションに類似している。つまり、マルチグリッド法では密なグリッド（元の解くべきグリッド）において除去しにくい誤差成分を、粗いグリッド、すなわち別途生成した係数行列により除去しており、類似性を持っている。
【００８８】
通常のマルチグリッド法は、レベル間における誤差の補間、修正を明示的に行うので、上記の考えに沿って電磁場解析に置き換えるとハイブリッドスムーザに相当する。そこで、マルチグリッド法において、電磁場解析におけるＡ−φ定式化と同様の定式化を試みるのが本提案の陰的マルチグリッド法であり、電磁場解析におけるＡ−φ定式化の有効性から、この手法もコースグリッドコレクションの効果を内包することが期待される。
【００８９】
上述の効果に加え、陰的マルチグリッド法を導入した場合に期待される効果について述べる。従来、マルチグリッド法は単独の線形ソルバあるいは反復法（主にクリロフ部分空間反復法）の前処理法として用いられて効果をあげてきた。特にマルチグリッド法を前処理とする反復法は高速性の点で他の方法を大きく凌駕している。
【００９０】
ところが、これらのマルチグリッド法やマルチグリッド前処理法を用いても十分な収束性が得られない場合がある。制約演算子、補間演算子、スムーザ、基本反復法、サイクル形状などに関して多くの選択肢があり、また新たな提案も行われているが十分な成果を挙げていないのが現状である。
【００９１】
一方、反復法の前処理技術では、近似逆行列分解前処理、領域分割型前処理など、近年新しい提案が行われているが、マルチグリッド前処理法とこれらの前処理法とを併用することはできない。こうした背景に対して、コースグリッドコレクションを陰的に行う陰的マルチグリッド法では、各グリッドレベルを統合した連立一次方程式（大連立方程式）を解くので、反復法において提案されているあらゆる前処理手法を適用することが可能となる。すなわち、陰的マルチグリッド法の利点は、従来のマルチグリッド法の枠を広げ、数多く提案されている他の前処理手法とコースグリッドコレクションの併用を可能にする点にある。
【００９２】
（データ処理装置）
次に、図４を参照して、本発明の他の実施形態に係るデータ処理装置について説明する。データ処理装置１は、コンピュータと、陰的に包含されたマルチグリッド法とを用いて連立一次方程式を解く装置であって、空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に未知数変数に対する連立一次方程式を生成する式生成手段３と、各粗密度のレベル毎に生成された複数の連立一次方程式を統合して１つの連立一次方程式とした大連立方程式を生成する式統合手段４と、生成された大連立方程式を解いて未知数を求める解法手段５とを備えている。
【００９３】
データ処理装置１は、さらに、制御手段２と、入出力手段６と、記憶手段７と、を備えている。制御手段２は、入出力手段６を介して入力された問題データや処理条件データを取得し、記憶手段７に記憶し、これらのデータを式生成手段３、式統合手段４、解法手段５に供給すると共に、その動作を制御して未知数を算出させ、その算出結果を入出力手段６から出力する。
【００９４】
上述の式生成手段３、式統合手段４、および解法手段５は、前述の図１、図２、図３を参照して説明したデータ処理方法における式生成工程（Ｓ１）、式統合工程（Ｓ２）、解法工程（Ｓ３）の処理を実行する。
【００９５】
制御手段２は、通常のコンピュータにおけるＣＰＵやＭＰＵを備えて構成される。入出力手段６は、ＭＯ，ＣＤ，ＤＶＤなどの光媒体や、半導体メモリ媒体に対して読み書きする装置、マウスなどのポインタを用いるＧＵＩ、プリンタなどを備えて構成される。
【００９６】
式生成手段３、式統合手段４、および解法手段５は、制御手段２が制御するＣＰＵとプログラムメモリとプログラムメモリに取り込まれたソフトウエアなどの総体によって構成される。従って、本データ処理装置１は、ＣＰＵやメモリや外部記憶装置や表示装置や入力装置などを備えた一般的な構成を備えた電子計算機、およびその上のプロセス又は機能の集合として構成することができる。
【００９７】
（実施例）
次に、陰的マルチグリッド法を用いたデータ処理方法による実施例と比較例とについて説明する。図５に示すように、以下の各式で与えられる２次元ポアソン方程式の境界値問題の差分解析を実施例とし、陰的マルチグリッド法の有効性について述べる。有効性の評価は、収束性によって行う。
（ｘｙ領域）  ０≦ｘ≦１，０≦ｙ≦１            （２５）、
（領域内で）  −▽（κ▽ｕ（ｘ，ｙ））＝ρ      （２６）、
（領域境界で）  ｕ（ｘ，ｙ）＝０                （２７）、
（拡散係数）  κ＝κ０  （１／４≦ｘ≦３／４  かつ  １／４≦ｙ≦３／４）、
κ＝１  （上記以外）              （２８）。
【００９８】
式（２６）を５点差分公式により離散化し、得られる連立一次方程式を解く。解析プログラムはＭＡＴＬＡＢにより記述され、解析はパーソナルコンピュータ上で行われた。
【００９９】
（解析結果）
図６乃至図１１に解析結果を示す。これらは、解くべき２次元差分格子のサイズと、解析対象の一部領域の拡散係数κ０と、を変化させた結果である。各図には、６種類の解析手法による結果が示されている。解析手法の識別記号を、次表１に示す。
【０１００】
【表１】
2008186361.tif 000005
【０１０１】
ＣＧとＩＣＣＧは、解くべき差分格子上で得られた連立一次方程式を、それぞれ、ＣＧ（共役勾配）法とＩＣＣＧ（不完全コレスキー分解前処理付き共役勾配）法とで解いた結果を示す。
【０１０２】
ｉＭＧと冠されているものは、陰的マルチグリッド定式化を用いた結果である。ｉＭＧ−ＳＧＳは、陰的マルチグリッド法によって統合化された方程式を、対称ガウス＝ザイデル法で解くものであり、マルチグリッド法による単体ソルバによる解法と同一である。
【０１０３】
ｉＭＧ−ＣＧ，ｉＭＧ−ＩＣＣＧ，ｉＭＧ−ＳＧＳＣＧは、それぞれ陰的マルチグリッド法によって統合化された方程式を、ＣＧ法、ＩＣＣＧ法、対称ガウス＝ザイデル前処理付きＣＧ法で解いた結果を示す。
【０１０４】
図６乃至図９では、一定の拡散係数（κ０＝１）のもとで、最密のグリッド（解くべき差分格子）のサイズを順番に変えている。それぞれ、図６では１５×１５、図７では６３×６３、図８では１２７×１２７、図９では２５５×２５５としている。
【０１０５】
図１０、図１１では、最密のグリッド（解くべき差分格子）のサイズを１２７×１２７として、拡散係数を変化させ、図１０ではκ０＝１０、図１１ではκ０＝１００としている。
【０１０６】
上述のことから、図６乃至図９におけるｘ軸の反復回数は、ＣＧ，ＩＣＣＧ，ｉＭＧ−ＣＧ，ｉＭＧ−ＩＣＣＧ，ｉＭＧ−ＳＧＳＣＧについてはＣＧ法の反復回数を示し、ｉＭＧ−ＳＧＳについては対称ガウス＝ザイデル法の反復回数（通常のマルチグリッド単体ソルバにおけるＶサイクル数）を示す。また、これらの解法において１反復あたりの計算量は各々異なっていることに留意が必要である。
【０１０７】
（コースグリッドコレクションの効果）
図６、図７、図８、図９において、ＣＧ，ＩＣＣＧとｉＭＧ−ＣＧ，ｉＭＧ−ＩＣＣＧの結果を比較する。図中において、解くべきグリッドのサイズが増加するにつれて、ＣＧ，ＩＣＣＧの場合には大幅に収束性が悪化している。
【０１０８】
一方、ｉＭＧ−ＣＧ，ｉＭＧ−ＩＣＣＧの場合には、反復回数は多少増加しているものの、ＣＧ，ＩＣＣＧの場合と比較すると収束性はほとんど変わらない。つまり、マルチグリッド法における最も重要な性質であるグリッドサイズによらない収束性、が実現されている。
【０１０９】
特に、ｉＭＧ−ＣＧの場合、統合化された方程式をＣＧ法で解いているだけであり、その解法手順には、マルチグリッド法のコースグリッドコレクションに相当する部分が、（陽には）含まれていない。従って、このｉＭＧ−ＣＧの結果は、陰的マルチグリッド法の有効性を示すものであり、陰的マルチグリッド法による定式化によって各グリッドレベルの方程式を連立して解くことにより、コースグリッドコレクションの効果が取り入れられることが分かる。
【０１１０】
（不連続条件）
次に、図９、図１０、図１１の結果を比較する。これらは、解くべき領域の一部の拡散係数κ０を変化させた結果である。拡散係数κ０の増加は、領域内の拡散係数の不連続性の増加を意味し、離散化の結果得られる方程式がより悪条件のもとでの問題となることを意味する。その結果、ＣＧ，ＩＣＣＧの場合だけでなく、元の係数行列を対象とした単体マルチグリッドソルバ（ｉＭＧ−ＳＧＳ）においても、収束性が悪化しており、ｉＭＧ−ＣＧも同様に悪化している。
【０１１１】
ところが、ｉＭＧ−ＩＣＣＧは、拡散係数κ０を増加した場合においても、高い収束性を維持している。その結果、単体のマルチグリッドソルバとｉＭＧ−ＩＣＣＧとは、図８の条件において同程度の収束性を示していたが、解くべき問題が困難になるに従い、ｉＭＧ−ＩＣＣＧの優位性が増している。従って、様々な前処理法との併用が可能な陰的マルチグリッド法は、より悪条件な問題において、単体のマルチグリッドソルバよりも、より高い性能を得ることが可能といえる。
【０１１２】
（まとめ）
以上に示したように、ｉＭＧ−ＳＧＳＣＧは、全解析結果を通じて最も優れた収束性を有する。ｉＭＧ−ＳＧＳＣＧは、その計算手順がＭＧＣＧ法とほぼ同一であり、その収束特性も同程度と考えられる。ＭＧＣＧ法は、現在、最も高速な連立一次方程式の解法の一つとして知られている。しかし、陰的マルチグリッド法では、前処理法として近似逆行列前処理やＩＬＵ（ｋ）といったより高度な前処理法を、容易に用いることができるので、これらの前処理法を用いることにより、ＭＧＣＧ法よりも高い収束性を、容易な手順によって、得ることが可能である。
【０１１３】
また、実装面において、陰的マルチグリッド法には以下のような利点がある。陰的マルチグリッド法では、一旦統合化された方程式（大連立方程式Ｅｑ）を構築すれば、解法の対象となるこの方程式は、通常のありふれた連立一次方程式なので、この連立一次方程式に対して、様々な反復法を柔軟に適用することができる。現在、反復法のライブラリ、テンプレートが商用またはフリーのソフトウェアとして利用可能であり、簡単にこれらのリソースを活用することができる。
【０１１４】
一方、従来のマルチグリッド法においては、例えばスムーザの変更は容易ではない。実際、現在利用可能なマルチグリッドソフトウェアでは、せいぜいいくつかのスムーザのうちから選択できるという機能があるのみであり、より高度なスムーザを実装するのはユーザにとって容易でない。その点、陰的マルチグリッド法では、連立一次方程式を統合化するという形でコースグリッドコレクションを取り込んでおり、コースグリッドコレクションを解法部分から分離できるという点が実用上の大きなメリットとなる。
【０１１５】
以上、実施形態例を詳述したが、本発明は、例えば、システム、プログラム、または記憶媒体（記録媒体）などとしての実施形態をとることができる。
【０１１６】
また、本発明のデータ処理方法をコンピュータを用いて実行させるためのプログラムも本発明を実現するものであり、本発明は、プログラムの形態によらずそのプログラムを発明として含む。
【０１１７】
さらに、本発明のデータ処理方法を実行するために生成した入力用のデータが、既存のコンピュータと既存のソフトウエアによって実行処理されることにより、本発明のデータ処理方法による効果が奏される場合に、当該入力用のデータが本発明のプログラムの一部として本発明に含まれる。
【０１１８】
本発明は、プログラムを格納したコンピュータ読み取り可能な記憶媒体（記録媒体）も含む。記憶媒体は、例えば、磁気ディスク、光ディスク、光磁気ディスク、磁気テープ、不揮発性のメモリカードなどである。
【０１１９】
また、コンピュータが読み出したプログラムを実行することによって、上述した実施形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行い、その処理によっても上述した実施形態の機能が実現される。
【図面の簡単な説明】
【０１２０】
【図１】本発明の一実施形態に係るデータ処理方法のフローチャート。
【図２】同上データ処理方法における陰的マルチグリッド法の概念説明図。
【図３】（ａ）（ｂ）（ｃ）は同上データ処理方法で用いられる大連立方程式の具体例の説明図。
【図４】一実施形態に係るデータ処理装置のブロック構成図。
【図５】同上データ処理方法を用いた方程式解法の実施例に関する問題設定の図。
【図６】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較のグラフ。
【図７】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較の他の例におけるグラフ。
【図８】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較のさらに他の例におけるグラフ。
【図９】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較のさらに他の例におけるグラフ。
【図１０】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較のさらに他の例におけるグラフ。
【図１１】同上データ処理方法およびデータ処理装置を用いた場合と他の方法による場合の繰り返し計算回数に対する残差の比較のさらに他の例におけるグラフ。
【符号の説明】
【０１２１】
１    データ処理装置
３    式生成手段
４    式統合手段
５    解法手段
Ｅｑ    大連立方程式
【図１】
2008186361.tif 000006
【図２】
2008186361.tif 000007
【図３】
2008186361.tif 000008
【図４】
2008186361.tif 000009
【図５】
2008186361.tif 000010
【図６】
2008186361.tif 000011
【図７】
2008186361.tif 000012
【図８】
2008186361.tif 000013
【図９】
2008186361.tif 000014
【図１０】
2008186361.tif 000015
【図１１】
2008186361.tif 000016