(57)【要約】【課題】ＣＡＥ解析を用いて、物理領域の物理挙動の数値シミュレーションをコンピュータで実施する方法を提供する。【解決手段】Ｎ×Ｎ行列は、物理領域を表す演算モデルから生成され、物理領域のＮの自由度に関連するＮ個の未知の物理量についてのＮ個の連立一次方程式の係数を有し、複数の辺によって接続されるＮ個の頂点を含む無向グラフによって表される。Ｎ個の頂点を、分離グループと、第１および第２の相互独立グループとに分割する最適な分割法を、Ｎ個の頂点から選択された複数の源点の距離ベクトルを演算し、それぞれの別のペアの源点に対して、それぞれの距離ベクトルの差異を用いて隣接疎マトリックスが５重対角行列である疎なグラフを検出し、疎なグラフを用いて試行分割法を初期決定し、分離グループが最小になるまで分離グループに含まれる頂点を取り出し、相互独立グループの一方に併合することにより、分離グループを反復的に改善して、決定する。【選択図】図２Ａ
2014225257.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ支援エンジニアリング（ＣＡＥ）解析を用いて、物理領域の物理的挙動の数値シミュレーションをコンピュータで実施する方法であって、
分散メモリマルチプロセッサコンピュータシステムにおいて物理領域を表す演算モデルを受け取るステップであって、前記演算モデルが非構造格子の複数の要素によって接続される複数のノードを有すると共に、前記ノードに関しＮの自由度（Ｎは正の整数）を有しているステップと、
前記分散メモリマルチプロセッサコンピュータシステムにインストールされたＣＡＥアプリケーションモジュールを用いて、前記演算モデルから前記物理領域の物性を表しているＮ×Ｎマトリックスを生成するステップであって、前記Ｎ×Ｎマトリックスが前記物理領域のＮ個の未知の物理量についてのＮ個の連立一次方程式の係数を有しており、それぞれの前記未知の物理量が前記Ｎの自由度のうちの１つに関連しているステップと、
前記Ｎ×Ｎマトリックスを表すために、複数の辺によって接続されるＮ個の頂点を含んでいる無向グラフを用いるステップであって、前記Ｎ個の頂点がそれぞれの前記Ｎの自由度に対応しており、前記辺が前記Ｎ×Ｎマトリックスにおける０でない項をそれぞれ表しているステップと、
前記Ｎ個の頂点から選択された複数の源点のそれぞれの距離ベクトルを演算するステップと、
それぞれの別のペアの前記源点に対して、前記Ｎ個の頂点を、分離グループと、第１および第２の相互独立グループとに分割する試行分割法を決定するステップであって、当該ステップが、
ａ）隣接疎マトリックスが５重対角行列である疎なグラフを検出するよう、前記別のペアの対応する前記距離ベクトルの差異であるハーフレベルセットベクトルを用いるステップと、
ｂ）前記疎なグラフを用いて、前記分離グループと、前記第１および第２の相互独立グループとを初期決定するステップと、
ｃ）前記分離グループが最小になるまで、前記分離グループに含まれている前記頂点を取り出し、いずれの前記辺によっても接続されていない前記第１および第２の相互独立グループの一方に併合することにより、前記分離グループを反復的に改善するステップと、
により実行されるステップと、
前記Ｎ個の連立一次方程式を解くための全体的演算リソースを低減するように構成されるユーザ定義基準に基づいて最適な分割法を決定するよう、全ての前記試行分割法を比較するステップであって、前記全体的演算リソースは、前記分散メモリマルチプロセッサコンピュータシステムのプロセッサ間のプロセッサ間通信を含んでいるステップと、
前記最適な分割法に従って前記分散メモリマルチプロセッサコンピュータシステムの対応する記憶システムに記憶される前記Ｎ×Ｎマトリックスを用いて前記Ｎ個の前記未知の物理量を解くことにより、前記物理領域の数値シミュレーションされた物理的挙動を取得するステップと、
を備える方法。
【請求項２】
請求項１に記載の方法であって、
前記物理領域の前記物理的挙動は製品の構造的挙動であり、
前記演算モデルは、有限要素を含む要素を具備する有限要素解析モデルを有する、
方法。
【請求項３】
請求項２に記載の方法であって、
前記物理領域の前記物性は剛性であり、
前記未知の物理量は前記有限要素解析モデルの前記ノードの変位である、
方法。
【請求項４】
請求項１に記載の方法であって、
前記Ｎ個の頂点からの１つの前記源点のグループの選択は、任意にランダムに行われる、
方法。
【請求項５】
請求項１に記載の方法であって、
前記距離ベクトルは、前記無向グラフにおいて前記別のペアの源点間の最小経路長を表す、
方法。
【請求項６】
請求項１に記載の方法であって、
前記ユーザ定義基準は、前記第１および第２の相互独立グループの不均衡および差異に基づき、
前記不均衡および前記差異は、
不均衡＝最大値（|B|，|W|）／最小値（|B|，|W|）
差異＝絶対値（|B|−|W|）／（|B|＋|W|＋|S|）
で求められ、
|B|は前記第１の相互独立グループにおける前記頂点の数であり、
|W|は前記第２の相互独立グループにおける前記頂点の数であり、
|S|は前記分離グループにおける前記頂点の数である、
方法。
【請求項７】
請求項６に記載の方法であって、
前記ユーザ定義基準は、特定の分割法の演算コスト指標を評価するための、ユーザが付与する第１および第２のパラメータを更に含んでおり、
前記不均衡が前記第１のパラメータ未満である場合、前記演算コスト指標は|S|×（1＋前記差異×前記第２パラメータ）であり、
前記不均衡が前記第１のパラメータ以上である場合、前記演算コスト指標は無限大である、
方法。
【請求項８】
コンピュータ支援エンジニアリング（ＣＡＥ）解析を用いて、物理領域の物理的挙動の数値シミュレーションするシステムであって、
第１および第２の記憶システムをそれぞれ有し、それぞれと局所的に接続される第１および第２のプロセッサであって、前記第１のプロセッサおよび前記第１の記憶システムが少なくとも１のプロセッサ間通信リンクを介して、前記第２のプロセッサおよび前記第２の記憶システムに機能可能に接続されている第１および第２のプロセッサと、
コンピュータ可読コードを有し、前記第１の記憶システムおよび／または前記第２の記憶システムに記憶されるＣＡＥアプリケーションモジュールと、
を備えるシステムであり、
前記ＣＡＥアプリケーションモジュールは、対応するプロセッサにおいて実行された時、方法に基づいてオペレーションを実行し、
前記方法は、
前記物理領域を表す演算モデルを受け取るステップであって、前記演算モデルが非構造格子の複数の要素によって接続される複数のノードを備えていると共に、前記ノードに関連するＮの自由度（Ｎは正の整数）を有しているステップと、
前記演算モデルから前記物理領域の物性を表しているＮ×Ｎマトリックスを生成するステップであって、前記Ｎ×Ｎマトリックスが前記物理領域のＮ個の未知の物理量についてのＮ個の連立一次方程式の係数を有しており、それぞれの前記未知の物理量が前記Ｎの自由度のうちの１つに関連しているステップと、
前記Ｎ×Ｎマトリックスを表すために、複数の辺によって接続されるＮ個の頂点を含んでいる無向グラフを用いるステップであって、前記Ｎ個の頂点がそれぞれの前記Ｎの自由度に対応しており、前記辺が前記Ｎ×Ｎマトリックスにおける０でない項をそれぞれ表しているステップと、
前記Ｎ個の頂点から選択された複数の源点のそれぞれの距離ベクトルを演算するステップと、
それぞれの別のペアの前記源点に対して、前記Ｎ個の頂点を、分離グループと、第１および第２の相互独立グループとに分割する試行分割法を決定するステップであって、当該ステップが、
ａ）隣接疎マトリックスが５重対角行列である疎なグラフを検出するよう、前記別のペアの対応する前記距離ベクトルの差異であるハーフレベルセットベクトルを用いるステップと、
ｂ）前記疎なグラフを用いて、前記分離グループと、前記第１および第２の相互独立グループとを初期決定するステップと、
ｃ）前記分離グループが最小になるまで、前記分離グループに含まれている前記頂点を取り出し、いずれの前記辺によっても接続されていない前記第１および第２の相互独立グループの一方に併合することにより、前記分離グループを反復的に改善するステップと、
により実行されるステップと、
前記Ｎ個の連立一次方程式を解くための全体的演算リソースを低減するように構成されるユーザ定義基準に基づいて最適な分割法を決定するよう、全ての前記試行分割法を比較するステップであって、前記全体的演算リソースは、前記第１および第２のプロセッサ間のプロセッサ間通信を含んでいるステップと、
前記最適な分割法に従って前記第１および前記第２の記憶システムに記憶される前記Ｎ×Ｎマトリックスを用いて前記Ｎ個の前記未知の物理量を解くことにより、前記物理領域の数値シミュレーションされた物理的挙動を取得するステップと、
を含んでいる、
システム。
【請求項９】
請求項８に記載のシステムであって、
前記物理領域の前記物理的挙動は製品の構造的挙動であり、
前記演算モデルは、有限要素を含む要素を具備する有限要素解析モデルを有する、
システム。
【請求項１０】
請求項９に記載のシステムであって、
前記物理領域の前記物性は剛性であり、
前記未知の物理量は前記有限要素解析モデルの前記ノードの変位である、
システム。
【請求項１１】
請求項８に記載のシステムであって、
前記Ｎ個の頂点からの１つの前記源点のグループの選択は、任意にランダムに実行される、
システム。
【請求項１２】
請求項８に記載のシステムであって、
前記距離ベクトルは、前記無向グラフにおいて前記別のペアの源点間の最小経路長を表す、
システム。
【請求項１３】
請求項８に記載のシステムであって、
前記ユーザ定義基準は、前記第１および第２の相互独立グループの不均衡および差異に基づき、
前記不均衡および前記差異は、
不均衡＝最大値（|B|，|W|）／最小値（|B|，|W|）
差異＝絶対値（|B|−|W|）／（|B|＋|W|＋|S|）
で求められ、
|B|は前記第１の相互独立グループにおける前記頂点の数であり、
|W|は前記第２の相互独立グループにおける前記頂点の数であり、
|S|は前記分離グループにおける前記頂点の数である、
システム。
【請求項１４】
請求項１３に記載のシステムであって、
前記ユーザ定義基準は、特定の分割法の演算コスト指標を評価するための、ユーザが付与する第１および第２のパラメータを更に含んでおり、
前記不均衡が第１のパラメータ未満である場合、前記演算コスト指標は|S|×（１＋前記差異×前記第２パラメータ）であり、
前記不均衡が第１のパラメータ以上である場合、前記演算コスト指標は無限大である、
システム。
【請求項１５】
所定の方法に基づき、コンピュータ支援エンジニアリング（ＣＡＥ）解析を用いて、物理領域の物理的挙動を数値シミュレーションするための、コンピュータが実行可能な命令を有する非一時的なコンピュータ可読記憶媒体であって、
前記方法が、
分散メモリマルチプロセッサコンピュータシステムにおいて物理領域を表す演算モデルを受け取るステップであって、前記演算モデルが非構造格子の複数の要素によって接続される複数のノードを有すると共に、前記ノードに関しＮの自由度（Ｎは正の整数）を有しているステップと、
前記分散メモリマルチプロセッサコンピュータシステムにインストールされたＣＡＥアプリケーションモジュールを用いて、前記演算モデルから前記物理領域の物性を表しているＮ×Ｎマトリックスを生成するステップであって、前記Ｎ×Ｎマトリックスが前記物理領域のＮ個の未知の物理量についてのＮ個の連立一次方程式の係数を有しており、それぞれの前記未知の物理量が前記Ｎの自由度のうちの１つに関連しているステップと、
前記Ｎ×Ｎマトリックスを表すために、複数の辺によって接続されるＮ個の頂点を含んでいる無向グラフを用いるステップであって、前記Ｎ個の頂点がそれぞれの前記Ｎの自由度に対応しており、前記辺が前記Ｎ×Ｎマトリックスにおける０でない項をそれぞれ表しているステップと、
前記Ｎ個の頂点から選択された複数の源点のそれぞれの距離ベクトルを演算するステップと、
それぞれの別のペアの前記源点に対して、前記Ｎ個の頂点を、分離グループと、第１および第２の相互独立グループとに分割する試行分割法を決定するステップであって、当該ステップが、
ａ）隣接疎マトリックスが５重対角行列である疎なグラフを検出するよう、前記別のペアの対応する前記距離ベクトルの差異であるハーフレベルセットベクトルを用いるステップと、
ｂ）前記疎なグラフを用いて、前記分離グループと、前記第１および第２の相互独立グループとを初期決定するステップと、
ｃ）前記分離グループが最小になるまで、前記分離グループに含まれている前記頂点を取り出し、いずれの前記辺によっても接続されていない前記第１および第２の相互独立グループの一方に併合することにより、前記分離グループを反復的に改善するステップと、
により実行されるステップと、
前記Ｎ個の連立一次方程式を解くための全体的演算リソースを低減するように構成されるユーザ定義基準に基づいて最適な分割法を決定するよう、全ての前記試行分割法を比較するステップであって、前記全体的演算リソースは、前記分散メモリマルチプロセッサコンピュータシステムのプロセッサ間のプロセッサ間通信を含んでいるステップと、
前記最適な分割法に従って前記分散メモリマルチプロセッサコンピュータシステムの対応する記憶システムに記憶される前記Ｎ×Ｎマトリックスを用いて前記Ｎ個の前記未知の物理量を解くことにより、前記物理領域の数値シミュレーションされた物理的挙動を取得するステップと、
を含んでいる、
非一時的なコンピュータ可読記憶媒体。
【請求項１６】
請求項１５に記載の非一時的なコンピュータ可読記憶媒体であって、
前記物理領域の前記物理的挙動は製品の構造的挙動であり、
前記演算モデルは、有限要素を含む要素を具備する有限要素解析モデルを有する、
非一時的なコンピュータ可読記憶媒体。
【請求項１７】
請求項１６に記載の非一時的なコンピュータ可読記憶媒体であって、
前記物理領域の前記物性は剛性であり、
前記未知の物理量は前記有限要素解析モデルの前記ノードの変位である、
非一時的なコンピュータ可読記憶媒体。
【請求項１８】
請求項１５に記載の非一時的なコンピュータ可読記憶媒体であって、
前記Ｎ個の頂点からの１つの前記源点のグループの選択は、任意にランダムに実行される、
非一時的なコンピュータ可読記憶媒体。
【請求項１９】
請求項１５に記載の非一時的なコンピュータ可読記憶媒体であって、
前記ユーザ定義基準は、前記第１および第２の相互独立グループの不均衡および差異に基づき、
前記不均衡および前記差異は、
不均衡＝最大値（|B|，|W|）／最小値（|B|，|W|）
差異＝絶対値（|B|−|W|）／（|B|＋|W|＋|S|）
で求められ、
|B|は前記第１の相互独立グループにおける前記頂点の数であり、
|W|は前記第２の相互独立グループにおける前記頂点の数であり、
|S|は前記分離グループにおける前記頂点の数である、
非一時的なコンピュータ可読記憶媒体。
【請求項２０】
請求項１９に記載の非一時的なコンピュータ可読記憶媒体であって、
前記ユーザ定義基準は、特定の分割法の演算コスト指標を評価するための、ユーザが付与する第１および第２のパラメータを更に含んでおり、
前記不均衡が前記第１のパラメータ未満である場合、前記演算コスト指標は|S|×（１＋前記差異×前記第２パラメータ）であり、
前記不均衡が前記第１のパラメータ以上である場合、前記演算コスト指標は無限大である、
非一時的なコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、コンピュータ支援エンジニアリング解析（ＣＡＥ）において用いられる方法、システムおよびソフトウェア製品に関する。本発明は、特に、双方向レベルセット(bi-directional level sets)を用いて、分散メモリマルチプロセッサコンピュータシステムにおいて物理領域（例えば自動車、飛行機および／またはそれらの部品などの製品）のＣＡＥ解析（例えば陰解法有限要素解析（ＦＥＡ）、境界要素解析など）において用いられるマトリックスを表す無向グラフ(undirected graph)を分割する方法およびシステムに関する。
【背景技術】
【０００２】
有限要素解析（ＦＥＡ）は、三次元の非線形構造の設計および解析など、複雑系に関する工学問題をモデル化して解くために産業界において広く用いられる、一般的なＣＡＥの１つである。ＦＥＡの名前は、着目されている対象のジオメトリを特定する方法に由来する。現代のデジタルコンピュータの登場により、ＦＥＡは、ＦＥＡのソフトウェアとして実装されている。基本的に、ＦＥＡのソフトウェアには、幾何学的な記述のモデルと、モデル内の各ポイントでの関連する材料特性と、が提供されている。このモデルにおいて、解析される系のジオメトリは、要素と呼ばれる、種々のサイズのソリッド、シェル、およびビームによって表現される。要素の角（コーナー）は、ノードと呼ばれる。各ノードは、三次元の空間においては６自由度を有する。モデルは、材料特性と関連づけられた材料名が割り当てられた、有限個の要素で構成される。モデルは、このように、解析対象によって占められた物理空間を、そのすぐ隣接した周囲と共に表現する。そして、ＦＥＡのソフトウェアは、各材料タイプの特性（例えば応力−歪み関係式、ヤング率、ポアソン比、熱伝導性）が作表されたテーブルを参照する。さらに、対象の境界での条件（つまり荷重、物理的な制約など）が指定される。このように、対象とその周囲のモデルが、生成される。
【０００３】
ＦＥＡソフトウェアには、陽解法と陰解法との二つのタイプがある。本発明は、１の方程式が各自由度を表す連立一次方程式の系を解くことを必要とする、陰解法ＦＥＡソフトウェアに関する。例えば、静的解析には、Ｎ個の未知の変位を伴うＮ×Ｎ剛性マトリックスと、連立一次方程式の右辺のＮ個の節点力および／または節点モーメントと、により表される、Ｎ個の連立一次方程式を解くことが含まれる。Ｎは正の整数である。有限要素ソフトウェアおよびコンピュータハードウェア技術の改良に伴い、今日のＦＥＡモデルの多くは、膨大な数の未知数（例えばしばしば数百万のオーダー）を含んでいる。ＦＥＡモデルのＮ×Ｎマトリックスは疎行列である（つまり、成分の多くがゼロである）。シリアル演算およびパラレル演算の両方に対し、このようなマトリックスを解く性能を改善するために、多くの手法が用いられている。分散メモリマルチプロセッサンピュータシステムにおいて、スパースマトリックス（疎行列）ソルバー性能を改善する鍵は、プロセッサ間通信を低減可能な分割法を用いてマトリックスを分割することである。しかしながら、大きなスパースマトリックス（疎行列）の分割は容易なタスクではない。従来技術のアプローチは、一般的に、非特許文献１（"Nested Dissection of a Regular Finite Element Mesh"(Alan George， SIAM Journal on Numerical Analysis， Vol. 10， No. 2、1973年4月）)に基づく。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術のアプローチは分散メモリコンピュータシステムにおいて十分には機能しない。そのため、分散メモリマルチプロセッサコンピュータシステムにおいて物理領域のＣＡＥ解析において用いられるマトリックスを表すグラフの分割を改善する方法およびシステムが望まれる。
【課題を解決するための手段】
【０００５】
この章は、本発明のいくつかの面を要約することを目的とし、いくつかの好適な実施形態を簡潔に紹介するものである。この章の目的が曖昧になることを避けるため、簡略化あるいは省略が行われている場合がある。このような簡略化あるいは省略は、本発明の範囲を制限するものではない。
【０００６】
分散メモリマルチプロセッサコンピュータシステムにおいてＣＡＥ解析を用いて、物理領域の物理的挙動を数値的にシミュレートする方法およびシステムを提供する。本発明の一実施形態では、物理領域(例えば自動車、飛行機などの製品)を表す演算モデル(例えば非構造格子有限要素解析モデル(unstructured finite element analysis model))が定義され、コンピュータシステムに提供される。演算モデルから、物理領域の物性（例えば剛性）を表しているＮ×Ｎマトリックスが生成される。Ｎ×Ｎマトリックスは物理領域のＮ個の未知の物理量（例えば、それぞれの自由度のＮ個のノードの変位、Ｎは正の整数）についてのＮ個の連立一次方程式の係数を有する。そして、マトリックスは、複数の辺（エッジ）によって接続されるＮ個の頂点（バーテックス(vertex)）を有する無向グラフによって表される。各頂点は自由度に対応する。また、各エッジはマトリックスにおけるゼロでない項を表す。
【０００７】
分散メモリマルチプロセッサコンピュータシステムにおいてＣＡＥ解析を効率的に実行するために、Ｎ個の頂点を分離グループ(separator group)と、第１および第２の相互独立グループ(mutually independent groups)とに分割する最適な分割法が決定される。第１の独立グループにおける頂点は、第２の独立グループにおける頂点にいずれの辺によっても接続されていない。本発明の一態様では、１の源点（ソースバーテックス(source vertex)）のグループが、Ｎ個の頂点から選択される（例えば、任意にランダムに選択される）。そして、源点のそれぞれの距離ベクトルが演算される。距離ベクトルは、グラフにおける２つの頂点間の最小経路長である。それぞれ別のペアの源点に対して、隣接疎マトリックス（adjacency coarse matrix）が５重対角（ペンタダイアゴナル(pentadiagonal)）である疎なグラフ(coarse graph)を検出するよう、ハーフレベルセットベクトル(half-level set vector)（つまり、それぞれの距離ベクトルの差異）が用いられる。試行分割法がその疎なグラフを用いて初期決定される。そして、分離グループが最小になるまで、分離グループに含まれている１以上の頂点を取り出し、それらを第１および第２の相互独立グループの一方に併合することにより、分離グループが改善される。最後に、分散メモリマルチプロセッサコンピュータシステムにおいてＮ個の連立一次方程式を解く全体的演算リソース（例えばプロセッサ間通信）を低減するように構成されるユーザ定義基準に従って、全ての試行分割法を比較することにより、最適な分割法が決定される。この分割が、結果として得られる分割のサイズが、連立一次方程式系を解くために用いられる演算環境（例えばプロセッサの数、各プロセッサのローカルメモリのサイズなど）に対して適切となるまで、繰り返し適用される。最適な分割法に従って記憶されたＮ×Ｎマトリックスを用いて、コンピュータシステムがＣＡＥ解析においてＮ×Ｎの連立一次方程式を解くことにより、シミュレートされた物理的挙動（例えば構造挙動）が得られる。
【０００８】
本発明の目的、特徴および利点は、添付した図面を参照し、以下の本発明の実施の形態の詳細な説明を考察することによって明らかになるであろう。
【図面の簡単な説明】
【０００９】
本発明のこれらおよび他の、特徴、態様および利点は、以下の説明、添付の特許請求の範囲および添付した図面によって、より一層理解されるであろう。図面は次の通りである。
【図１Ａ】本発明の一実施形態を実現可能である例示的なコンピュータシステムの主な構成を示す機能ブロック図である。
【図１Ｂ】例示的な分散メモリマルチプロセッサコンピュータシステムを示すブロック図である。
【図２Ａ】図２Ａは、図２Ｂと共に、本発明の一実施形態に係る、物理領域のＣＡＥ解析において用いられるマトリックスを表す無向グラフを分割するために双方向レベルセットを用いる例示的なプロセスをフローチャートである。
【図２Ｂ】図２Ｂは、図２Ａと共に、本発明の一実施形態に係る、物理領域のＣＡＥ解析において用いられるマトリックスを表す無向グラフを分割するために双方向レベルセットを用いる例示的なプロセスをフローチャートである。
【図３】例示的な物理領域のＦＥＡモデルを示す図である。
【図４】種々の例示的な有限要素を示す図である。
【図５Ａ】例示的な有限要素の剛性マトリックスを示す図である。
【図５Ｂ】本発明の一実施形態に係る物理領域の例示的な物性を表す、簡易化されたマトリックスを示す図である。
【図６Ａ】図５Ａに示した要素剛性マトリックスを表す例示的なグラフを示す図である。
【図６Ｂ】本発明の一実施形態に係る例示的な無向グラフを示す図である。
【発明を実施するための形態】
【００１０】
以下の説明においては、本発明の完全な理解を提供するために、多数の具体的な詳細が記述される。しかしながら、本発明をこれらの具体的な詳細によらなくとも実現できることは、当業者にとって明らかである。ここでの説明および表現は、当該技術で経験のある者すなわち当業者が彼らの仕事を他の当業者に最も効果的に伝えるために用いる通常の手段である。他の事例で、よく知られている、方法、手順、および構成は、本発明の態様が不必要に不明瞭となることを回避するために、詳細には説明しない。
【００１１】
ここで言及する「一実施形態」あるいは「ある実施形態」は、その実施形態に関して説明される特定の特徴、構造あるいは特性を、本発明の少なくとも１つの実施形態に含めることができるということを意味する。本明細書において記載される「一実施形態において」という語は、全てが同一の実施形態を言及しているものである必要はなく、また、他の実施形態とは相互に排他的な、別のあるいは代替的な実施形態である必要もない。さらに、本発明の１つ以上の実施形態を表わすプロセスフローチャートあるいはプロセス図におけるブロックの順序は、本質的に、いかなる特定の順序も示すものではなく、また、本発明におけるいかなる限定も意味するものでもない。
【００１２】
本発明の実施形態を、図１Ａから図６Ｂを参照して、ここに説明する。しかしながら、ここで行われるこれらの図面を参照した詳細な説明は、例示を目的とするものであって、当業者は、本発明がこれらの限られた実施形態よりも広いことを容易に認識するであろう。
【００１３】
本発明は、分散メモリマルチプロセッサコンピュータシステムにおいて、ＣＡＥ解析を用いて、物理領域の物理的挙動を数値シミュレーションする方法およびシステムに関する。
【００１４】
コンピュータシステム１００の一例を、図１Ａに示す。コンピュータシステム１００は、プロセッサ１０４の様なプロセッサを１つ以上有する。プロセッサ１０４は、コンピュータシステム内部通信バス１０２に接続されている。種々のソフトウェアの実施形態を、この例示的なコンピュータシステムに関して説明する。この説明を見れば、関連する技術分野に習熟している者には、いかにして他のコンピュータシステムおよび／またはコンピューターアーキテクチャーを用いて本発明を実行するかが明らかである。
【００１５】
コンピュータシステム１００は、また、メインメモリ１０８好ましくはランダムアクセスメモリ（ＲＡＭ））を有しており、そして補助メモリ１１０を有することもできる。補助メモリ１１０は、例えば、１つ以上のハードディスクドライブ１１２、および／または、フレキシブルディスクドライブ、磁気テープドライブ、光ディスクドライブなどを表わす１つ以上のリムーバブルストレージドライブ１１４を含むことができる。リムーバブルストレージドライブ１１４は、よく知られている方法で、リムーバブルストレージユニット１１８を読み出し、および／または、リムーバブルストレージユニット１１８に書き込む。リムーバブルストレージユニット１１８は、リムーバブルストレージドライブ１１４によって読み出し・書き込みされるフレキシブルディスク、磁気テープ、光ディスクなどを表わす。上記の内容からわかるように、リムーバブルストレージユニット１１８は、コンピューターソフトウェアおよび／またはデータを内部に記憶している、コンピュータで使用可能な記憶媒体を含む。
【００１６】
代替的な実施形態では、補助メモリ１１０は、コンピュータプログラムあるいは他の命令をコンピュータシステム１００にロードすることを可能にする他の同様な手段を有することもできる。そのような手段は、例えば、リムーバブルストレージユニット１２２とインタフェース１２０とを有してもよい。そのようなものの例には、プログラムカートリッジおよびカートリッジのインタフェース（ビデオゲーム機に見られるようなものなど）や、リムーバブルメモリチップ（ＥＰＲＯＭ（Erasable Programmable Read-Only Memory）あるいはＰＲＯＭ（Programmable Read-Only Memory）など）および関連するソケットや、リムーバブルストレージユニット１２２からコンピュータシステム１００にソフトウェアおよびデータを転送することを可能にする他のリムーバブルストレージユニット１２２およびインタフェース１２０が含まれうる。一般に、コンピュータシステム１００は、プロセススケジューリング、メモリ管理、ネットワーキングおよびＩ／Ｏ（Input/Output）サービスなどのタスクを行なうオペレーティングシステム（ＯＳ）ソフトウェアによって、制御され連係される。
【００１７】
通信インタフェース１２４も、バス１０２に接続できる。通信インタフェース１２４は、コンピュータシステム１００と外部装置との間で、ソフトウェアおよびデータを転送することを可能にする。通信インタフェース１２４の例には、モデム、ネットワークインタフェース（イーサネット（登録商標）・カードなど）、コミュニケーションポート、ＰＣＭＣＩＡ（Personal Computer Memory Card International Association）スロットおよびカードなど、が含まれうる。
【００１８】
チャンネルは、データネットワークとコンピュータシステム１００との間のデータの流れを円滑化し、典型的には、特定のセットのルール（つまりプロトコル）を実行してデータを行き来させる。一般的なプロトコルのうちの１つは、インターネットにおいて一般に用いられているＴＣＰ／ＩＰ（伝送コントロール・プロトコル／インターネット・プロトコル）である。一般に、通信インタフェース１２４は、データファイルをアセンブルしてデータネットワーク上で伝達される小さなパケットに変換することを管理し、あるいは受信したパケットを逆アセンブルして元のデータファイルに変換することを管理する。さらに、通信インタフェース１２４は、パケットが正しい宛先に届くよう、それぞれのパケットのアドレス部を処理し、あるいはコンピュータシステム１００が宛先となっているパケットをインターセプトする。
【００１９】
本明細書において、「コンピュータ可読記憶媒体」および「コンピュータが使用可能な媒体」という語は、通常、リムーバブルストレージドライブ１１４や、ハードディスクドライブ１１２に組み込まれたハードディスクなどの媒体の意味で用いられる。これらのコンピュータプログラム製品は、コンピュータシステム１００にソフトウェアを提供する手段である。本発明は、このようなコンピュータプログラム製品に対してなされたものである。
【００２０】
コンピュータシステム１００は、また、コンピュータシステム１００をモニタ、キーボード、マウス、プリンタ、スキャナ、プロッタなどにアクセスさせるＩ／Ｏインタフェース１３０を有してもよい。
【００２１】
コンピュータプログラム（コンピュータ制御ロジックともいう）は、メインメモリ１０８および／または補助メモリ１１０にアプリケーションモジュール１０６として記憶される。コンピュータプログラムは、通信インタフェース１２４を介して受け取られてもよい。このようなコンピュータプログラムが実行された時、コンピュータプログラムによって、コンピュータシステム１００がここに説明される本発明の特徴を実行することが可能になる。詳細には、コンピュータプログラムが実行された時、コンピュータプログラムによって、プロセッサ１０４が本発明の特徴を実行することが可能になる。したがって、このようなコンピュータプログラムは、コンピュータシステム１００のコントローラを表わしている。
【００２２】
ソフトウェアを用いて発明が実行される実施形態においては、ソフトウェアをコンピュータプログラム製品に記憶でき、リムーバブルストレージドライブ１１４、ハードディスクドライブ１１２あるいは通信インタフェース１２４を用いてコンピュータシステム１００へとロードすることができる。アプリケーションモジュール１０６は、プロセッサ１０４によって実行された時、プロセッサ１０４に、ここに説明される本発明の機能を実行させる。
【００２３】
所望のタスクを達成するために、Ｉ／Ｏインタフェース１３０を介したユーザ入力によって、あるいは、ユーザ入力によることなしに、１つ以上のプロセッサ１０４によって実行することができる１つ以上のアプリケーションモジュール１０６を、メインメモリ１０８にロードすることもできる。動作中、少なくとも１つのプロセッサ１０４がアプリケーションモジュール１０６のうちの１つを実行すると、結果が演算されて補助メモリ１１０（つまりハードディスクドライブ１１２）に記憶される。演算の状況（例えばＣＡＥ解析の進行状況）は、Ｉ／Ｏインタフェース１３０を介してユーザに報告される。状況を、視覚的に認識するためにグラフィック表現で示すこともできる。グラフィック出力はＩ／Ｏインタフェース１３０を介してモニタに送信される。
【００２４】
図１Ｂは、本発明の実施形態を実装できる、例示的な分散メモリマルチプロセッサコンピュータシステム１４０を示す。分散メモリマルチプロセッサコンピュータシステム１４０は、通信リンク１５５（例えばイーサネット（登録商標）、インターネットなど）を介して互いに機能的に適合している複数の演算ユニット１５０ａ〜１５０ｎを有する。演算ユニット１５０ａ〜１５０ｎのそれぞれは、それ自身の、プロセッサ１５１ａ〜１５１ｎとメモリ１５２ａ〜１５２ｎとを有する。メモリ１５２ａ〜１５２ｎが分散しているので、通信リンク１５５を介した比較的遅いデータ通信は、本発明において回避すべきボトルネックである。
【００２５】
図２Ａおよび図２Ｂを参照して、本発明の一実施形態に係る、分散メモリマルチプロセッサコンピュータシステムにおけるＣＡＥ解析に用いられる、物理領域の物理的挙動を数値シミュレーションする例示的なプロセス２００、を示すフローチャートを説明する。プロセス２００は、好ましくはソフトウェアで実行される。プロセス２００は、他の図面により理解されよう。
【００２６】
ステップ２０２において、分散メモリマルチプロセッサコンピュータシステム（例えば図１Ｂに示すコンピュータシステム１４０）が物理領域の演算モデルを受け付けることによって、プロセス２００はスタートする。一実施形態では、演算モデルは、図3に示す非構造格子の複数の有限要素によって接続される複数のノードを有するＦＥＡモデル３００である。図４は、使用可能な種々の例示的なタイプの有限要素を示す。例示的なタイプの有限要素には、１次元のビームまたはトラス要素４０２、２次元の三角形要素４１２、２次元の四角形要素４１４、３次元の四面体要素４２２、および３次元の六面体要素４２４を含む。
【００２７】
物理領域は、製品（例えば自動車、飛行機および／またはそれらの部品）とできる。他の実施形態において、演算モデルを境界要素法（ＢＥＭ）モデルとできる。ＢＥＭモデルは、複数のＢＥＭ面によって接続される複数のノードを有する。物理領域は、ＢＥＭモデルによって囲まれた液体または空気とできる。
【００２８】
ステップ２０４で、コンピュータシステムにインストールされたアプリケーションモジュールを用いて、演算モデルから、物理領域の物性を表すＮ×Ｎマトリックスが生成される。１つの例示的な物理的特性は剛性である。Ｎは正の整数である。また、Ｎは演算モデルにおける自由度を表す。Ｎ×Ｎマトリックスは、物理領域のＮ個の未知の物理量についてのＮ個の連立一次方程式の係数を含んでいる。未知の物理量の１つの例は演算モデルのノードの変位である。例示的な剛性マトリックス５１０を図５Ａに示す。未知のノードの変位５１２は、各ノードに対し６自由度を有する。マトリックス５１０はビーム要素（例えば図４の要素４０２）に対するものである。要素剛性マトリックスから、全体的剛性マトリックスが構成される。Ｎ自由度の簡易化されたマトリックス５５０を、図５Ｂに示す。ＦＥＡモデルから生成された典型的な剛性マトリックスは一般に疎である（つまり、非対角項の多くはゼロである）。
【００２９】
次にステップ２０６では、無向グラフがＮ×Ｎマトリックスを表すために用いられる。無向グラフは、複数の辺によって接続されるＮ個の頂点を含んでいる。各頂点は、それぞれのＮ自由度に関連するＮ個の未知の物理量のうちの１つに対応する。各辺はＮ×Ｎマトリックスにおけるゼロでない項を表す。図６Ａは、図５Ａの要素剛性マトリックス５１０に関する例示的なグラフを示す。例示的な無向グラフ６５０を図６Ｂに示す。
【００３０】
分散メモリマルチプロセッサコンピュータシステムにおけるＮ個の連立一次方程式を効率的に解くために、プロセッサ間通信、記憶装置および演算能力（例えばプロセッサの数）などの演算リソースを最小化して演算時間を低減する分割法で、Ｎ×Ｎマトリックスは記憶される必要がある。ステップ２０８では、演算リソースを低減するように構成されるユーザ定義基準に従って、Ｎ個の頂点を、分離グループと、第１および第２の相互独立グループに分割する最適な分割法が決定される。最適な分割法は以下のステップで決定される。
【００３１】
ステップ２０８ａで、多数の源点のそれぞれの距離ベクトルが演算される。一実施形態では、源点は、Ｎ個の頂点から任意にランダムに選択される。距離ベクトルは、無向グラフにおける二つの頂点間の最小経路長である。ステップ２０８ｂでは、それぞれの別のペアの源点に対して、以下のように試行分割法が決定される。
ａ）隣接疎マトリックスが５重対角行列である疎のグラフを検出するよう、ハーフレベルセットベクトル（つまり、それぞれの距離ベクトルの差異）を用いる。
ｂ）疎のグラフを用いて、分離グループと、第１および第２の相互独立グループと、を初期検出する。
ｃ）分離グループが最小になるまで、分離グループに含まれている１つ以上の頂点を取り出し、第１および第２の相互独立グループの一方に併合することにより、分離グループを反復的に改善する。
ステップ２０８ｃでは、全体的演算リソース（例えば分散メモリマルチプロセッサコンピュータシステムのプロセッサ間のプロセッサ間通信）を低減するように構成されるユーザ定義基準に従って、全ての試行分割法を比較することによって、最適な分割法が決定される。
【００３２】
例示的な１のユーザ定義基準は、第１および第２の相互独立グループにおける頂点の数の不均衡および差異に基づく。
不均衡＝最大値(max)（|B|，|W|）／最小値(min)（|B|，|W|）
差異＝絶対値(abs)（|B|−|W|）／（|B|＋|W|＋|S|）
ここで、|B|は第一の相互独立グループにおける頂点の数である。|W|は第二の相互独立グループにおける頂点の数である。|S|は分離グループにおける頂点の数である。
【００３３】
各試行分割法の演算コストを評価するために、２つのユーザが付与するパラメータαおよびパラメータβが以下の通り用いられる。
If不均衡＜α then（不均衡＜αの場合、）
コスト=|S|×（１＋β×差異）
else（その他の場合、）
コスト＝無限大
end（終了）
１の実施形態では、αは１．３であり、βは０．３である。
【００３４】
最後に、ステップ２１０で、最適な分割法に従って、分散メモリマルチプロセッサコンピュータシステムのそれぞれの記憶システムに記憶されるＮ×Ｎマトリックスを用いてＮ個の連立一次方程式のＮ個の未知の量を解くことにより、ＣＡＥ解析において物理領域の数値シミュレーションされた物理的挙動が得られる。
【００３５】
本発明を、具体的な実施形態を参照しながら説明したが、これらの実施形態は単なる例示であって、本発明を限定するものではない。具体的に開示された例示的な実施形態に対する種々の変更あるいは変形を、当業者は思いつくであろう。例えば、製品の物性を表すマトリックスを剛性マトリックスとして説明したが、他の物性、例えば固有値評価マトリックスを用いることができる。さらに、コンピュータ支援エンジニアリング解析として、陰解法有限要素法を説明したが、他のタイプ、例えば境界要素法を用いることができる。つまり、本発明の範囲は、ここで開示した具体的で例示的な実施形態に限定されず、当業者が容易に想到するあらゆる変更が、本願の精神および範囲、そして添付の特許請求の範囲の権利範囲に含まれる。
【符号の説明】
【００３６】
１００  コンピュータシステム
１０２  バス
１０４  プロセッサ
１０６  モジュール
１０８  メインメモリ（ＲＡＭ）
１１０  補助メモリ
１１２  ハードディスクドライブ
１１４  リムーバブルストレージドライブ
１１８  リムーバブルストレージユニット
１２０  インタフェース
１２２  リムーバブルストレージユニット
１２４  通信インタフェース
１３０  Ｉ／Ｏインタフェース
１４０  分散メモリマルチプロセッサコンピュータシステム
１５０ａ〜１５０ｎ  演算ユニット
１５１ａ〜１５１ｎ  プロセッサ
１５２ａ〜１５２ｎ  メモリ
１５５  通信リンク
３００  ＦＥＡモデル
４０２  １次元のビーム要素
４１２  ２次元の三角形要素
４１４  ２次元の四角形要素
４２２  ３次元の四面体要素
４２４  ３次元の六面体要素
５１０  剛性マトリックス
５１２  未知のノードの変位
５５０  簡単化されたマトリックス
６５０  無向グラフ
【先行技術文献】
【非特許文献】
【００３７】
【非特許文献１】"Nested Dissection of a Regular Finite Element Mesh"(Alan George， SIAM Journal on Numerical Analysis， Vol. 10， No. 2、1973年4月
【図１Ａ】
2014225257.tif 000003
【図１Ｂ】
2014225257.tif 000004
【図２Ａ】
2014225257.tif 000005
【図２Ｂ】
2014225257.tif 000006
【図３】
2014225257.tif 000007
【図４】
2014225257.tif 000008
【図５Ａ】
2014225257.tif 000009
【図５Ｂ】
2014225257.tif 000010
【図６Ａ】
2014225257.tif 000011
【図６Ｂ】
2014225257.tif 000012
【外国語明細書】
TITLE OF INVENTION
Methods and systems for using bi-directional level sets to partition an undirected graph representing a matrix to be used in CAE
FIELD OF THE INVENTION
The present invention generally relates to methods, systems and software product used in computer-aided engineering analysis (CAE), more particularly to methods and systems for using bi-directional level sets to partition an undirected graph representing a matrix used in CAE analysis (e.g. implicit finite element analysis (FEA), boundary element analysis, etc.) of a physical domain (e.g., a product such as car, airplane, and/or their components) in a distributed memory multi-processor computer system. 
BACKGROUND OF THE INVENTION
Finite element analysis (FEA) is one of the popular CAE analyses widely used in industry to model and solve engineering problems related to complex systems such as three-dimensional non-linear structural design and analysis.  FEA derives its name from the manner in which the geometry of the object under consideration is specified. With the advent of the modern digital computer, FEA has been implemented as FEA software.  Basically, the FEA software is provided with a model of the geometric description and the associated material properties at each point within the model. In this model, the geometry of the system under analysis is represented by solids, shells and beams of various sizes, which are called elements. The corners of the elements are referred to as nodes. Each node has 6-degrees of freedom in three-dimensional space. The model is comprised of a finite number of elements, which are assigned a material name to associate with material properties. The model thus represents the physical space occupied by the object under analysis along with its immediate surroundings.  The FEA software then refers to a table in which the properties (e.g., stress-strain constitutive equation, Young’s modulus, Poisson’s ratio, thermo-conductivity) of each material type are tabulated. Additionally, the conditions at the boundary of the object (i.e., loadings, physical constraints, etc.) are specified. In this fashion a model of the object and its environment is created. 
There are two types of FEA software - explicit and implicit. The present invention is related to implicit FEA software, which requires solving a system of simultaneous linear equations with one equation representing each degree-of-freedom. For example, a static analysis involves solving N simultaneous linear equations represented by an NxN stiffness matrix with N unknown displacements and N nodal forces and/or moments as the right hand side of the simultaneous linear equations. N is a positive integer.  With the improvement of the finite element software and computer hardware technologies, many today's FEA model includes huge number of unknowns (e.g., often in the order of millions).  The NxN matrix for a FEA model is sparse (i.e., there are many zeros).  A number of techniques have been used to improve the performance of solving such a matrix both in serial and parallel computations.  In a distributed memory multi-processor computer system, one of the keys to improve sparse matrix solver performance is to partition the matrix in a partition scheme that can reduce the inter-processor communications.  However, partitioning a large sparse matrix is not an easy task.  Prior art approaches are generally based on "Nested Dissection of a Regular Finite Element Mesh" by Alan George, SIAM Journal on Numerical Analysis, Vol. 10, No. 2. April 1973.  
However the prior art approaches do not work well in a distributed memory computer system. Therefore, it would be desirable to have improved methods and systems for partitioning a graph representing a matrix to be used in CAE analysis of a physical domain in a distributed memory multi-processor computer system.
SUMMARY OF THE INVENTION
This section is for the purpose of summarizing some aspects of the present invention and to briefly introduce some preferred embodiments. Simplifications or omissions may be made to avoid obscuring the purpose of the section. Such simplifications or omissions are not intended to limit the scope of the present invention.
Methods and systems for numerically simulating physical behaviors of a physical domain using CAE analysis in a distributed memory multi-processor computer system are disclosed.  According to one exemplary embodiment of the present invention, a computerized model (e.g., an unstructured finite element analysis model) representing the physical domain (e.g., a product such as car, airplane, etc.) is defined and received in the computer system. An NxN matrix is generated from the computerized model for representing a physical characteristic property (e.g., stiffness) of the physical domain, where the NxN matrix comprises coefficients of N simultaneous linear equations with N unknown physical quantities (e.g., N nodal displacements at respective degrees-of-freedom, N is a positive integer) of the physical domain.  The matrix is then represented by an undirected graph having N vertices connected by a plurality of edges. Each vertex corresponds to a degree-of-freedom and each edge represents a non-zero term in the matrix.  
In order to efficiently perform a CAE analysis in a distributed memory multi-processor computer system, a best suitable partition scheme is determined for dividing the N vertices into a separator group and, first and second mutually independent groups.  Vertices in the first independent group are not connected to those in the second independent group by any edge.  According one aspect of the present invention, a group of source vertices is selected from the N vertices (e.g., arbitrarily selected in random). Then respective distance vectors of the source vertices are calculated.  A distance vector is a minimum path length between two vertices in the graph. For each distinct pair of the source vertices, a half-level set vector (i.e., the difference of respective distance vectors) is used to find a coarse graph whose adjacency coarse matrix is pentadiagonal; a trial partition scheme is determined using the coarse graph initially; the separator group is then improved by trimming one or more vertices contained therein and merging them into either one of the first and second mutually independent groups until the separator group becomes minimal.  Finally, the best suitable partition scheme is determined by comparing all of the trial partition schemes in accordance with a user defined criterion, which is configured to reduce the overall computing resources of solving the N simultaneous linear equations in the distributed memory multi-processor computer system (e.g., inter-processor communications).  This partitioning is applied recursively until the size of the resulting partition is appropriate for the computer environment used to solve the system of simultaneous linear equations, for example, the number of processors, the size of local memory for each processor, etc. The simulated physical behaviors (e.g., structural behaviors) are obtained by solving the NxN simultaneous linear equations in a CAE analysis in the computer system with the NxN matrix stored according to the best suitable partition scheme.
Objects, features, and advantages of the present invention will become apparent upon examining the following detailed description of an embodiment thereof, taken in conjunction with the attached drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
These and other features, aspects, and advantages of the present invention will be better understood with regard to the following description, appended claims, and accompanying drawings as follows:
FIG. 1A is a function block diagram showing salient components of an exemplary computer system, in which an embodiment of the present invention may be implemented. 
FIG. 1B is a block diagram showing an exemplary distributed memory multi-processor computer system;
FIGS. 2A and 2B collectively show a flowchart illustrating an exemplary process of using bi-directional level sets to partition a undirected graph representing a matrix used in CAE analysis of a physical domain, according to an embodiment of the present invention;
FIG. 3 is a diagram showing an exemplary FEA model of a physical domain;
FIG. 4 is a diagram showing various exemplary finite elements;
FIG. 5A is a diagram showing a stiffness matrix of an exemplary finite element;
FIG. 5B is a diagram showing a simplified matrix representing an exemplary physical property of a physical domain in accordance with one embodiment of the present invention;
FIG. 6A is a diagram showing exemplary graphs representing the element stiffness matrix shown in FIG. 5A; and
FIG. 6B is a diagram showing an exemplary undirected graph in accordance with one embodiment of the present invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention.  However, it will become obvious to those skilled in the art that the present invention may be practiced without these specific details.  The descriptions and representations herein are the common means used by those experienced or skilled in the art to most effectively convey the substance of their work to others skilled in the art.  In other instances, well-known methods, procedures, and components have not been described in detail to avoid unnecessarily obscuring aspects of the present invention.
Reference herein to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment can be included in at least one embodiment of the invention.  The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments.  Further, the order of blocks in process flowcharts or diagrams representing one or more embodiments of the invention do not inherently indicate any particular order nor imply any limitations in the invention.
Embodiments of the present invention are discussed herein with reference to FIGS. 1A-6B. However, those skilled in the art will readily appreciate that the detailed description given herein with respect to these figures is for explanatory purposes as the invention extends beyond these limited embodiments.
The present invention is related to methods and systems for numerically simulating physical behaviors of a physical domain using CAE analysis in a distributed memory multi-processor computer system. 
An example of a computer system 100 is shown in FIG. 1A. The computer system 100 includes one or more processors, such as processor 104. The processor 104 is connected to a computer system internal communication bus 102. Various software embodiments are described in terms of this exemplary computer system. After reading this description, it will become apparent to a person skilled in the relevant art(s) how to implement the invention using other computer systems and/or computer architectures.
Computer system 100 also includes a main memory 108, preferably random access memory (RAM), and may also include a secondary memory 110. The secondary memory 110 may include, for example, one or more hard disk drives 112 and/or one or more removable storage drives 114, representing a floppy disk drive, a magnetic tape drive, an optical disk drive, etc. The removable storage drive 114reads from and/or writes to a removable storage unit 118 in a well-known manner. Removable storage unit 118, represents a floppy disk, magnetic tape, optical disk, etc. which is read by and written to by removable storage drive 114. As will be appreciated, the removable storage unit 118includes a computer usable storage medium having stored therein computer software and/or data. 
In alternative embodiments, secondary memory 110 may include other similar means for allowing computer programs or other instructions to be loaded into computer system 100. Such means may include, for example, a removable storage unit 122 and an interface 120. Examples of such may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM, or PROM) and associated socket, and other removable storage units 122 and interfaces 120 which allow software and data to be transferred from the removable storage unit 122 to computer system 100. Ingeneral, Computer system 100 is controlled and coordinated by operating system (OS) software, which performs tasks such as process scheduling, memory management, networking and I/O services.  
There may also be a communications interface 124 connecting to the bus 102. Communications interface 124 allows software and data to be transferred between computer system 100and external devices. Examples of communications interface 124 may include a modem, a network interface (such as an Ethernet card), a communications port, a PCMCIA slot and card, etc.  
The channel facilitates a data flow between a data network and the computer 100 and typically executes a special set of rules (i.e., a protocol) to send data back and forth.  One of the common protocols is TCP/IP (Transmission Control Protocol/Internet Protocol) commonly used in the Internet. In general, the communication interface 124 manages the assembling of a data file into smaller packets that are transmitted over the data network or reassembles received packets into the original data file. In addition, the communication interface 124 handles the address part of each packet so that it gets to the right destination or intercepts packets destined for the computer 100.
In this document, the terms "computer readable storage medium" and "computer usable medium" are used to generally refer to media such as removable storage drive 114, ahard disk installed in hard disk drive 112. These computer program products are means for providing software to computer system 100. The invention is directed to such computer program products. 
The computer system 100may also include an I/O interface 130, which provides the computer system 100to access monitor, keyboard, mouse, printer, scanner, plotter, and alike.
Computer programs (also called computer control logic) are stored as application modules 106 in main memory 108 and/or secondary memory 110. Computer programs may also be received via communications interface 124. Such computer programs, when executed, enable the computer system 100 to perform the features of the present invention as discussed herein. In particular, the computer programs, when executed, enable the processor 104 to perform the features of the present invention. Accordingly, such computer programs represent controllers of the computer system 100. 
In an embodiment where the invention is implemented using software, the software may be stored in a computer program product and loaded into computer system 100 using removable storage drive 114, hard drive 112, or communications interface 124. The application module 106, when executed by the processor 104, causes the processor 104 to perform the functions of the invention as described herein. 
The main memory 108may be loaded with one or more application modules 106 that can be executed by one or more processors 104 with or without a user input through the I/O interface 130 to achieve desired tasks. In operation, when at least one processor 104 executes one of the application modules 106, the results are computed and stored in the secondary memory 110 (i.e., hard disk drive 112). The status of the computation (e.g., progress of a CAE analysis) is reported to the user via the I/O interface 130. The status may be shown graphically for visual inspection.  The graphical output is sent through the I/O interface 130 to a monitor. 
FIG. 1B shows an exemplary distributed memory multi-processor computer system 140, in which an embodiment of the present invention may be implemented.  The distributed memory multi-processor computer system 140 contains a plurality of computing units 150a-150n operatively adapted to one another via a communication link 155 (e.g., Ethernet, Internet, etc.).  Each of the computing units 150a-150n contains its own processor 151a-151n and memory 152a-152n. Because the memories 152a-152n are distributed, the relatively slower data communication via the link 155 is a bottleneck to be avoided in the present invention.
Referring now to FIGS. 2A and 2B, a flowchart illustrating an exemplary process 200 of numerically simulating physical behaviors of a physical domain using a CAE analysis in a distributed memory multi-processor computer system is shown, according to an embodiment of the present invention. Process 200 is preferably implemented in software and understood with other figures.
Process 200 starts at step 202 by receiving a computerized model of a physical domain in a distributed memory multi-processor computer system (e.g., computer system 140 shown in FIG. 1B). In one embodiment, computerized model can be a FEA model 300 having a plurality of nodes connected by a plurality of finite elements in unstructured manner shown in FIG. 3. FIG. 4 shows various exemplary types of finite elements that can be used: 1-dimensional beam or truss element 402, 2-dimensional triangular element 412, 2-dimensional quadrilateral element 414, 3-dimensional tetrahedral element 422 and 3-dimensional hexahedral element 424.
Physical domain can be a product (e.g., car, airplane and/or their components).  In another embodiment, computerized model can be a boundary element method (BEM) model containing a plurality of nodes connected by a plurality of BEM faces. Physical domain can be the fluid or air enclosed by the BEM model.
At step 204, an NxN matrix represent a physical characteristic property of the physical domain is generated from the computerized model using an application module installed on the computer system. One exemplary physical characteristic property is the stiffness. N is a positive integer and N represents the number of degree-of-freedom in the computerized model. The NxN matrix contains coefficients of N simultaneous linear equations with N unknown physical quantities of the physical domain.  One example of the unknown physical quantities is nodal displacement of the computerized model. An exemplary stiffness matrix 510 is shown in FIG. 5A. Unknown nodal displacements 512 are at six degrees-of-freedom for each node.  The matrix 510 is for a beam element (e.g., element 402 of FIG. 4). Element stiffness matrices are assembled into a global stiffness matrix. A simplified matrix 550 having N degrees-of-freedom is shown in FIG. 5B. A typical stiffness matrix generated from a FEA model is generally sparse (i.e., many of the off-diagonal terms are zeros).
Next, at step 206, an undirected graph is used to represent the NxN matrix. The undirected graph contains N vertices connected by a plurality of edges.  Each vertex corresponds to one of the N unknown physical quantities associated with respective N degrees-of-freedom. Each edge represents a non-zero term in the NxN matrix. FIG. 6A shows exemplary graphs for element stiffness matrix 510 of FIG. 5A.  An exemplary undirected graph 650 is shown in FIG. 6B.
In order to efficiently solving the N simultaneous linear equations in the distributed memory multi-processor computer system, the NxN matrix needs to be stored in a partition scheme that minimizes computing resources such as inter-processor communications, storage and computational power (e.g., number of processors) thereby reducing the computational time.  At step 208, a best suitable partition scheme for dividing the N vertices into a separator group and, first and second mutually independent groups in accordance with a user defined criterion that is configured to reduce computing resources.  The best suitable partition scheme is determined with following steps. 
At step 208a, respective distance vectors of a number of source vertices are calculated.  According to one embodiment, the source vertices are chosen arbitrarily in random from the N vertices.  The distance vector is the minimum path length between two vertices in the undirected graph. At step 208b, a trial partition scheme is determined for each distinct pair of the source vertices by a) using a half-level set (i.e., the difference of respective distance vectors) to find a coarse graph whose adjacency coarse matrix is pentadiagonal; b) initially finding the separator group and, first and second mutually independent groups using the coarse graph; and c) iteratively improving the separator group by trimming one or more vertices contained therein and merging them into one of the first and second mutually independent groups until the separator group becomes minimal. At step 208c, a best suitable partition scheme is determined by comparing all of the trial partition schemes in accordance with the user defined criterion that is configured to reduce overall computing resources (e.g., inter-processor communications between processors of a distributed memory multi-processor computer system). 
One exemplary user defined criterion is based on the imbalance and the difference of the number of vertices in the first and second mutually independent groups. 
imbalance = max (|B|,|W|) / min (|B|,|W|)
difference  = abs (|B|-|W|) / (|B|+|W|+|S|)
where:
|B| is the number of vertices in the first mutually independent group.
|W| is the number of vertices in the second mutually independent group.
|S| is the number of vertices in the separator group.
To estimate the cost of computation for each trial partition scheme, two user provided parameters α and β are used in the following manner:
If imbalance < α then
Cost = |S| (1+ βdifference)
else
Cost = infinity
end
In one embodiment, α is 1.3 while β is 0.3.
Finally, at step 210, numerically simulated physical behaviors of the physical domain are obtained in a CAE analysis by solving for N unknowns of the N simultaneous linear equations with the NxN matrix stored in respective memory systems of the distributed memory multi-processor computer system according to the best suitable partition scheme. 
Although the present invention has been described with reference to specific embodiments thereof, these embodiments are merely illustrative, and not restrictive of, the present invention. Various modifications or changes to the specifically disclosed exemplary embodiments will be suggested to persons skilled in the art. For example, whereas the matrix representing physical characteristic of the product has been shown and described as the stiffness matrix, other physical characteristics can be used, for example, eigenvalue evaluation matrix. Further, implicit finite element method has been shown and described as the computer-aided engineering analysis, other types can be used, for example, boundary element method. In summary, the scope of the invention should not be restricted to the specific exemplary embodiments disclosed herein, and all modifications that are readily suggested to those of ordinary skill in the art should be included within the spirit and purview of this application and scope of the appended claims. 
CLAIMS
What is claimed is:
1.  A computer-implemented method of numerically simulating physical behaviors of a physical domain using a computer-aided engineering (CAE)analysis, the method comprising:
receiving a computerized model representing a physical domain in a distributed
memory multi-processor computer system, the computerized model comprising a
plurality of nodes connected by a plurality of elements in an unstructured
manner, wherein the computerized model contains N degrees-of-freedom
associated with the nodes, N is a positive integer; 
generating an NxN matrix representing a physical characteristic property of
the physical domain from the computerized model using a CAE application
module installed on the distributed memory multi-processor computer system,
wherein the NxN matrix comprises coefficients of N simultaneous linear
equations with N unknown physical quantities of the physical domain, each
unknown physical quantity being associated with one of the N degrees-of
freedom;
using an undirected graph containing N vertices connected by a plurality of
edges to represent the NxN matrix, the N vertices corresponding to the
respective N degrees-of-freedom while the edges representing respective non
zero terms in the NxN matrix;
calculating respective distance vectors of a plurality of source vertices
selected from the N vertices;
for each distinct pair of the source vertices, determining a trial partition
scheme for dividing the N vertices into a separator group and, first and
second mutually independent groups by
a) using a half-level set vector to find a coarse graph whose adjacency
coarse matrix is pentadiagonal, the half-level set vector being the
difference of said corresponding distance vectors of the distinct pair, 
b) initially determining the separator group and, the first and second
mutually independent groups using the coarse graph, and 
c) iteratively improving the separator group by trimming vertices contained
therein and merging into one of the first and the second mutually
independent groups until the separator group becomes minimal, wherein the
first and the second mutually independent groups are unconnected by any of
the edges; and
comparing all trial partition schemes to determine a best suitable partition
scheme based on a user defined criterion that is configured to reduce
overall computing resources for solving the N simultaneous linear equations,
wherein the overall computing resources include inter-processor
communications between processors of the distributed memory multi-processor
computer system; and 
obtaining numerically simulated physical behaviors of the physical domain by
solving the N unknown physical quantities with the NxN matrix stored in
corresponding memory systems of the distributed memory multi-processor
computer system according to the best suitable partition scheme.
2.  The method of claim 1, wherein said physical behaviors of the physical domain are structural behaviors of a product and said computerized model comprises a finite element analysis model with the elements comprising finite elements.
3.  The method of claim 2,wherein the physical characteristic property of the physical domain is stiffness and the unknown physical quantities are displacements at the nodes of the finite element analysis model.
4.  The method of claim 1, wherein said selecting a group of source vertices from the N vertices are selected arbitrarily in random.
5.  The method of claim 1, wherein said distance vectors represent minimum path length between said distinct pair of source vertices in the undirected graph.
6.  The method of claim 1, wherein the user defined criterion is based on imbalance and difference of the first and second mutually independent groups, wherein the imbalance and the difference are defined as follows:
imbalance = max (|B|,|W|) / min (|B|,|W|)
difference  = abs (|B|-|W|) / (|B|+|W|+|S|)
where:
|B| is the number of vertices in the first independent group,
|W| is the number of vertices in the second independent group,
|S| is the number of vertices in the separator group.
7.  The method of claim 6, wherein the user defined criterion further includes first and second user provided parameters for estimating a computational cost indicator of a particular partition scheme as follows: if said imbalance is less than the first parameter, then the computational cost indicator is equal to  
|S| (1+ said difference x the second parameter), otherwise the computational cost indicator is infinite.
8.  A system for numerically simulating physical behaviors of a physical domain using a computer-aided engineering (CAE) analysis, the system comprising:
first and second processors having respective first and second memory systems
coupled thereon locally, the first processor and the first memory system
being operatively coupled to the second processor and the second memory
system via at least one inter-processor communication link;
a CAE application module containing computer readable code being stored on the
first and/or the second memory systems, when executed in a corresponding
processor causing the CAE application module to perform operations by a
method of:
receiving a computerized model representing a physical domain, the
computerized model comprising a plurality of nodes connected by a plurality
of elements in an unstructured manner, wherein the computerized model
contains N degrees-of-freedom that are associated with the nodes, N is a
positive integer; 
generating an NxN matrix representing a physical characteristic property of
the physical domain from the computerized model, wherein the NxN matrix
comprises coefficients of N simultaneous linear equations with N unknown
physical quantities of the physical domain, each unknown physical quantity
being associated with one of the N degrees-of-freedom;
using an undirected graph containing N vertices connected by a plurality of
edges to represent the NxN matrix, the N vertices corresponding to the
respective N degrees-of-freedom while the edges representing respective non
zero terms in the NxN matrix;
calculating respective distance vectors of a plurality of source vertices
selected from the N vertices;
for each distinct pair of the source vertices, determining a trial partition
scheme for dividing the N vertices into a separator group and, first and
second mutually independent groups by
a) using a half-level set vector to find a coarse graph whose adjacency
coarse matrix is pentadiagonal, the half-level set vector being the
difference of said corresponding distance vectors of the distinct pair, 
b) initially determining the separator group and, the first and second
mutually independent groups using the coarse graph, and 
c) iteratively improving the separator group by trimming vertices contained
therein and merging into one of the first and the second mutually
independent groups until the separator group becomes minimal, wherein the
first and the second mutually independent groups are unconnected by any of
the edges; and
comparing all trial partition schemes to determine a best suitable partition
scheme based on a user defined criterion that is configured to reduce
overall computing resources for solving the N simultaneous linear equations,
wherein the overall computing resources include inter-processor
communications between the first and second processors; and 
obtaining numerically simulated physical behaviors of the physical domain by
solving the N unknown physical quantities with the NxN matrix stored in in
the first and the second memory systems according to the best suitable
partition scheme.
9.  The system of claim 8, wherein said physical behaviors of the physical domain are structural behaviors of a product and said computerized model comprises a finite element analysis model with the elements comprising finite elements. 
10.  The system of claim 9, wherein the physical characteristic property of the physical domain is stiffness and the unknown physical quantities are displacements at the nodes of the finite element analysis model.
11.  The system of claim 8, wherein said selecting a group of source vertices from the N verticesare selected arbitrarily in random.
12.  The system of claim 8, wherein said distance vectors represent minimum path length between said distinct pair of source vertices in the undirected graph.
13.  The system of claim 8, wherein the user defined criterion is based on imbalance and difference of the first and second mutually independent groups, wherein the imbalance and the difference are defined as follows:
imbalance = max (|B|,|W|) / min (|B|,|W|)
difference  = abs (|B|-|W|) / (|B|+|W|+|S|)
where:
|B| is the number of vertices in the first independent group,
|W| is the number of vertices in the second independent group,
|S| is the number of vertices in the separator group.
14.  The system of claim 13, wherein the user defined criterion further includes first and second user provided parameters for estimating a computational cost indicator of a particular partition scheme as follows: if said imbalance is less than the first parameter, then the computational cost indicator is equal to  |S| (1+ said difference x the second parameter), otherwise the computational cost indicator is infinite.
15.  A non-transitory computer readable storage medium containing computer executable instructions for numerically simulating physical behaviors of a physical domain using a computer-aided engineering (CAE) analysis by a method comprising:
receiving a computerized model representing a physical domain in a distributed
memory multi-processor computer system, the computerized model comprising a
plurality of nodes connected by a plurality of elements in an unstructured
manner, wherein the computerized model contains N degrees-of-freedom
associated with the nodes, N is a positive integer; 
generating an NxN matrix representing a physical characteristic property of
the physical domain from the computerized model using a CAE application
module installed on the distributed memory multi-processor computer system,
wherein the NxN matrix comprises coefficients of N simultaneous linear
equations with N unknown physical quantities of the physical domain, each
unknown physical quantity being associated with one of the N degrees-of
freedom;
using an undirected graph containing N vertices connected by a plurality of
edges to represent the NxN matrix, the N vertices corresponding to the
respective N degrees-of-freedom while the edges representing respective non
zero terms in the NxN matrix;
calculating respective distance vectors of a plurality of source vertices
selected from the N vertices;
for each distinct pair of the source vertices, determining a trial partition
scheme for dividing the N vertices into a separator group and, first and
second mutually independent groups by
a) using a half-level set vector to find a coarse graph whose adjacency
coarse matrix is pentadiagonal, the half-level set vector being the
difference of said corresponding distance vectors of the distinct pair, 
b) initially determining the separator group and, the first and second
mutually independent groups using the coarse graph, and 
c) iteratively improving the separator group by trimming vertices contained
therein and merging into one of the first and the second mutually
independent groups until the separator group becomes minimal, wherein the
first and the second mutually independent groups are unconnected by any of
the edges; and
comparing all trial partition schemes to determine a best suitable partition
scheme based on a user defined criterion that is configured to reduce
overall computing resources for solving the N simultaneous linear equations,
wherein the overall computing resources include inter-processor
communications between processors of the distributed memory multi-processor
computer system; and 
obtaining numerically simulated physical behaviors of the physical domain by
solving the N unknown physical quantities with the NxN matrix stored in
corresponding memory systems of the distributed memory multi-processor
computer system according to the best suitable partition scheme.
16.  The non-transitory computer readable storage medium of claim 15, wherein said physical behaviors of the physical domain are structural behaviors of a product and said computerized model comprises a finite element analysis model with the elements comprising finite elements. 
17.  The non-transitory computer readable storage medium of claim 16, wherein the physical characteristic property of the physical domain is stiffness and the unknown physical quantities are displacements at the nodes of the finite element analysis model.
18.  The non-transitory computer readable storage medium of claim 15, wherein said selecting a group of source vertices from the N vertices are selected arbitrarily in random.
19.  The non-transitory computer readable storage medium of claim 15, wherein the user defined criterion is based on imbalance and difference of the first and second mutually independent groups, wherein the imbalance and the difference are defined as follows:
imbalance = max (|B|,|W|) / min (|B|,|W|)
difference  = abs (|B|-|W|) / (|B|+|W|+|S|)
where:
|B| is the number of vertices in the first independent group,
|W| is the number of vertices in the second independent group,
|S| is the number of vertices in the separator group.
20.  The non-transitory computer readable storage medium of claim 19, wherein the user defined criterion further includes first and second user provided parameters for estimating a computational cost indicator of a particular partition scheme as follows: if said imbalance is less than the first parameter, then the computational cost indicator is equal to  |S| (1+ said difference x the second parameter), otherwise the computational cost indicator is infinite.
ABSTRACT OF THE DISCLOSURE
An NxN matrix is generated from computerized model representing a physical domain, comprises coefficients of N simultaneous linear equations with N unknown physical quantities associated with N degrees-of-freedom of the physical domain, and is represented by an undirected graph having N vertices connected by a plurality of edges. A best suitable partition scheme for dividing the N vertices into a separator group and, first and second mutually independent groups as follows: distance vectors of source vertices selected from the N vertices are calculated;  for each distinct pair of the source vertices, the difference of respective distance vectors is used for finding a coarse graph whose adjacency coarse matrix is pentadiagonal; a trial partition scheme is determined using the coarse graph initially; the separator group is then iteratively improved by trimming vertices contained therein and merging them into one of the mutually independent groups until the separator group becomes minimal.
[Fig.2A]
Figure 1A
2014225257.tif 000013
Figure 1B
2014225257.tif 000014
Figure 2A
2014225257.tif 000015
Figure 2B
2014225257.tif 000016
Figure 3
2014225257.tif 000017
Figure 4
2014225257.tif 000018
Figure 5A
2014225257.tif 000019
Figure 5B
2014225257.tif 000020
Figure 6A
2014225257.tif 000021
Figure 6B
2014225257.tif 000022