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

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

国内特許コード P09A014465
整理番号 1409
掲載日 2009年5月8日
出願番号 特願2007-021230
公開番号 特開2008-186361
登録番号 特許第5066711号
出願日 平成19年1月31日(2007.1.31)
公開日 平成20年8月14日(2008.8.14)
登録日 平成24年8月24日(2012.8.24)
発明者
  • 岩下 武史
  • 美舩 健
出願人
  • 国立大学法人京都大学
発明の名称 データ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置
発明の概要

【課題】マルチグリッド法を用いたデータ処理方法とそのプログラムおよび記録媒体並びにデータ処理装置において、簡単な構成により、他の前処理法との容易な併用を可能とする。
【解決手段】データ処理方法は、コンピュータと、陰的に包含されたマルチグリッド法とを用いて連立一次方程式を解く方法であって、空間領域に定義した互いに粗密度のレベルが異なる複数のグリッドのもとで各グリッドに未知数変数を割り当てると共に未知数変数に対する連立一次方程式を生成する式生成工程(S1)と、各粗密度のレベル毎に生成された複数の連立一次方程式を統合して1つの連立一次方程式とした大連立方程式を生成する式統合工程(S2)と、生成された大連立方程式を解いて未知数を求める解法工程(S3)とを備えている。大連立方程式は、補間演算や制約演算を陽的に行わないマルチグリッド法となっており、他の前処理法を併用して求解を行うことができる。
【選択図】図1

従来技術、競合技術の概要


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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



すると、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に対する平滑化演算によってχを更新。



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



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



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



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

【特許文献1】特開2006-293488号公報

【特許文献2】特開2002-56038号公報

産業上の利用分野


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

特許請求の範囲 【請求項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)、によって与えられることを特徴とするデータ処理装置。
産業区分
  • 計算機応用
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2007021230thum.jpg
出願権利状態 権利存続中
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記までご連絡ください。


PAGE TOP

close
close
close
close
close
close
close