JP2002056038A - メッシュ／グリッド生成に由来する線形連立方程式の数値解を得るためのアクセラレーターおよび高速化手法 - Google Patents

Abstract

(57)【要約】 （修正有） 【課題】メッシュ計算に由来する線形行列方程式の解法
を高速化するシステムを提供する。 【解決手段】アクセラレーターは、メッシュジェネレー
ターが生成したメッシュに基づいた線形行列方程式を解
くアナライザー／ソルバーに外部的に接続するライブラ
リとして使用される。このアクセラレーターはＮ＊Ｎ線
形行列方程式の細密メッシュを受け取り、この細密メッ
シュに基づいて最適な粗メッシュを算出する。ここでＮ
は細密メッシュにおける結節点の数である。この粗メッ
シュはアナライザー／ソルバーに送られる。アナライザ
ー／ソルバーは、Ｎ＊Ｎ線形行列方程式と同等である粗
メッシュのＭ＊Ｍ線形行列方程式を解く。アクセラレー
ターはＭ＊Ｍ線形行列方程式の最初の解を受け取る。す
ると次にアクセラレーターは、粗メッシュの点について
解の勾配とヘッセ行列式の最適見積りを用いて、Ｎ＊Ｎ
線形行列方程式の第２の解を計算する。

Description

【発明の詳細な説明】

【０００１】

【発明の背景】１．発明の範囲 本発明は、コンピューター化数値分析による線形方程式
解法に関するものである。本発明は特に、ＣＡＤ／ＣＡ
ＭやＧＩＳ、３次元描写システムの分析速度を上げるこ
とを目的としたものである。

【０００２】２．関連技術の説明 グラフィックスを取り扱うために市販されているシステ
ムとしては、ＣＡＤ／ＣＡＭ（コンピューター支援設計
／コンピューター支援製造）システムや、ＧＩＳ（地理
情報システム）、３次元描写システムなど、さまざまな
ものがある。これらのシステムはオブジェクトの設計を
行なうのに利用されている。対象となるオブジェクトに
は、機械部品や地理的外形などが挙げられる。これらの
システムは、一般に市販されているメッシュジェネレー
ターや、オブジェクトに関する現象を分析するアナライ
ザー／ソルバーに広く使用されている。オブジェクトに
関する現象とは、例えば、機械部品の振動や熱分散、特
定地域の地理上の水流や汚染分散などである。分析する
オブジェクトのメッシュデータを受け取って処理するア
ナライザー／ソルバーも市販されている。

【０００３】図３はＣＡＤ、メッシュジェネレーター、
アナライザー／ソルバーを使用した通常のシステムの使
用構成である。ＣＡＤ１が生成したオブジェクトは、メ
ッシュジェネレーター２に送られる。メッシュジェネレ
ーター２ではオブジェクトに対応するメッシュデータ配
列が生成される。このメッシュデータがアナライザー／
ソルバーに送られる。アナライザー／ソルバーは現象を
線形方程式で表現し、その方程式を解く。アナライザー
／ソルバーによって得られた解がＣＡＤ１に送り返さ
れ、オブジェクトに対する現象がグラフィックスに表示
されることになる。

【０００４】この種のシステムを構成する際は、必ず、
解の精度、線型方程式を解く計算の労力（かかる時
間）、方程式を解くのに要するメモリの容量、という３
つの要素が考慮される。これら３つは、トレードオフの
観点から考慮される。すなわち、１つのシステムで（同
時に）３つの要素全てを充足する（つまり、精度を最高
にし、計算時間を短縮し、データ記憶容量を極力抑え
る）のはきわめて難しい。

【０００５】コンピューターを用いて線形行列方程式を
解くには、ガウシアン法、ＬＵ法、因数分解法、コレス
キー法、ハウスホルダー法、ガウス法、サイデル法、勾
配法、共役勾配法など、数多くの古典的な手法がある。
アナライザー／ソルバーでは、線形方程式を解くのに、
これらのうち一つが用いられている。

【０００６】未知数がＮ個の線形連立方程式は、行列方
程式の形式で表わすことができる。ＡＸ＝Ｂ、ここでＡ
はＮ＊Ｎ行列であり、Ｘは未知数ベクトル、Ｂは項決定
ベクトルである。グリッドに打切りが用いられる場合、
Ｎはメッシュの結節点における未知変数の総数になる。

【０００７】こういった古典的手法を実行する場合の計
算時間は、Ｎの数によって大きく異なる。通常、Ｎの数
はかなり大きくなる。さらに、計算するオブジェクトが
複雑な形状の場合、正確な解を得ようとすると、Ｎは非
常に大きくなる。従って、上記のような古典的な手法に
基づいて妥当な計算時間で適切な解を得るのは困難とな
っている。

【０００８】このような系の計算時間を改善（短縮）す
るひとつの方法は、マルチグリッドを使用することであ
る。マルチグリッドとは、補助的な粗メッシュを用い
て、Ｎの総数を減らすものである。また別の方法として
は、線形方程式を並行して計算するマルチプロセシング
がある。しかしながら、これら２つの方法は、元のアナ
ライザー／ソルバーに統合しなければならない。言い換
えると、アナライザー／ソルバーシステムの内部コード
を、計算の高速化のために書き直さなければならないの
である。従って、このような改善方法はユーザーやソフ
ト開発業者にとって不便である。

【０００９】グリッドの最適化には、適応的メッシュ技
法を使用することができる。このグリッド最適化の古典
的手法は、簡単にまとめると次のようになる。詳細
は、”Ｈａｎｄｂｏｏｋ ｏｆ Ｇｒｉｄ Ｇｅｎｅｒ
ａｔｉｏｎ”（ＴｈｏｍｐｓｏｎＪ．Ｆ．， Ｂｋ Ｓ
ｏｎｉ ａｎｄ Ｗｅａｔｈｅｒｉｌｌ ＮＰ， Ｃｈ
ａｐｔｅｒ ３３， ＣＲＣ Ｐｒｅｓｓ， １９９９
年）に解説されている。本文書では、この本の全内容が
参考文献として明示的に織り込まれている。

【００１０】１．最初のメッシュＭ０を構築し、解Ｕ０
を計算し、メッシュジェネレーターに由来するＮ＊Ｎの
線形連立方程式ＡＵ０＝Ｂが生成される。

【００１１】２．適応最適化基準σ（Ｍ０，Ｕ０，−）
を選択する。

【００１２】３．Ｍ ａｄａｐｔ＝ＡｒｇＭｉｎ σ
（Ｍ０，Ｕ０，Ｍ）を見出す。未知数Ｍ個の結節点をも
つ補助グリッドＭ ａｄａｐｔを解く。

【００１３】４．等値のＭ＊Ｍ線形連立方程式Ａ’Ｘ’
＝Ｂ’を構築する。

【００１４】５．Ｍ＊Ｍ線形連立方程式を解く。

【００１５】選んだ最適化基準が、この線形連立方程式
を解く計算労力を減らす場合、ＭはＮよりかなり小さく
なっている。しかしながらこの方法では、Ｎ＊Ｎ線形連
立方程式を少なくとも１回、ステップ１で計算する必要
がある。さらに、選択した最適化基準σ（Ｍ０，Ｕ０，
−）は、妥当な計算時間内で、望むような精度を達成す
るには適当でない。言い換えると、適切な精度を得るに
は、複数回繰り返すことが必要になってくる。これらの
問題が、線形連立方程式の解法で計算労力を減らす際の
障害となっている。

【００１６】本発明は、これらの障害を克服するための
ものである。

【００１７】

【発明の概要】本発明の目的は、メッシュ計算に由来す
る線形行列方程式の解法を高速化する手法およびシステ
ムを提供することである。このアクセラレーターは、外
部のコンピューターライブラリとして使用される。

【００１８】本発明は、構造化・非構造化グリッド（メ
ッシュ）における常微分方程式、偏微分方程式、通常方
程式の打切りにより、線形方程式を解くソルバー／アナ
ライザーの計算速度を高めるアクセラレーターおよび高
速化手法を提供する。

【００１９】本発明によるアクセラレーターは、アナラ
イザー／ソルバーおよびメッシュジェネレーターに外部
的に接続することができる。このアナライザー／ソルバ
ーは、メッシュジェネレーターが生成するメッシュに基
づき線形行列方程式を解く。アクセラレーターに含まれ
るメッシュサイズオプチマイザーは、メッシュジェネレ
ーターが生成した最初のメッシュを受け取り、その最初
のメッシュに基づいて最適なメッシュサイズを計算し、
最適メッシュサイズをメッシュサイズジェネレーターに
対して出力し、メッシュジェネレーターはこの最適メッ
シュサイズに従って第２のメッシュを生成する。最適メ
ッシュサイズは最初のメッシュのサイズよりも大きなも
のになる。アクセラレーターにはインターポレーターも
含まれており、このインターポレーターは、第２のメッ
シュについてアナライザー／ソルバーが計算した解を読
み取り、その第２のメッシュに関する解を、補間によ
り、最初のメッシュの解に変換する。

【００２０】本発明の特性として、このアクセラレータ
ーは、メッシュやグリッドの生成用に市販されているす
べてのアナライザー／ソルバーと一緒に使用して、アナ
ライザー／ソルバーの実行コードやソースコードを一切
書き換えることなく計算時間を短縮し、解の精度も維持
することができる。計算時間の短縮は、アナライザー／
ソルバーに外部接続されるソフトウェアライブラリの使
用によって実現される。

【００２１】アナライザー／ソルバーは、複数の入出力
データ構造を有する複数のアナライザー／ソルバーから
選択される。本アクセラレーターにはソルバーセレクタ
ーも含まれており、これは、選択されたアナライザー／
ソルバーに対応するデータ構造を選択するのに使用され
る。データ構造を選択すると同時に、ソルバーセレクタ
ーは、上記の複数のアナライザー／ソルバーと複数のデ
ータ構造との間の関係が保存されているモデルデータベ
ースを活用する。このようにして、本発明はＣＡＤ／Ｃ
ＡＭやＧＩＳ、３次元描写システム、おらびそれぞれの
アナライザー／ソルバーに適用することができる。

【００２２】本アクセラレーターにはデコンポザーも含
めることができる。このデコンポザーは、３次元メッシ
ュデータの解をアナライザー／ソルバーから受け取り、
その３次元メッシュデータの解を変換する。これにより
本発明は、３次元および２次元データを生成するアナラ
イザー／ソルバーやＣＡＤ／ＣＡＭ、ＧＩＳ、３次元描
写システムに適用することができる。

【００２３】本アクセラレーターには誤差エスチメータ
ーも含められる。この誤差エスチメーターは、補間され
た解についての誤差が、既定値範囲内になるかどうか評
価するものである。この誤差は、補間解のヘッセ行列式
に基づいて評価される。この誤差が既定値範囲を上回る
場合は、粗メッシュサイズを調節して、方程式解を求め
る。このようにして、適切な精度が確保される。

【００２４】粗メッシュサイズオプチマイザーでは、仮
定的予測に基づいて最適なメッシュサイズを計算する。
その後に、最小二乗法に基づいて最適メッシュサイズを
調整するようになっている。

【００２５】詳しく述べると、粗メッシュサイズオプチ
マイザーでは、次の方程式によって最適メッシュサイズ
を調整する：

【００２６】

【数１】

【００２７】ここにおいてｕ_１ｈ（ｘ）は、不連続解ａ
ｌ（Ｎ次ベクトル）を補間して得られた細密メッシュの
連続解で、Ｎ＊Ｎ線形方程式の解である。ｕ_２Ｈ（ｘ）
は、粗メッシュについての連続解で、勾配予測により不
連続解ａ２（Ｍ次ベクトル）を補間して得られたもので
あり、Ｍ＊Ｍ線形行列方程式の解である。ｃは第２回目
に加わる加重関数であり、ＬおよびＢはアナライザー／
ソルバーの種類によって決まる、あるいはユーザーが定
義する演算子である。Ωは変域、Γは分析するオブジェ
クトの境界である。

【００２８】アナライザー／ソルバーによって算出され
た解は、第２のメッシュの点それぞれについての不連続
解である。全変域の連続解ｕ_２Ｈ（ｘ）を計算するイン
ターポレーターは、次の関数を使用して連続解を計算す
る：

【００２９】

【数２】

【００３０】ここでＭは最初のメッシュの点、Ｍ_１ は
第２のメッシュの最近接点、∇ ｕ _２Ｈ｜_Ｍ１は解ｕ
_２Ｈ（ｘ）の勾配ベクトル、Ｈ（ＭＭ_１ ）はベクトル
ＭＭ_１ に適用する解のヘッセ行列式、ＭＭ_１ は座標
（ｘ１，ｙ１，ｚ１）の点Ｍ_１ から座標（ｘ，ｙ，ｚ）
の点Ｍへのベクトルを示す。

【００３１】さらにインターポレーターは、アナライザ
ー／ソルバーが計算した第２メッシュの解を、次の関係
を用いて最初のメッシュに投影する：

【００３２】

【数３】

【００３３】ここでｎｐは最初のメッシュにおける補間
点の数、Ｍ_ｉ は第２のメッシュ上にある座標（ｘｉ，
ｙｉ，ｚｉ）の点、Ｍ_{（ｉ＋１）} は第２のメッシュに
ある座標（ｘ（ｉ＋１），ｙ（ｉ＋１），ｚ（ｉ＋
１））の点である。

【００３４】インターポレーターは第２メッシュの解
を、次の関係を用いて最初のメッシュに投影する：

【００３５】

【数４】

【００３６】ここでｘは特殊点（最初のメッシュの点に
対応する点）、Ｍ_ｋ は、点ｘを含む第２メッシュ上に
おける要素Ｅの少なくとも一部を構成する点群、Ｎｅは
ユーザーが固定した補間点の総数、ｕ_２Ｈ（ｘ）は第２
メッシュの点の解に基づいて計算した変域全体の連続解
である。

【００３７】これらの誤差予測技法を使用することによ
り、高速化と適切な精度が同時に得られるのである。

【００３８】本発明のもう一つの側面として、メッシュ
生成に由来する線形行列方程式を解くアナライザー／ソ
ルバーの計算速度を高める手法を提供するという点があ
る。この手法では、Ｎ＊Ｎの線形連立方程式を生じる細
密メッシュが生成される。次に適応最適化基準を選択す
る。ここで、仮定的予測に基づいて最適のメッシュサイ
ズが得られる。次に、Ｍ＊Ｍ線形連立方程式（これはＮ
＊Ｎ線形連立方程式に対応）となる最適なメッシュサイ
ズの粗メッシュが生成され、Ｍ＊Ｍ線形連立方程式の最
初の解が求められる。最後に、Ｎ＊Ｎ線形連立方程式の
第２の解が、最初のＭ＊Ｍ線形連立方程式の解を補間す
ることにより計算される。このような本発明の特性とし
て、この線形連立方程式の計算速度が高められる。

【００３９】本発明でさらにもう一つの特徴は、アナラ
イザー／ソルバーが複数の中から一つ選ばれることであ
る。アナライザー／ソルバーのデータ構造は、その選択
されたものによって決まってくる。このようにして、こ
の手法はさまざまなアナライザー／ソルバーに使用する
ことができる。

【００４０】さらに、３次元オブジェクトの最初の解
は、そのオブジェクトの２次元表面にそれぞれ対応する
ようグループに分けられる。このようにして、本発明の
手法は、２次元と３次元の解を生成するアナライザー／
ソルバーに使用することができる。

【００４１】本発明の他の特徴は、第２の解の誤差はヘ
ッセ行列式に基づいて評価され、既定値範囲内になるか
どうかが評価される点である。誤差が既定値範囲内に収
まらない場合、より細密メッシュサイズのメッシュを新
たに生成し、それについて第２の解を計算する。このよ
うにして、適切な精度が確保される。

【００４２】本発明のもう一つの特徴は、上記のアナラ
イザー／ソルバーの外部ライブラリを使用したメッシュ
計算に由来する数値的アナライザー／ソルバーを使用し
て、線形行列方程式の解法を高速化したシステムである
という点である。本システムは、二レベルのメッシュ計
算で適応グリッド技術を活用している。このシステムは
細密メッシュから粗メッシュを計算し、粗メッシュにつ
いての方程式を解く。粗メッシュと細密メッシュ間の誤
差の補間は、評価手法、特に最小二乗法によって管理さ
れる。本発明によれば、アナライザー／ソルバーの高速
化はライブラリとして実行されるため、アナライザー／
ソルバーの内部コードは変更する必要がない。

【００４３】本発明３５の別の特徴として、プログラム
保存装置がある。このプログラム保存装置は、線形行列
方程式の高速化解法を実行するための手順プログラムを
物理的に保管するものである。この手法では、メッシュ
ジェネレーターが生成した細密メッシュを読み込んでＮ
＊Ｎ線形連立方程式とし、この細密メッシュに基づいて
仮定的予測により最適メッシュサイズを算出し、最適メ
ッシュサイズに基づき粗メッシュを生成して、Ｎ＊Ｎ線
形連立方程式に対応するＭ＊Ｍ線形連立方程式とし、ア
ナライザー／ソルバーに対してこのＭ＊Ｍ線形連立方程
式を解かせ、最初の解を得る。このＭ＊Ｍ線形連立方程
式の最初の解を補間することによりＮ＊Ｎ線形連立方程
式の第２の解を算出する。

【００４４】このプログラム保存装置には、複数のアナ
ライザー／ソルバーと複数のデータ構造との関係を保存
するモデルデータベースも含まれている。この手法では
さらに、複数のアナライザー／ソルバーのうちひとつを
選択する入力を受け取り、その選択に対応するデータ構
造を読み込むという手順も含まれている。

【００４５】

【本発明の具体的な詳細説明】本発明については以降の
詳細説明で詳しく説明される。この中で、本発明の具体
的かつ非制限的な例を挙げる図が複数参照されている。
これらの図全体を通じて、図中にある参照番号は、類似
の部品を示すものである。

【００４６】図１はＣＡＤ／ＣＡＭシステムおよびＣＡ
Ｄ／ＣＡＭシステム用のアナライザー／ソルバーを使用
した。本発明のアクセラレーターを示すブロック線図で
ある。ここで用いられるＣＡＤ／ＣＡＭシステムおよび
アナライザー／ソルバーは、現象を分析するためのメッ
シュ生成に由来する線形行列方程式を解くシステムと共
に使用される典型的な例である。市販されているＣＡＤ
／ＣＡＭシステム１は、幾何学的データを出力し、これ
が分析対象となるオブジェクトの境界となる。この幾何
学的データとは例えば、オブジェクトの境界を表わす基
本的な表面、辺、副変域などである。幾何学的データ構
造の詳細は、例えば”Ｔｒｉａｎｇｕｌａｔｉｏｎ ａ
ｎｄ Ｍｅｓｈｉｎｇ−Ａｐｐｌｉｃａｔｏｎ ｔｏ
Ｆｉｎｉｔｅ Ｅｌｅｍｅｎｔｓ”（Ｇｅｏｒｇｅ
Ｐ．Ｌ． ａｎｄ Ｂｏｒｏｕｃｈａｋｉ Ｈ． Ｄｅ
ｌａｕｎｅｙ， Ｈｅｒｍｅｓ １９９８年）の１０．
４節に示されているようなものである。本文書では、こ
の全内容が参考文献として明示的に織り込まれている。

【００４７】市販のメッシュジェネレーター２は、ＣＡ
Ｄ／ＣＡＭシステムからの幾何学的データを受け取り、
またキーボードやマウス、ディスク、テープなどの入力
装置を経由してユーザーからメッシュサイズや規則性、
要素数などのパラメータを受け取る。この幾何学的デー
タとパラメータに基づいて、メッシュジェネレーターは
メッシュデータ（細密メッシュデータ）を生成し、出力
する。このメッシュデータには、例えば、結節点、辺、
要素タイプ、打切りタイプなどが含まれている。メッシ
ュデータ構造の詳細は例えば、”Ｔｒｉａｎｇｕｌａｔ
ｉｏｎ ａｎｄＭｅｓｈｉｎｇ−Ａｐｐｌｉｃａｔｉｏ
ｎ ｔｏ Ｆｉｎｉｔｅ Ｅｌｅｍｅｎｔｓ”の１０．
６節に示されている。本文書では、この全内容が参考文
献として明示的に織り込まれている。

【００４８】本発明のアクセラレーター１０は、ＤＬＬ
（ダイナミックリンクライブラリ）ファイルなどのコン
ピューターライブラリとして提供されている。アクセラ
レーター１０は、メッシュジェネレーター２が生成した
細密メッシュデータを読み、この細密メッシュデータに
基づいて新たに粗メッシュデータを計算して、これをア
ナライザー／ソルバー３に出力する。

【００４９】アナライザー／ソルバー３は、受け取った
粗メッシュについて現象の分析をするため、あらかじめ
定められた線形方程式を解く。アクセラレーター１０
は、アナライザー／ソルバー３が計算した粗メッシュの
解を読み取り、これに基づいて細密メッシュの解を計算
する。つまり、解は粗メッシュの結節点について算出さ
れ、これを補間することにより変域内の連続解（すなわ
ちオブジェクト全体）を構成する。次にこの解が、細密
メッシュの結節点に投影され、補間されて、変域全体の
連続解が形成される。

【００５０】このようにして、本発明のアクセラレータ
ーは、市販のＣＡＤ／ＣＡＭシステムやメッシュジェネ
レーター、アナライザー／ソルバーに外部的に接続さ
れ、アナライザー／ソルバーの予備処理・後処理を行な
う装置としてプロセスを高速化する。アナライザー／ソ
ルバーの高速化は、アナライザー／ソルバーの実行コー
ドやソースコードの変更なしに実現することができる。

【００５１】上記の説明は、ＣＡＤ／ＣＡＭシステムに
ついて述べたものである。だが本発明のアクセラレータ
ーは、ＣＡＤ／ＣＡＭだけでなく、メッシュ生成に由来
する線形行列方程式を使用する（および解く）システム
である、ＧＩＳシステムや３次元描画システムにも使用
することができる。ＣＡＤ／ＣＡＭシステムやＧＩＳシ
ステム、３次元描画システムには、市販品が数多くあ
る。また、これらのシステムで作成されたオブジェクト
において生じる現象を分析するアナライザー／ソルバー
も数多く市販されている。これらの例を図５に挙げる。

【００５２】本出願書において、「アナライザー／ソル
バー」という語は、ＣＡＤシステムなどに使用されてい
る「ソルバー」と、ＧＩＳシステムに使用されている
「アナライザー」の両方を含める一般的な用語として使
用されている。

【００５３】図２は本発明のアクセラレーター１０の構
成を示すブロック線図である。メッシュジェネレーター
２（図１）で生成された細密メッシュデータが、粗メッ
シュオプチマイザー１０１に入力されている。

【００５４】粗メッシュオプチマイザーは、入力装置か
らのユーザー入力により精度指定を受け取る。粗メッシ
ュオプチマイザー１０１は、細密メッシュデータに基づ
いて、入力精度を達成できると思われる最適な粗メッシ
ュを見積る。このメッシュ（数値的メッシュは、一連の
パラメータとして表現される。このパラメータに含まれ
るのは、サイズ、結節点の数、要素の数、規則性、直交
性である。ここでは、サイズと結節点数、要素数だけが
使用されている。

【００５５】さらに詳しく述べると、この粗メッシュオ
プチマイザー１０１は、２つの手法によって最適な粗メ
ッシュを予測している。最初の最適な粗メッシュを計算
する際、粗メッシュのパラメーター（サイズ、結節点
数、要素数）は、細密メッシュのサイズの比として決定
され、仮定的予測に基づいたデフォルト値として与えら
れる（前記”Ｈａｎｄｂｏｏｋ ｏｆ Ｇｒｉｄ Ｇｅ
ｎｅｒａｔｉｏｎ”を参照）。計算されたパラメーター
は、粗メッシュジェネレーター１０２に送られ、ここ
で、対応する最初の粗メッシュが生成される。最初の粗
メッシュが生成されたら、指定された精度が得られるよ
う、解のヘッセ行列式（２次導関数）の評価により、粗
メッシュのサイズを調整する。（前記”Ｄｅｌａｕｎｅ
ｙ Ｔｒｉａｎｇｌｕｌａｔｉｏｎ ａｎｄ Ｍｅｓｈ
ｉｎｇ−Ａｐｐｌｉｃａｔｉｏｎ ｔｏ Ｆｉｎｉｔｅ
Ｅｌｅｍｅｎｔｓ”を参照）。

【００５６】粗メッシュジェネレーター１０２は、粗メ
ッシュサイズオプチマイザー１０１によるパラメーター
入力に従って、粗メッシュを生成し、これをアナライザ
ー／ソルバー３に出力する。

【００５７】粗メッシュジェネレーター１０２は必ずし
も、メッシュジェネレーター２と物理的に別個である必
要はない（図１参照）。すなわち粗メッシュオプチマイ
ザー１０１は、市販のメッシュジェネレーター２に対し
てパラメーターを出力し、メッシュジェネレーター２に
粗メッシュを生成させる。この場合、メッシュジェネレ
ーター２が生成した粗メッシュをアナライザー／ソルバ
ー３に送るために、コントローラー（ソフトウェア）が
提供されることになる。

【００５８】ここでは、ＣＡＤシステム１が３次元オブ
ジェクトを取り扱い、メッシュジェネレーター２および
粗メッシュジェネレーター１０２が３次元メッシュデー
タを生成するものと仮定して説明を進める。このアナラ
イザー／ソルバーは、３次元メッシュや、３次元オブジ
ェクトの表面メッシュ、２次元メッシュ、２次元層状メ
ッシュなど、そのアナライザー／ソルバーのタイプに応
じて、解を算出することができる。インターポレーター
１０５は、各タイプのメッシュについて開発されてい
る。２次元メッシュや表面メッシュを扱うインターポレ
ーターについては、２次元デコンポーザー１０４が用意
されていて、粗グリッドの３次元解データを受け取り、
これを２次元解に変換して、インターポレーター１０５
が扱えるデータに加工する。このようにして、インター
ポレーターはあらゆる種類のアナライザー／ソルバーに
適用することができる。ＣＡＤシステムやメッシュジェ
ネレーター、アナライザー／ソルバーが２次元データし
か生成しない場合は、２次元デコンポーザーは不要であ
る。

【００５９】インターポレーター１０５は、細密メッシ
ュにおける対応する解を得るために、粗メッシュの解を
補間する。インターポレーターの詳細は後述する。

【００６０】誤差エスチメーター１０６は、インターポ
レーター１０５から細密メッシュの解を受け取り、ヘッ
セ行列式に基づいて誤差を評価する。誤差エスチメータ
ー１０６は、アナライザー／ソルバー３とは独立のアク
セラレーターの一部として提供することができる。ただ
し、市販のアナライザー／ソルバーは通常、それぞれの
誤差エスチメーターを内蔵していることが多い。よっ
て、このシステムはアナライザー／ソルバーの誤差エス
チメーターを利用することもできる。言い換えると、イ
ンターポレーター１０５は補間による解をアナライザー
／ソルバー３に送り、誤差をアナライザー／ソルバーに
計算させることができる。適切な解の精度が得られた場
合（すなわち、誤差が既定の閾値の範囲内である場
合）、細密メッシュの解をフォーマット変換器１１０に
送り、解データのフォーマットをＧＵＩデータに変換す
る。このＧＵＩデータはＣＡＤ（ＧＩＳまたは３次元）
システムのファイル形式と互換性があるため、ＣＡＤシ
ステム上で表示させることができる。一方、解が適切で
ない場合は、誤差エスチメーター１０６が粗メッシュサ
イズオプチマイザー１０１に対して、誤差が大きすぎる
（すなわち、粗メッシュが大きすぎる）ことを通知す
る。すると、粗メッシュサイズオプチマイザー１０１が
メッシュサイズを変更（例えば、メッシュの結節点数を
増加）し、改訂したメッシュサイズに基づいて新たなメ
ッシュを生成するよう、粗メッシュジェネレーター１０
２に指示を送る。そして新しいメッシュについて、新た
な解が算出される。

【００６１】ソルバーセレクター１０３と、モデルデー
タベース１０９は、さまざまな種類のアナライザー／ソ
ルバー３と共に使用するアクセラレーター１０を使用可
能にするために供給される。アナライザー／ソルバーが
異なると、入力データ構造や出力データ構造、方程式に
よって分析する現象の種類なども異なってくる。よって
アクセラレーター１０は、アナライザー／ソルバーと互
換性のあるデータ構造になるようデータ構造を変換し、
アナライザー／ソルバーからの出力データ構造も、アク
セラレーターが使用できるデータ構造に変換しなければ
ならない。どのモデルのソルバーが何のデータ構造を使
用しているかを知るため、モデルデータベースには、ア
ナライザー／ソルバーの各種モデルと、それぞれに使用
されている入出力データ構造の情報が保管されている。

【００６２】詳しく説明すると、アナライザー／ソルバ
ーのデータ構造は（１）次元、（２）立体幾何学、
（３）ソルバーのタイプ、といった一連の基準に従って
分類される。このソルバーのタイプは、（ａ）ソフトウ
ェアのタイプ、（ｂ）エンジニアリング、（ｃ）用途、
（ｄ）特性、（ｅ）モデルタイプ、（ｆ）対象、（ｇ）
数値処理手法、などで区分される。

【００６３】実際に使用する際、ユーザーは、使用した
いアナライザー／ソルバーのモデルを入力する。すると
ソルバーセレクター１０３がそのモデル入力を受け取
り、モデルデータベースからそのモデルの入・出力デー
タ構造を読み込む。ソルバーセレクター１０３は、その
入力データ構造を粗メッシュジェネレーター１０２に出
力し、これにより粗メッシュジェネレーター１０２が、
アナライザー／ソルバーの要求する入力データ構造で粗
メッシュを出力することができる。オプションとして、
この出力データ構造を２次元デコンポーザーに送り、こ
の２次元デコンポザーが、アナライザー／ソルバーの３
次元出力を、インターポレーター１０５のデータ形式の
２次元データに変換することもできる。

【００６４】粗メッシュオプチマイザーが最適メッシュ
サイズを計算し、インターポレーターが補間計算を、ま
た２次元デコンポザーが２次元への変換を実行している
間は、幾何学的データベース１０７とメッシュデータベ
ース１０８が使用されている。

【００６５】幾何学的データベース１０７は、任意の３
次元オブジェクトの幾何学的特性を抽出・分類するため
のものである。この幾何学的データベース１０７は、連
結した一連のフィールドとして構成されている。それぞ
れのフィールドは、一連のパラメータと関連付けられて
いる。次に、フィールドとそれに対応するパラメータの
例を挙げる（「フィールド：パラメータ」の形式）。

【００６６】（１）平面状表面：（ａ）表面の原点の３
次元座標、（ｂ）平面の基本ベクトル２つについての３
要素。

【００６７】（２）円柱状表面：（ａ）基底の中心原点
の３次元座標、（ｂ）円柱の基本ベクトル２つについて
の３要素。

【００６８】（３）頂点と線分：（ａ）基準点、（ｂ）
スプライン補間の度合。

【００６９】（４）基準点：基準点の座標。

【００７０】（５）副変域：オブジェクトの部品番号。

【００７１】球状表面やプリズム状表面などについて
も、一連のパラメーターと関連付けたフィールドとして
保存することができる。フィールドの例として挙げたよ
うに、あるフィールド（頂点と線分）のパラメータ（基
準点）を、別のフィールドにすることができる。

【００７２】ここでは、ＡＣＣＥＳＳ（マイクロソフト
社製品）などのデータベースソフトウェア利用によって
もこのデータベースを使用することができる。もちろ
ん、その他の適切なソフトウェア使用についても、本発
明申請の範囲内である。

【００７３】メッシュデータベース１０８は、メッシュ
ジェネレーター２が生成したメッシュのデータを抽出・
分類するためのものである。このメッシュデータベース
１０８は、一連のフィールドとして構成されている。そ
れぞれのフィールドは、一連のパラメータと関連付けら
れている。

【００７４】次に、フィールドとそれに対応するパラメ
ータの例を挙げる（「フィールド：パラメータ」の形
式）。

【００７５】（１）制御基準：（ａ）メッシュの次元、
（ｂ）結節点の数、（ｃ）要素の数、（ｄ）規則性、
（ｅ）直交性、など。

【００７６】（２）タイプ：（ａ）三角形、（ｂ）四辺
形、（ｃ）四面体、（ｄ）五面体、など。

【００７７】（３）結節点番号：（ａ）結節点の指数、
（ｂ）結節点のｘ座標、ｙ座標、ｚ座標、など。

【００７８】（４）要素番号：（ａ）要素の指数、
（ｂ）頂点の連結度（要素に属するもの）、など。

【００７９】（５）メッシュの幾何学的要素：（ａ）各
要素指数についての頂点の数 メッシュデータベース１０７は、ＡＣＣＥＳＳなどのデ
ータベースソフトウェア利用によっても使用することが
できる。もちろん、その他の適切なソフトウェア使用に
ついても、本発明申請の範囲内である。

【００８０】フィールドに対応する幾何学的データは、
幾何学的データベースに入力され、対応するパラメータ
が返される。一方、そのフィールドに対応するメッシュ
データは、メッシュデータベースに入力され、対応する
パラメータが返される。これらのパラメータは、補間や
メッシュ最適化などの計算に使用される。

【００８１】幾何学的データベースは、表面メッシュが
使用されるときに限り使用される。メッシュデータベー
スは、メッシュ最適化および補間のための方程式に幅広
く活用される： （１）式（Ａ）において、任意の結節点に対する近接要
素の選択に用いる。

【００８２】（２）式（Ｄ）において、要素数および結
節点の座標の計算に用いる。

【００８３】式（Ａ）と（Ｄ）については後述する。

【００８４】本発明と、この幾何学的データベース、メ
ッシュデータベース、モデルデータベースにより、粗メ
ッシュの解を（ソルバーで）読むコンピューターコード
は、インターポレーターおよび適切な関係Ｐ_ｋ （ｘ）
（これについては後述する）を使用して、細密メッシュ
にこの解をマッピングし、解を正しい出力形式に変換
し、その結果の画像化を行なうＧＵＩと同様に、外部コ
ンピューターライブラリに格納される。この外部コンピ
ューターライブラリは、使用するＣＡＤ（またはＧＩＳ
や３次元描画）システムやソルバー、メッシュジェネレ
ーター、プラットフォーム（Ｗｉｎｄｏｗｓ ＮＴ（登
録商標）やＵＮＩＸ（登録商標）など）の各タイプによ
って異なる。外部コンピューターライブラリは、ＣＤや
フロッピーディスク（登録商標）などの記録媒体で使用
することができる。また、インターネットなどのネット
ワークを通じて利用することもできる。

【００８５】図３は、本発明のアクセラレーターの働き
を図解したフローチャートである。本発明の基本的な手
法は、適応メッシュ技法と計算の予備処理に基づいてい
る。本手法の主眼は、粗メッシュについて問題（方程
式）を解くという点にある。これ以降、粗メッシュの解
が細密メッシュ上に投影される。

【００８６】最初のステップＳ３００では、分析するオ
ブジェクトの幾何学的データがＣＡＤシステムで作成さ
れ、メッシュジェネレーターに送られる。また、問題の
種類に応じて、熱伝導度や電気伝導度などのオブジェク
トの特性も入力される。これらの特性が、アナライザー
／ソルバーで解く線形方程式の条件を形成するものとな
る。

【００８７】ステップＳ３０１では、Ｎ＊Ｎ線形連立方
程式ＡＵ１＝Ｂをもたらす最初の（細密な）メッシュＭ
１が生成される。Ｎは、細密メッシュＭ１の結節点数に
対応する。細密メッシュＭ１は、構造化・非構造化グリ
ッドの従来型アルゴリズムを使用した従来型のメッシュ
ジェネレーター２によって生成されるものである。非構
造化グリッドの従来型アルゴリズムとは例えば、”Ｈａ
ｎｄｂｏｏｋ ｏｆＧｒｉｄ Ｇｅｎａｒａｔｉｏｎ”
（Ｔｈｏｍｐｓｏｎ Ｊ．Ｆ．， ＢＫ Ｓｏｎｉ ａ
ｎｄ Ｗｅａｔｈｅｒｉｌｌ ＮＰ， ＣＲＣ Ｐｒｅ
ｓｓ， １９９９年）に記載されているＤｅｌａｕｎｅ
ｙアルゴリズムなどである。本文書では、この全内容が
参考文献として明示的に織り込まれている。構造化グリ
ッドの従来型アルゴリズムは、曲線グリッドであり、こ
れも上記の”Ｈａｎｄｂｏｏｋｏｆ Ｇｒｉｄ Ｇｅｎ
ｅｒａｔｉｏｎ”に記載されている。これらアルゴリズ
ムは、パラメータによるメッシュ化の一種である。パラ
メーターによるメッシュ化についての詳細は、例えば、
上記の”Ｈａｎｄｂｏｏｋ ｏｆ ＧｒｉｄＧｅｎｅｒ
ａｔｉｏｎ”の他に、”Ｉｎｔｒｏｄｕｃｔｉｏｎ ａ
ｌ’ａｎａｌｙｓｅ ｎｕｍｅｒｉｑｕｅ ｄｅｓ
ｅｑｕａｔｉｏｎｓ ａｕｘ ｄｅｒｉｖｅｅｓ ｐａ
ｒｔｉｅｌｌｅｓ”（Ｒａｖｉａｒｔ Ｐ．Ａ． ａｎ
ｄ Ｊ．Ｍ． Ｔｈｏｍａｓ， Ｅｄｉｔｉｏｎｓ Ｍ
ａｓｓｏｎ（フランス語）１９８８年）、また構造化メ
ッシュについては”Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏｎ
ｕｍｅｒｉｃａｌ ｌｉｎｅａｒ ａｌｇｅｂｒａ ａ
ｎｄ ｏｐｔｉｍｉｚａｔｉｏｎ”（Ｃｉａｒｌｅｔ
Ｐ．Ｇ． Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ
Ｐｒｅｓｓ， １９８９年）、非構造化メッシュにつ
いては上記の”Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｎｕ
ｍｅｒｉｃａｌ ｌｉｎｅａｒ ａｌｇｅｂｒａ ａｎ
ｄ ｏｐｔｉｍｉｚａｔｉｏｎ”や”Ｄｅｌａｕｎｅｙ
Ｔｒｉａｎｇｕｌａｔｉｏｎ ａｎｄ Ｍｅｓｈｉｎ
ｇ−Ａｐｐｌｉｃａｔｉｏｎ ｔｏ Ｆｉｎｉｔｅ Ｅ
ｌｅｍｅｎｔｓ”（Ｇｅｏｒｇｅ Ｐ．Ｌ． ａｎｄ
Ｂｏｒｏｕｃｈａｋｉ Ｈ．， Ｈｅｒｍｅｓ １９９
８年）に記載されている。これらの、メッシュパラメー
ターの詳細な説明や全報告内容は、本文書全体で明示的
に織り込まれている。

【００８８】ステップＳ３０２では、予測と誤差制御に
使用される適応最適化基準σ（Ｍ１，Ｕ１，−）が選択
される。ここで、σ（Ｍ１，Ｕ１，−）は最小二乗法で
ある。Ｍ１はステップＳ３０１で定義された細密メッシ
ュである。Ｕ１はＭ１について基本方程式（Ｎ＊Ｎ線形
方程式）の打切りから算出される解である。

【００８９】ステップＳ３０３においては、最初の最適
化粗メッシュＭ２が、細密メッシュデータのサイズに関
する仮定的誤差予測に基づいて決定される。（仮定的予
測の基本理論は、上記の”Ｈａｎｄｂｏｏｋ ｏｆ Ｇ
ｒｉｄ Ｇｅｎｅｒａｔｉｏｎ”に記載されている。）
最適の粗メッシュを見出すというのは、そのメッシュを
表現する一連のパラメーターを見出すことと同義であ
る。パラメーターのひとつはメッシュサイズＨである。
またその他に、結節点の数、要素数、規則性、直交性な
どがある。前に述べたように、本発明では、メッシュサ
イズと結節点の数、要素の数だけを考慮している。これ
らのパラメータは、仮定的予測に基づき、デフォルト値
として与えられる。

【００９０】ステップＳ３０２とＳ３０３は、図２の粗
メッシュオプチマイザー１０１が生成した最初の最適な
粗メッシュの計算に相当するものである。

【００９１】ステップＳ３０４では、現像方程式の解を
得るためのアクセラレーターと共に使用する特定のアナ
ライザー／ソルバーを、ユーザーが選択して入力する。
選択されたアナライザー／ソルバーの入出力データ構造
は、モデルデータベース１０９に参照することにより決
定される。

【００９２】ステップＳ３０５では、これらのパラメー
ターに従って、粗メッシュが生成される。

【００９３】ステップＳ３０６では、アナライザー／ソ
ルバーが、Ｎ＊Ｎ線形連立方程式ＡＵ１＝Ｂに対応する
Ｍ＊Ｍ線形連立方程式Ａ’Ｘ’＝Ｂ’を構成する。アナ
ライザー／ソルバーはＭ＊Ｍ線形連立方程式Ａ’Ｘ’＝
Ｂ’を解き、メッシュＭ２上の各結節点について不連続
解を得る。ここでメッシュＭ２は３次元メッシュである
ため、結節点も３次元空間に分配される。

【００９４】ステップＳ３０６−１では、補間を２次元
（表面）で行なうか、それとも３次元オブジェクトで行
なうかをチェックする。インターポレーターが３次元メ
ッシュを使用する場合、アナライザー／ソルバーからの
解は直接インターポレーターに送られる。すなわち、ス
テップＳ３０８に進むことになる。だがインターポレー
ターが２次元メッシュまたは２次元表面メッシュを使用
する場合は、アナライザー／ソルバーからの解を変換す
るため、ステップＳ３０７に進む。

【００９５】ステップＳ３０７では、メッシュＭ２の不
連続解をグループに分け、ひとつのグループにはひとつ
の２次元表面にある結節点の不連続解群が含まれるよう
にする。（３次元の幾何学的データを分解することによ
り、複数の２次元表面が得られる。）それぞれのグルー
プについて順に、補間計算が実施される。

【００９６】ステップＳ３０８では、（メッシュＭ２
の）Ｍ＊Ｍ線形連立方程式の補間により、（メッシュＭ
１の）Ｎ＊Ｎ連立方程式の解が得られる。ステップＳ３
０８はインターポレーター１０５によって実行される。
このステップＳ３０８の詳細については後述する。

【００９７】ステップＳ３０９では、アナライザー／ソ
ルバーによりＮ＊Ｎ線形連立方程式の解の誤差が計算さ
れる。

【００９８】ステップＳ３１０では、その誤差が既定値
Ｔよりも小さいかどうかが判定される。Ｔはユーザーが
選択・入力する値である。Ｔは精度入力から導くことも
できる。誤差がＴよりも小さい場合、手順はＳ３１１に
進む。誤差がＴより大きい場合は、Ｓ３１２に行く。

【００９９】ステップＳ３１１では、メッシュＭ２のＮ
＊Ｎ線形連立方程式解のデータ形式を、ＧＵＩ形式に変
換する。つまり、ＣＡＤシステムがその分析結果をグラ
フィカルに表示できるようなデータに変換してやるので
ある。

【０１００】ステップＳ３１２では、ヘッセ行列式によ
る評価に基づいて、粗メッシュのパラメーターを調整す
る。粗メッシュの解と細密メッシュの解との間の相違
（誤差）を縮めるために、粗メッシュの誤差を、粗メッ
シュの計算をするアナライザー／ソルバーから得る。誤
差を小さくするには、縮小できる関連パラメーターの誤
差を探し出し、この誤差を最小限にする。数学的には、
次のように表現される。

【０１０１】Ｍをこのパラメーター群とすると、最適な
メッシュとは、σ（Ｍ１，Ｕ１，Ｍ）を最小化する最適
パラメーターを見つけることと同義である。ここで、σ
（Ｍ１，Ｕ１，Ｍ）は次のように定義される：

【０１０２】

【数５】

【０１０３】ｕ_２ｈ（ｘ）は、メッシュＭ１上で計算さ
れる解である。ｕ_２ｈ（ｘ）は連続解であり、ａ２（ｈ
個のベクトル）の不連続解を補間して得られるもので、
Ｎ＊Ｎ線形行列方程式の解である。ｕ_２Ｈ（ｘ）はメッ
シュＭ２上で計算される解である。ｕ_２Ｈ（ｘ）は非連
続解であり、ａ２（Ｈ個のベクトル）の不連続解を補間
して得られるもので、Ｍ＊Ｍ線形行列方程式の解であ
る。（これはＳ３０６の段階である。）ｃは第２回目に
加わる加重関数である。ＬおよびＢはアナライザー／ソ
ルバーの種類によって決まるもので、ユーザーが定義す
る演算子である。Ωは変域、Γは分析するオブジェクト
の境界である。（Ａ）の計算は従来の手法で算出でき、
特にＣＡＤ・ＧＩＳについての詳細は”Ｎｕｍｅｒｉｃ
ａｌ Ｓｏｌｕｔｉｏｎ ｏｆ Ｐａｒｔｉａｌ Ｄｉ
ｆｆｅｒｅｎｔｉａｌ Ｅｑｕａｔｉｏｎｓ ｉｎ Ｓ
ｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ”（Ｌ
ａｐｉｄｕｓ Ｌ． ａｎｄ Ｇ．Ｆ． Ｐｉｎｄｅ
ｒ， Ｊｏｈｎ Ｗｉｌｅｙ＆ Ｓｏｎｓ， １９８２
年）に記載されている。本文書では、この本の全内容が
参考文献として明示的に織り込まれている。３次元グラ
フィックスつにいては、”Ｃｏｍｐｕｔｅｒ Ｇｒａｐ
ｈｉｃｓ”（Ｆｏｒｌｅｙ， Ｖａｎ Ｄａｍ， Ｆｅ
ｉｎｅｒ， ａｎｄ Ｈｕｇｈｅｓ， Ａｄｄｉｓｏｎ
Ｗｅｓｌｅｙ， １９９７年）に詳細が記されてい
る。本文書にはこの本の全内容が参考文献として明示的
に織り込まれている。

【０１０４】新たに計算されたパラメーターをもって手
順はＳ３０５に戻り、小さなメッシュサイズ（すなわち
大きな要素数）の問題を解く。最小二乗法（全体的なＬ
２投影）の使用により、粗メッシュから細密メッシュへ
の解の投影における誤差は最小化される。

【０１０５】上に述べたフローチャートのうち、Ｓ３０
１〜Ｓ３０３，Ｓ３０５，Ｓ３０８は主に、計算の高速
化に貢献している。Ｓ３０９，Ｓ３１０，Ｓ３１２は、
最初の回で適切な精度が得られなかった場合のステップ
である。ここで提案されている最適化基準（後述する最
小二乗法に従って）と補間を組合せることにより、高速
化が達成される。ステップＳ３０４は、さまざまな分析
ソフトウェア（ソルバー）と共に使用できるようにする
ためのものである。

【０１０６】図４はステップＳ３０８の詳細を示すフロ
ーチャートである。

【０１０７】ステップＳ４０１では、Ｍ＊Ｍ線形連立方
程式における不連続の結節点解（ａ _２ｉ，ｉ＝１…Ｈ）
をアナライザー／ソルバー３から受け取る。ａ_２ｉは粗
メッシュＭ１におけるメッシュ結節点Ｍ_ｉ についての
解である。ここでａ_２ｉの補間を行ない、オブジェクト
全体の解ｕ_２Ｈ（ｘ）を得る。ここでｘはオブジェクト
の任意の点である。ｕ_２Ｈ（ｘ）は、次の式によって得
られる点の値ａ_２ｉから見積られる解ｕ_２Ｈ（ｘ）の局
所的予測値を使用して計算される。すなわち、粗メッシ
ュＭ２の結節点の不連続解は、変域全体に解をもつよう
補間される。

【０１０８】

【数６】

【０１０９】ここでＭはメッシュＭ１の点（結節点）、
Ｍ_１ とＭ_２ はメッシュＭ２に属する２つの最近接点
（結節点）である。

【０１１０】∇ ｕ｜_Ｍ１は解ｕ_２Ｈの勾配ベクトルで
あり、Ｈ（ＭＭ_１ ）はベクトルＭＭ_１ に当てはまる
解のヘッセ行列式である。ＭＭ_１ は座標（ｘ１，ｙ
１，ｚ１）の点Ｍ_１ から座標（ｘ，ｙ，ｚ）の点Ｍま
でのベクトルを意味する。ベクトルＭＭ_１ の要素は、
参照系（ｘ−ｘ１，ｙ−ｙ１，ｚ−ｚ１）内にある。

【０１１１】勾配ベクトルで∇ｕ｜_Ｍ１の２点の近似値
は、次の式で見積られる：

【０１１２】

【数７】

【０１１３】この式は、導関数の古典的な差分推定を３
次元で一般化したものである。この生成式の詳細は、前
に述べた”Ｎｕｍｅｒｉｃａｌ Ｓｏｌｕｔｉｏｎ ｏ
ｆＰａｒｔｉａｌ ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｑｕ
ａｔｉｏｎｓ ｉｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇ
ｉｎｅｅｒｉｎｇ”に記載されている。

【０１１４】この概算式を使用することにより、明らか
に、Ｍ_１ とＭ_２ で粗メッシュの解の値を使用して、
ｕ_２Ｈ（ｘ）が計算される。

【０１１５】

【数８】

【０１１６】この最後の概算によって、ＭＭ_１ の方向
において勾配のみが計算される。使用される要素のタイ
プに応じて、次のように補間を一般化することができ
る。

【０１１７】

【数９】

【０１１８】ここでｎｐは、補間に使用されたメッシュ
Ｍ２の補間点の数である。

【０１１９】補間は、他の方法でも行なうことができ
る。例えば、ｕ_２Ｈ（ｘ）を計算する最も単純な方法
は、補間関数Ψ_ｉ （ｘ）を、メッシュＭ２の補間関数
として使用することである。Ψ_ｉ （ｘ）はアナライザ
ー／ソルバーによって決まってくる。補間関数Ψ
_ｉ （ｘ）は線形補間とすることもできる。

【０１２０】ステップＳ４０２では、移転関数Ｐ
_ｋ （ｘ）が計算される。上の式より、多項式Ｐ
_ｋ （ｘ）は簡単に計算することができる。

【０１２１】２点近似は次の式で行なわれる：

【０１２２】

【数１０】

【０１２３】細密メッシュの各点についてｕ_２Ｈ（ｘ）
を計算した後、次の式を用いてヘッセ行列式の要素を見
積ることができる：

【０１２４】

【数１１】

【０１２５】この式は、細密メッシュの各点に使用され
る。このヘッセ行列式の見積りは、前記の”Ｄｅｌａｕ
ｎｅｙ Ｔｒｉａｎｇｕｌａｔｉｏｎ ａｎｄ Ｍｅｓ
ｈｉｎｇ−Ａｐｐｌｉｃａｔｉｏｎ ｔｏ Ｆｉｎｉｔ
ｅ Ｅｌｅｍｅｎｔｓ”１２章にある見積りを使った粗
メッシュのサイズ計算に使用することができる。

【０１２６】ステップＳ４０３では、ｕ_２ｈ（ｘ）の近
似Ｕｌａｐｐ（ｘ）を、次のようにＰ_ｋ （ｘ）とｕ
_２Ｈ（ｘ）を使用して計算する。Ｕｌａｐｐ（ｘ）＝Σ
Ｐ_ｋ（ｘ）ｕ_２Ｈ（Ｍ_ｋ ），ｋ＝１…Ｎｅ、ここでｘ
は特殊点、すなわち細密メッシュＭ１の結節点に対応す
る点である。Ｍ_ｋ は、点ｘを含む粗メッシュＭ２上に
おいて要素Ｅのほとんど（すべてではないが）を少なく
とも一部を構成する点群、Ｎｅはユーザーが固定した補
間点の総数である。

【０１２７】ステップＳ４０４では、細密メッシュＭ１
の各結節点について、Ｕｌａｐｐ（ｘ）計算結果の補間
により、連続解ｕ_１ｈ（ｘ）が計算される。この補間
は、アナライザー／ソルバーに付随のデフォルトの補間
関数に従って計算することができる。例えば、線形の補
間を使用することができる。

【０１２８】よって、ｕ_１ｈ（ｘ）は解としての出力に
なる。

【０１２９】従来型のアナライザー／ソルバーでは、ｕ
_１ｈ（ｘ）はＮ＊Ｎ線形方程式を解いて不連続解
ａ_１ｊ，ｊ＝１…ｈを算出し、ソルバーにある補間関数
φ_ｉ （ｘ）を使用してａ_１ｊを補間する。一方、本発
明では、Ｎ＊Ｎ線形行列方程式をソルバーで解くことは
しない。代わりにａ_１ｊの解を使用して近似Ｕｌａｐｐ
（ｘ）を計算する。従って、計算時間が短縮される。ま
た同時に、本発明では次の組合せにより良好な近似解を
得ることができる。

【０１３０】（１）仮定的予測から、最初の最適粗メッ
シュを決める。

【０１３１】（２）上記の補間により移転関数Ｐ
_ｋ （ｘ）が得られる。

【０１３２】（３）式（Ｄ）を用いて、ｕ_２Ｈ（ｘ）が
見積られる。

【０１３３】（４）式（Ａ）の最小二乗法により、最初
の粗メッシュが調整される。

【０１３４】上記のようにして本発明では、望ましい精
度の解を得る処理時間が高速化される。

【０１３５】このように本発明は基本的処理の数が少な
く押えられている。ステップＳ３０８において補間が線
形である場合は、直接反転法の処理の桁はＯ（Ｍ^３ ）
＋Ｎ＊Ｍ＝Ｏ（Ｍ^３ ）となる。上記のようにＭ＊Ｍ線
形方程式の解は従来型の（市販の）アナライザー／ソル
バーで計算される。ＮとＭの比が１０の桁である場合、
同じ精度を得るのに、必要となる計算労力が１０^３ の
桁で減少する。

【０１３６】よってこの方法により、計算労力の理論的
な高速化は、１０^３ の桁で実現される。

【０１３７】実際の計算時間の高速化は、使用するアナ
ライザー／ソルバーやプラットフォーム、メッシュジェ
ネレーターそれぞれによって異なる。実地の試験によれ
ば、計算時間は約１／２０〜１／６０に短縮されてい
る。

【０１３８】以降では、最適メッシュの選択についての
最適化基準、および粗メッシュと細密メッシュとの間の
補間の移転関数が導かれた理論について説明する。この
導出は、最小二乗法の式に基づくものである。

【０１３９】Ａ．概説 最小二乗法の式は、次のような境界値の問題として記述
され得る：

【０１４０】

【数１２】

【０１４１】ここでＬは線形または非線型の微分演算
子、Ｂは線形演算子、Ωは変域、Γは外表面の境界であ
る。

【０１４２】一般的な最小二乗法は、次の最小化問題に
よって方程式化される：

【０１４３】

【数１３】

【０１４４】パラメーターｐは一般に、関数ＬｖがＬ
^２ （Ω）に属するように選ばれる。ノルム‖・‖はス
カラー積＜．，．＞に関連し、部分空間Ｖ_ｇ 上で定義
される。

【０１４５】問題（Ｐ）の内部近似は、有限次元の閉じ
た部分空間Ｖ_ｇ の集合｛Ｖ_ｈ ｝ _ｈ として定義する
ことができる。これは次の条件を満たす：

【０１４６】

【数１４】

【０１４７】これについては”Ｎｕｍｅｒｉｃａｌ Ｍ
ｅｔｈｏｄｓ ｆｏｒ Ｎｏｎｌｉｎｅａｒ Ｖａｒｉ
ａｔｉｏｎａｌ Ｐｒｏｂｌｅｍｓ． Ｓｐｒｉｎｇｅ
ｒＳｅｒｉｅｓ ｉｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ
Ｐｈｙｓｉｃｓ”（Ｇｌｏｗｉｎｇｓｋｉ Ｒ．， Ｓ
ｐｒｉｎｇｅｒ Ｖｅｒｌａｇ， １９８６年）を参
照。この近似の詳細つにいて、本文書では、この全内容
が参考文献として明示的に織り込まれている。

【０１４８】内部的近似としては例えば、有限要素法分
析を使用して達成することができる。このアプローチで
は、閉じた変域Ωは、多角形変域Ω_ｈ により近似され
る。ここでΩ_ｈ には標準的な三角形分割τ_ｈ が用い
られ、τ_ｈ は有限要素Ｅの集合である。このアプロー
チの詳細は、”Ｉｎｔｒｏｄｕｃｔｉｏｎ ａ ｌ’ａ
ｎａｌｙｓｅ ｎｕｍｅｒｉｑｕｅ ｄｅｓ ｅｑｕａ
ｔｉｏｎｓ ａｕｘｄｅｒｉｖｅｅｓｐａｒｔｉｅｌｌ
ｅｓ”（Ｒａｖｉａｒｔ Ｐ．Ａ． ａｎｄＪ．Ｍ．
Ｔｈｏｍａｓ， Ｅｄｉｔｏｎｓ Ｍａｓｓｏｎ（フラ
ンス語）１９８８年）に記載されている。

【０１４９】ここでソボレフ空間Ｈ^ｐ （Ω）はτ_ｈ
において次のように近似される。

【０１５０】

【数１５】

【０１５１】ここでＰ_ｐ は、次元がｐよりも低い１変
数、２変数、３変数の多項式空間である。計算コードが
大きいため、放物線型の問題処理で単要素の補間には、
通常、ラグランジュ関数およびエルミート補間関数が使
用される。詳しくは、前述の文献”Ｉｎｔｒｏｄｕｃｔ
ｉｏｎ ａ ｌ’ａｎａｌｙｓｅ ｎｕｍｅｒｉｑｕｅ
ｄｅｓ ｅｑｕａｔｉｏｎｓ ａｕｘ ｄｅｒｉｖｅ
ｅｓ ｐａｒｔｉｅｌｌｅｓ”および”Ｎｕｍｅｒｉｃ
ａｌ Ｓｏｌｕｔｉｏｎ ｏｆ Ｐａｒｔｉａｌ Ｄｉ
ｆｆｅｒｅｎｔｉａｌ Ｅｑｕａｔｉｏｎｓ ｉｎ Ｓ
ｃｉｅｎｃｅａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ”に記載
されている。

【０１５２】全体的補間関数のベクトルは、次のように
定義される：

【０１５３】

【数１６】

【０１５４】形式的に、関数ｕ_ｈ ∈ Ｈ
^ｐ _ｈ（Ω_ｈ ）はすべて、一般的な補間関数のベクトル
として記述することができ、未知のパラメーターのベク
トルは次のようになる：

【０１５５】

【数１７】

【０１５６】パラメーターＮ_ｐ は未知数の総数であ
り、Ｎ_Ｔ は要素Ｅにおける未知数の数である。ベクト
ルｘは変域の独立空間変数を示す。

【０１５７】境界条件は、有限次元の部分空間Ｖ_ｈ を
指定することで表現される。

【０１５８】

【数１８】

【０１５９】問題（Ｐ）の近似最小二乗法は次のように
定義することができる。

【０１６０】

【数１９】

【０１６１】この一般的枠組については、”Ｌｅａｓｔ
−Ｓｑｕａｒｅｓ Ｍｅｔｈｏｄｓｆｏｒ Ｅｌｌｉｐ
ｔｉｃ Ｓｙｓｔｅｍｓ”（Ａｚｉｚ Ａ．Ｋ．， Ｋ
ｅｌｌｏｇ Ｒ．Ｂ．， Ｓｔｅｐｈｅｎｓ Ａ．
Ｂ．， Ｍａｔｈ Ｃｏｍｐ．Ｖｏｌ．４４， Ｎｕｍ
ｂｅｒ １６９， ｐｐ．５３−７０， １９８５年）
で、楕円形について最小二乗法近似の誤差分析が検討さ
れている。また、混合タイプの方程式については”Ｌｅ
ａｓｔ−ｓｑｕａｒｅｓ ｍｅｔｈｏｄｓ ｆｏｒ ｍ
ｉｘｅｄ−ｔｙｐｅ ｅｑｕａｔｉｏｎｓ”（Ｓｅｒｍ
ｅｒ Ｐ． ａｎｄ Ｒ． Ｍａｔｈｏｎ， ＳＩＡＭ
Ｊｏｕｒｎａｌ ｏｆ Ｎｕｍｅｒｉｃａｌ Ａｎａ
ｌｙｓｉｓ， Ｖｏｌ．１８， Ｎｏ．４， ｐｐ．７
０５，７２３， １９８１年）で特に流体力学の問題に
ついて検討されている。（”Ｎｕｍｅｒｉｃａｌ Ｍｅ
ｔｈｏｄｓ ｆｏｒ Ｎｏｎｌｉｎｅａｒ Ｖａｒｉａ
ｔｉｏｎａｌ Ｐｒｏｂｌｅｍｓ， Ｓｐｒｉｎｇｅｒ
Ｓｅｒｉｅｓ ｉｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ
Ｐｈｙｓｉｃｓ”ではこれらの文献が参考文献として明
示的に織り込まれている。） Ｖ_ｋ の適切なノルム‖・‖選択は、微分演算子のタイ
プによって異なってくる。例えば、非線形の双曲線問題
で、最小二乗法解を安定化した古典的なＬ^２ノルムの代
わりにＨ^１ ノルムを選択すると、衝撃が発生する。

【０１６２】ここでは、線形演算子だけを検討し、よっ
て提示される最小二乗法はＬ^２ ノルムで定式化され
る。

【０１６３】境界条件 ここに記述されているアプローチでは、境界条件が満足
されているかどうかは、最小化する対象となる関数に対
するペナルティ条件を追加するという操作によって認識
される。このペナルティ条件手法を定式化するため、対
象となる関数（最小二乗法関数）に伴うノルムを適切に
定義しなければならない。問題（Ｐ）、および近似問題
（Ｐ_ｈ ）の最小二乗法にペナルティ式は、次のように
表現することができる：

【０１６４】

【数２０】

【０１６５】ここでｃは加重関数である。

【０１６６】問題Ｃ_ｈ が、内部残余Ｒ_Ｌ および境界
残余Ｒ_Ｂ と関連するＬ^２ ノルムとして表現される場
合、Ｌ^２ ０最小二乗法方程式は、未知のベクトルａに
ついての関数Ｉ_ｃ 最小化により構成される。ここで

【０１６７】

【数２１】

【０１６８】この最小二乗法に対応する不連続方程式
は、選点最小二乗法とも呼ばれるもので、変域内および
境界上にある一連の点配列を選び、次の関数で最小化を
行う：

【０１６９】

【数２２】

【０１７０】ここでｉ＝１，…，ｋ，ｘ_ｉ は内部の点
配列に対応し、ｉ＝ｋ＋１，…，ｍは境界の点配列に対
応する。

【０１７１】加重ｃを大きくすることによって、重要な
境界条件を強調し、境界残余を小さくすることができ
る。

【０１７２】最適なｃの選択については、Ｚｅｉｔｏｕ
ｎ ｅｔ ａｌの”Ａｎ ｉｔｅｒａｔｉｖｅ ｐｅｎ
ａｌｔｙ ｍｅｔｈｏｄ ｆｏｒ ｔｈｅ ｌｅａｓｔ
ｓｑｕａｒｅ ｓｏｌｕｔｉｏｎ ｏｆ ｂｏｕｎｄ
ａｒｙ ｖａｌｕｅ ｐｒｏｂｌｅｍｓ”（Ｎｕｍｅｒ
ｉｃａｌ Ｍｅｔｈｏｄｓ Ｐａｒｔｉａｌ Ｄｉｆｆ
ｅｒｅｎｔｉａｌ Ｅｑｕａｔｉｏｎｓ １３：ｐ．２
５７−２８１， １９９７年）で検討されている。本文
書では、この本の全内容が参考文献として明示的に織り
込まれている。

【０１７３】問題Ｐ_ｈ は、次の最小二乗法の式に還元
される：

【０１７４】

【数２３】

【０１７５】問題（Ｐ_ｈ ） 問題（Ｐ_ｈ ）は、最小化が境界Γ上でのみ定義される
という制約のある特殊な場合である。

【０１７６】以降では、線形微分方程式のみを検討す
る。この場合、ミニマックス問題から二次方程式プログ
ラムが導かれる。

【０１７７】内部残余および境界残余に試行的な関数を
挿入した後、ａが最小となる最初の必要条件は：

【０１７８】

【数２４】

【０１７９】Ｐ_ｋ （ｘ）の最近近似 ２つのメッシュＭ１とＭ２について、同じ境界値問題の
異なる解ａ_１ ，ａ_２ を考える。２つの連続解は次のよ
うに表現できる：

【０１８０】

【数２５】

【０１８１】これら積分の分析式は、例えば、”Ｉｎｔ
ｒｏｄｕｃｔｉｏｎ ｔｏ ｎｕｍｅｒｉｃａｌ ｌｉ
ｎｅｒ ａｌｇｅｂｒａ ａｎｄ ｏｐｔｉｍｉｚａｔ
ｉｏｎ”（Ｃｉａｒｌｅｔ Ｐ．Ｇ． Ｃａｍｂｒｉｄ
ｇｅ ＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ， １９８９
年）などで、有限要素法理論として記載されている。本
文書では、この本の全内容が参考文献として明示的に織
り込まれている。

【０１８２】この最後の式に於いて、難しいのは結節点
の解ａ_２ からｕ_２Ｈ（ｘ）を計算することである。

【０１８３】ｕ_２Ｈ（ｘ）の計算で最も簡単な方法は、
メッシュＭ２の補間関数としてΨ_ｉ （ｘ）を使用するこ
とである。

【０１８４】他の方法としては、点の値から予測した解
ｕ（ｘ）の局所解を使用する手法がある。

【０１８５】メッシュＭ１の点Ｍと、メッシュＭ２に属
するその最近点Ｍ１およびＭ２を考えてみる。

【０１８６】

【数２６】

【０１８７】ここで∇ｕ｜_Ｍ１は解ｕ_２Ｈ（ｘ）の勾配
ベクトル、Ｈ（ＭＭ_１ ）はベクトルＭＭ_１ に適用す
る解のヘッセ行列式である。ＭＭ_１ は、座標（ｘ１，
ｙ１，ｚ１）の点Ｍ_１ から座標（ｘ，ｙ，ｚ）の点Ｍ
へのベクトルを示す。ベクトルＭＭ_１ の要素は、参照
系（ｘ−ｘ１，ｙ−ｙ１，ｚ−ｚ１）内にある。

【０１８８】２点の近似のために、勾配ベクトル∇ｕ｜
_Ｍ１は次の式で見積られる：

【０１８９】

【数２７】

【０１９０】この式は、導関数の古典的な差分推定を３
次元で一般化したものである。この生成式の詳細は、前
述の”Ｎｕｍｅｒｉｃａｌ Ｓｏｌｕｔｉｏｎ ｏｆ
Ｐａｒｔｉａｌ ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｑｕａ
ｔｉｏｎｓ ｉｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉ
ｎｅｅｒｉｎｇ”に記載されている。

【０１９１】この概算式を使用することにより、明らか
に、Ｍ１とＭ２で粗メッシュの解の値を使用して、ｕ
_２Ｈ（ｘ）が計算される。

【０１９２】

【数２８】

【０１９３】この後者の概算によって、ＭＭ_１ の方向
において勾配のみが計算される。使用される要素のタイ
プに応じて、次のように補間を一般化することができ
る。

【０１９４】

【数２９】

【０１９５】この式は、細密メッシュの各点に使用され
る。このヘッセ行列式の見積りは、前記の”Ｄｅｌａｕ
ｎｅｙ Ｔｒｉａｎｇｕｌａｔｉｏｎ ａｎｄ Ｍｅｓ
ｈｉｎｇ−Ａｐｐｌｉｃａｔｉｏｎ ｔｏ Ｆｉｎｉｔ
ｅ Ｅｌｅｍｅｎｔｓ”１２章にある見積りを使った粗
メッシュのサイズ計算に使用することができる。

【０１９６】ここで、「メッシュ」と「グリッド」とい
う語は、同じ意味で用いられている。上記で特に明確な
記載がない範囲内で、本文書では、この本の全内容が参
考文献として明示的に織り込まれている。

【０１９７】図５は、ＣＡＤ、ＧＩＳ、３次元描写シス
テムと共に用いるさまざまなソフトウェアと、それに関
係するアナライザー／ソルバーを示したものである。

【０１９８】本発明の機能では、Ｎａｓｔｒａｎソルバ
ー／アナライザーを１００，０００結節点で使用した場
合、誤差２０％の解が得られた。同じプログラムを５
０，０００結節点で使用した場合、解の誤差は４０％と
なった。しかし本発明を用いると（すなわち、本発明の
アクセラレーターと高速化手法を用いると）、本発明を
用いない１００，０００結節点での解と同じ誤差なら、
１０，０００結節点で解が得られる。これに応じて、本
発明では計算労力（すなわち計算時間）も大幅に縮小さ
れた。本発明を使用すると、処理量は１／２０〜１／６
０の短縮が達成された。これに関して、理論的には（す
なわち本発明の数学的実証に基づいて）、１０^３ の桁
での削減が達成され得ることをここに特記する。しかし
ながら実際的には、使用されるアナライザー／ソルバー
やプラットフォームの種類、装置の仕様などにより、高
速化や計算労力の削減程度は、上記よりもやや低くな
る。

【０１９９】本発明の実現において、ここに記した方法
はコンピュータープロセッサー上でソフトウェアプログ
ラムの実行として使用するためのものである。専用のハ
ードウェアとしては、アプリケーション専用の集積回
路、プログラマブル論理アレイ、その他のハードウェア
装置などがあり、これらはここに記載された手法の実行
用に構築することが可能である。さらに、分散処理や要
素／オブジェクト分散処理、並列処理、仮想マシン処理
などのほかのソフトウェア実行形態も、ここに述べられ
ている手法実施を構築することができる。

【０２００】本発明のソフトウェア実用には、ディスク
やテープなどの磁気媒体、ＭＯディスク、光ディスク、
メモリカードなどのソリッドステート媒体、その他リー
ドオンリーメモリ（非揮発性）パッケージやランダムア
クセスメモリ、その他のリライタブルメモリなど（揮発
性）、有形の記録媒体に任意に保存することができるこ
とを特記する。電子メールの添付デジタルファイルや、
独立型情報アーカイブも、有形の記録媒体と同等の配布
媒体と見なされる。従って、本発明は、上記に挙げたよ
うな有形の記録媒体または配布媒体、および技術的に同
等であると見なされるものや後続の媒体技術も、ソフト
ウェア実用を保存するための手段として含まれるものと
見なされる。

【０２０１】これまでに挙げた例や実用例は、単に説明
目的のものであり、本発明の特徴機能を制限するものと
解釈されるものではない。本発明は典型的な実例を参照
しながら説明されているが、ここに用いられている表現
は、内容を制限するためのものではなく、解説と説明の
ためのものと理解されるべきである。この文書で説明さ
れている添付の申請書の範囲においては、変更がなされ
ることがあり、修正は、さまざまな観点において本発明
の範囲と本質からかけ離れることなく行なわれる。本発
明は本文書において特定の手段、道具、実用化手法など
を参照して説明されているが、本発明はここに発表され
ている特定例に限られるものではない。むしろ本発明
は、機能的に同等で、添付の申請書の範囲内において使
用される構造手法すべてに拡張されるものである。

【図面の簡単な説明】

【図１】図１は、本発明におけるＣＡＤ／ＧＩＳ／３次
元描写システム、メッシュジェネレーター、アナライザ
ー／ソルバー、アクセラレーターの接続関係を示すブロ
ック線図である。

【図２】図２は、本発明におけるアクセラレーターの内
容構成を示すブロック線図である。

【図３】図３は、本発明におけるアクセラレーターの操
作手順を示すフローチャートである。

【図４】図４は、図３のステップＳ３０８手順を詳細に
記したフローチャートである。

【図５】図５は、市販されているいくつかのグラフィッ
クシステム（ＣＡＤ、ＧＩＳ、３次元描写）と、それら
によって作成されたオブジェクトに関連した現象を分析
するアナライザー／ソルバーの例の表である。

【図６】図６は、ＣＡＤシステム、メッシュジェネレー
ター、アナライザー／ソルバーから成る従来型システム
である。

───────────────────────────────────────────────────── フロントページの続き (71)出願人 501119414 ５ Ｎａｈｕｍ， Ｈａｆａｔｓｅｄｉ Ｓｔｒｅｅｔ， Ｇｉｖａｔ Ｓｈａｕ ｌ， Ｊｅｒｕｓａｌｅｍ 91341， Ｉ ｓｒａｅｌ (72)発明者 デービット ガストン ゼイトン イスラエル国， エルサレム 91341， ジバット シャウル， ハファットセディ ストリート， ナフム ５，オプティモ ド ソフトウェア システムズ リミテッ ド内 Ｆターム(参考） 5B046 JA07 5B056 AA04 BB01 HH03

Claims (39)

【特許請求の範囲】
1. 【請求項１】アナライザー／ソルバーおよびメッシュジ
   ェネレーターに外部的に接続可能なアクセラレーター。
   アナライザー／ソルバーはメッシュジェネレーターが生
   成したメッシュに基づく線形行列方程式を解く。アクセ
   ラレーターは次のものから成る： メッシュサイズオプチマイザー：メッシュジェネレータ
   ーが生成した最初のメッシュを受け取り、その最初のメ
   ッシュに基づいて最適なメッシュサイズを計算し、その
   最適なメッシュサイズをメッシュジェネレーターに対し
   て出力して、この最適なメッシュサイズに従いメッシュ
   ジェネレーターが第２のメッシュを生成する。最適なメ
   ッシュサイズは最初のメッシュサイズよりも大きくな
   る。 インターポレーター：アナライザー／ソルバーが第２の
   メッシュについて計算した解を読み取り、その第２のメ
   ッシュの解を変換して最初のメッシュの解に補間する。
2. 【請求項２】請求項１におけるアクセラレーターには、
   複数の入出力データ構造を有する複数のアナライザー／
   ソルバーの中からアナライザー／ソルバーがひとつ選択
   され、さらにこのアクセラレーターには、選択したアナ
   ライザー／ソルバーに対応するデータ構造をひとつ選択
   するソルバーセレクターが含まれている。
3. 【請求項３】請求項２におけるアクセラレーターにはさ
   らに、複数のアナライザー／ソルバーと複数のデータ構
   造との間の関係を保存するモデルデータベースがあり、
   ここでソルバーセレクターが選択されたアナライザー／
   ソルバーに対応するデータ構造をモデルデータベースか
   ら読み取る。
4. 【請求項４】請求項１におけるアクセラレーターでは、
   メッシュジェネレーターが対象オブジェクトの３次元メ
   ッシュデータをつくり、アナライザー／ソルバーは３次
   元メッシュデータの解を出力する。アクセラレーターは
   さらに、アナライザー／ソルバーから３次元メッシュデ
   ータの解を受け取り、これをそのオブジェクトの２次元
   表面についての解に変換するデコンポーザーも有する。
5. 【請求項５】請求項１におけるアクセラレーターには、
   補間解の誤差が規定値よりも少ないかどうかを評価する
   誤差エスチメーターが含まれている。
6. 【請求項６】請求項５におけるアクセラレーターでは、
   補間解のヘッセ行列式に基づいて誤差の見積りが行われ
   る。
7. 【請求項７】請求項１におけるアクセラレーターでは、
   粗メッシュサイズオプチマイザーが、仮定的予測に基づ
   いて最適なメッシュサイズを算出する。
8. 【請求項８】請求項７におけるアクセラレーターでは、
   上記の粗メッシュサイズオプチマイザーが、最小二乗法
   に基づいて最適なメッシュサイズの調整を行なう。
9. 【請求項９】請求項８におけるアクセラレーターでは、
   粗メッシュサイズオプチマイザーが次の式により最適メ
   ッシュサイズを調整する。 【数３０】 ここにおいてＩ_ｃ （ａ）はオブジェクトの少なくとも
   一部分について定義された最小二乗法関数、ｕ
   _１ｈ（ｘ）は、不連続解ａ１（Ｎ次ベクトル）を補間し
   て得られた細密メッシュの連続解で、Ｎ＊Ｎ線形方程式
   の解である。ｕ_２Ｈ（ｘ）は、粗メッシュについての連
   続解で、勾配予測により不連続解ａ２（Ｍ次ベクトル）
   を補間して得られたものであり、Ｍ＊Ｍ線形行列方程式
   の解である。ｃは第２回目に加わる加重関数であり、Ｌ
   およびＢはアナライザー／ソルバーの種類によって決ま
   る。あるいはユーザーが定義する演算子である。Ωは変
   域、Γは分析するオブジェクトの境界である。
10. 【請求項１０】メッシュ生成に由来する線形行列方程式
    を解くアナライザー／ソルバーの計算を加速する手法。
    これは次のものから構成されている：Ｎ＊Ｎ線形連立方
    程式を形成する細密メッシュの生成、 適応最適化基準の選択、 仮定的予測に基づく最適メッシュサイズの選定、 Ｎ＊Ｎ線形連立方程式に対応するＭ＊Ｍ連立方程式の最
    適メッシュサイズで粗メッシュを生成、 Ｍ＊Ｍ線形連立方程式を解き、最初の解を算出、 Ｍ＊Ｍ線形連立方程式の最初の解の補間により、Ｎ＊Ｎ
    線形連立方程式の第２の解を算出。
11. 【請求項１１】請求項１０における手法には、さらに次
    の内容が含まれる：複数のアナライザー／ソルバーの中
    からひとつを選択し、その選択されアナライザー／ソル
    バーのデータ構造を決定する。
12. 【請求項１２】請求項１０における手法には、さらに次
    の内容が含まれる：３次元オブジェクトの最初の解をグ
    ループに分けて、各グループがそれぞれの２次元表面に
    対応するようにする。
13. 【請求項１３】請求項１０における手法には、さらに次
    の内容が含まれる：ヘッセ行列式に基づいて第２の解の
    誤差を評価する、 その誤差が規定の値以下であるかどうかを判定する、 その誤差が規定の値以下でなかった場合は、その粗メッ
    シュのメッシュサイズよりも小さなメッシュサイズにし
    て新たなメッシュを生成し、新たなメッシュで第２の解
    を算出する。
14. 【請求項１４】請求項１０における手法には、さらに次
    の内容が含まれる：第２の解を、グラフィカルユーザー
    インターフェースで表示できるデータに変換する。
15. 【請求項１５】請求項８における手法では、適応最適化
    基準が次の式で定義される。 【数３１】 ここにおいてＩ_ｃ （ａ）はオブジェクトの少なくとも
    一部分について定義された最小二乗法関数、ｕ
    _１ｈ（ｘ）は、不連続解ａ１（Ｎ次ベクトル）を補間し
    て得られた細密メッシュの連続解で、Ｎ＊Ｎ線形方程式
    の解である。ｕ_２Ｈ（ｘ）は、粗メッシュについての連
    続解で、勾配予測により不連続解ａ２（Ｍ次ベクトル）
    を補間して得られたものであり、Ｍ＊Ｍ線形行列方程式
    の解である。ｃは第２回目に加わる加重関数であり、Ｌ
    およびＢはアナライザー／ソルバーの種類によって決ま
    る、あるいはユーザーが定義する演算子である。Ωは変
    域、Γは分析するオブジェクトの境界である。
16. 【請求項１６】前述のアナライザー／ソルバーの外部の
    コンピューターライブラリを使用したメッシュ計算に由
    来する、数値アナライザー／ソルバーによる線形行列方
    程式の解算出を高速化するシステム。
17. 【請求項１７】請求項１６におけるシステムでは、２レ
    ベルのメッシュ計算において適応グリッド技法が利用さ
    れる。
18. 【請求項１８】請求項１６におけるシステムでは、細密
    メッシュから粗メッシュを生成し、その粗メッシュの方
    程式を解く。
19. 【請求項１９】請求項１８におけるシステムでは、細密
    メッシュと粗メッシュとの比は１０の桁となる。
20. 【請求項２０】請求項１８におけるシステムでは、粗メ
    ッシュと細密メッシュの間の補間誤差は、見積り手法に
    よって制御される。
21. 【請求項２１】請求項２０におけるシステムでは、この
    見積り手法は最小二乗法である。
22. 【請求項２２】請求項１６におけるシステムでは、前述
    のコンピューターライブラリがオブジェクトの幾何学的
    データを入力として利用し、最適なメッシュを生成し、
    誤差制御を行ない、その最適なメッシュについての解を
    算出する。
23. 【請求項２３】請求項１６におけるシステムでは、前述
    のコンピューターライブラリがアナライザー／ソルバー
    の入力データに基づき、アナライザー／ソルバーの内部
    コードを変更することなく処理を行なう。
24. 【請求項２４】請求項１６におけるシステムでは、計算
    時間の高速化は、理論上、１０^３ の桁で可能である。
25. 【請求項２５】請求項１６におけるシステムでは、前記
    のコンピューターライブラリによる誤差制御により、解
    の精度が既定値に維持され、同時に必要なデータ容量が
    低減し、計算時間が短縮される。
26. 【請求項２６】粗メッシュを、細密メッシュサイズの投
    影として生成することにより、線形行列方程式の解算出
    を高速化するシステム。このシステムは、次の式の関係
    を最小化することにより、最適なメッシュサイズを計算
    する： 【数３１】 ここにおいてＩ_ｃ （ａ）はオブジェクトの少なくとも
    一部分について定義された最小二乗法関数、ｕ
    _１ｈ（ｘ）は、不連続解ａ１（Ｎ次ベクトル）を補間し
    て得られた細密メッシュの連続解で、Ｎ＊Ｎ線形方程式
    の解である。ｕ_２Ｈ（ｘ）は、粗メッシュについての連
    続解で、勾配予測により不連続解ａ２（Ｍ次ベクトル）
    を補間して得られたものであり、Ｍ＊Ｍ線形行列方程式
    の解である。ｃは第２回目に加わる加重関数であり、Ｌ
    およびＢはアナライザー／ソルバーの種類によって決ま
    る、あるいはユーザーが定義する演算子である。Ωは変
    域、Γは分析するオブジェクトの境界である。
27. 【請求項２７】細密メッシュにより記述された線形行列
    方程式を解く手法。この手法は次の内容より構成されて
    いる：仮定的予測に基づく誤差制御を使用して粗メッシ
    ュを選択する、 粗メッシュについての方程式を解く、 その解を細密メッシュに対して補間する。
28. 【請求項２８】請求項２７における手法では、補間に最
    小二乗法が使用される。
29. 【請求項２９】請求項１におけるアクセラレーターで、
    アナライザー／ソルバーによって算出された解は第２の
    メッシュの各点に対応する不連続解であり、インターポ
    レーターは次の関係を使用して、全変域の連続解ｕ_２Ｈ
    （ｘ）を計算する： 【数３２】 ここでＭは最初のメッシュの点、Ｍ_１ は第２のメッシ
    ュの最近接点、∇ｕ_{２ Ｈ}｜_Ｍ１はｕ_２Ｈ（ｘ）の勾配ベ
    クトル、Ｈ（ＭＭ_１ ）はベクトルＭＭ_１ に適用する
    解のヘッセ行列式、ＭＭ_１ は、座標（ｘ１，ｙ１，ｚ
    １）の点Ｍ_１から座標（ｘ，ｙ，ｚ）の点Ｍへのベクト
    ルを示す。
30. 【請求項３０】請求項１におけるアクセラレーターで、
    インターポレーターはアナライザー／ソルバー計算した
    第２メッシュの解を、次の関係を用いて最初のメッシュ
    に投影する： 【数３３】 ここでｎｐは最初のメッシュにおける補間点の数、Ｍ
    _１ は第２のメッシュ上にある座標（ｘｉ，ｙｉ，ｚ
    ｉ）の点、Ｍ_{（ｉ＋１）} は第２のメッシュにある座標
    （ｘ（ｉ＋１），ｙ（ｉ＋１），ｚ（ｉ＋１））の点で
    ある。
31. 【請求項３１】請求項３０におけるアクセラレーター
    で、インターポレーターは第２メッシュの解を、次の関
    係を用いて最初のメッシュに投影する： 【数３４】 ここでｘは特殊点（最初のメッシュの点に対応する
    点）、Ｍ_ｋ は、点ｘを含む第２メッシュ上における要
    素Ｅの少なくとも一部を構成する点群、Ｎｅはユーザー
    が固定した補間点の総数、ｕ_２Ｈ（ｘ）は第２メッシュ
    の点の解に基づいて計算した変域全体の連続解である。
32. 【請求項３２】請求項１０における手法で、最初の解は
    第２のメッシュの各点に対応する不連続解であり、第２
    の解の計算には、次の関係を使用して、全変域の連続解
    ｕ_２Ｈ（ｘ）を計算することが含まれる： 【数３５】 ここでＭは最初のメッシュの点、Ｍ_１ は第２のメッシ
    ュの最近接点、∇ｕ_{２ Ｈ}｜_Ｍ１は解ｕ_２Ｈ（ｘ）の勾配
    ベクトル、Ｈ（ＭＭ_１ ）はベクトルＭＭ_１に適用する
    解のヘッセ行列式、ＭＭ_１ は、座標（ｘ１，ｙ１，ｚ
    １）の点Ｍ_１ から座標（ｘ，ｙ，ｚ）の点Ｍへのベクト
    ルを示す。
33. 【請求項３３】請求項１０における手法で、第２の解の
    計算には、次の関係を使用して、第２のメッシュについ
    ての最初の解を第１のメッシュに投影することが含まれ
    る： 【数３６】 ここでｎｐは最初のメッシュにおける補間点の数、Ｍ
    _１ は第２のメッシュ上にある座標（ｘｉ，ｙｉ，ｚ
    ｉ）の点、Ｍ_{（ｉ＋１）} は第２のメッシュにある座標
    （ｘ（ｉ＋１），ｙ（ｉ＋１），ｚ（ｉ＋１））の点で
    ある。
34. 【請求項３４】請求項３３における手法で、第２の解の
    計算には、次の関係を使用して、第２のメッシュについ
    ての最初の解を第１のメッシュに投影することが含まれ
    る： 【数３７】 ここでｘは特殊点（最初のメッシュの点に対応する
    点）、Ｍ_ｋ は点ｘを含む第２メッシュ上における要素
    Ｅの少なくとも一部を構成する点群、Ｎｅはユーザーが
    固定した補間点の総数、ｕ_２Ｈ（ｘ）は第２メッシュの
    点の解に基づいて計算した変域全体の連続解である。
35. 【請求項３５】プログラム保存装置。このプログラム保
    存装置は、コンピューターが読み込むことができる装置
    で、線形行列方程式の高速化解法を実行するため、コン
    ピューターが実行できる手順プログラムを物理的に保管
    するものである。この手法は次の内容から成る：メッシ
    ュジェネレーターが生成した細密メッシュを読み込ん
    で、Ｎ＊Ｎ線形連立方程式とする、 この細密メッシュに基づいて仮定的予測により最適なメ
    ッシュサイズを算出する、 最適メッシュサイズに基づき粗メッシュを生成して、Ｎ
    ＊Ｎ線形連立方程式に対応するＭ＊Ｍ線形連立方程式と
    する、 アナライザー／ソルバーに対してこのＭ＊Ｍ線形連立方
    程式を解かせ、最初の解を得る、 このＭ＊Ｍ線形連立方程式の最初の解を補間することに
    よりＮ＊Ｎ線形連立方程式の第２の解を算出する。
36. 【請求項３６】請求項３５におけるプログラム保存装置
    で、最初の解は第２のメッシュの各点に対応する不連続
    解であり、第２の解の計算には、次の関係を使用して、
    全変域の連続解ｕ_２Ｈ（ｘ）を計算することが含まれ
    る。 【数３８】 ここでＭは最初のメッシュの点、Ｍ_１ は第２のメッシ
    ュの最近接点、∇ｕ_{２ Ｈ}｜_Ｍ１は解ｕ_２Ｈ（ｘ）の勾配
    ベクトル、Ｈ（ＭＭ_１ ）はベクトルＭＭ_１に適用する
    解のヘッセ行列式、ＭＭ_１ は、座標（ｘ１，ｙ１，ｚ
    １）の点Ｍ_１ から座標（ｘ，ｙ，ｚ）の点Ｍへのベクト
    ルを示す。
37. 【請求項３７】請求項３５におけるプログラム保存装置
    で、第２の解の計算には、次の関係を使用して、第２の
    メッシュについての最初の解を第１のメッシュに投影す
    ることが含まれる： 【数３９】 ここでｎｐは最初のメッシュにおける補間点の数、Ｍ
    _１ は第２のメッシュ上にある座標（ｘｉ，ｙｉ，ｚ
    ｉ）の点、Ｍ_{（ｉ＋１）} は第２のメッシュにある座標
    （ｘ（ｉ＋１），ｙ（ｉ＋１），ｚ（ｉ＋１））の点で
    ある。
38. 【請求項３８】請求項３７におけるプログラム保存装置
    で、第２の解の計算には、次の関係を使用して、第２の
    メッシュについての最初の解を第１のメッシュに投影す
    ることが含まれる： 【数４０】 ここでｘは特殊点（最初のメッシュの点に対応する
    点）、Ｍ_ｋ は、点ｘを含む第２メッシュ上における要
    素Ｅの少なくとも一部を構成する点群、Ｎｅはユーザー
    が固定した補間点の総数、ｕ_２Ｈ（ｘ）は第２メッシュ
    の点の解に基づいて計算した変域全体の連続解である。
39. 【請求項３９】請求項３５におけるプログラム保存装置
    にはさらに、複数のアナライザー／ソルバーと複数のデ
    ータ構造との関係を保存するモデルデータベースがあ
    る。この手法はさらに、次の内容から成る：複数のアナ
    ライザー／ソルバーのうちひとつを選択する入力を受け
    取り、 その選択したアナライザー／ソルバーに対応するデータ
    構造を読み込む。