(57)【特許請求の範囲】
【請求項１】
スカイライン行列の三角分解により、前記スカイライン行列を係数行列とする連立一次方程式の数値解を求める計算装置において、
有効な要素のみが格納された一次元の配列データで表される前記係数行列と、前記係数行列を構成する各々の列の先頭に位置している前記配列データのアドレスを保持する列先頭アドレステーブルとに基づき、前記係数行列中の列における該有効な要素の上端が連続的に揃っているスカイライン列群を識別し、該連続的に揃っているスカイライン列群のそれぞれの前記係数行列内における位置情報をスカイライン列情報テーブルに格納する手段と、
前記生成したスカイライン列情報テーブルを参照して任意数の列からなるスカイライン列群を順次選択し、そのスカイライン列群を対象として三角分解における消去処理を行う手段とを備えたことを特徴とする計算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は計算装置に係り、特に、有限要素法に基づく構造解析から得られるスカイライン行列を三角分解して、そのスカイライン行列を係数行列とする連立一次方程式の数値解を求める計算装置に関する。
【０００２】
【従来の技術】
従来より、連立一次方程式の数値解を求めるためにその係数行列を高速に三角分解する方法として、スカイライン法の改訂コレスキー分解を利用する方法が知られている（小国  力・編著「行列計算ソフトウェア−ＷＳ，スーパーコン，並列計算機」丸善）。これは、一行一列内積計算処理を基本とする方法である。また、スカイライン行列をＬ×Ｌ（Ｌ＝２，３，…）のセルに分割した後、各々のセルごとに分解を行うパラレルスカイライン法や、スカイライン行列をいくつかの列ごとにブロック化して外部記憶装置に記憶させ、計算に必要なブロックのみを適宜コアメモリに読み込んで分解を行うブロックスカイライン法なども知られている。
【０００３】
一方、本出願人は、与えられたスカイライン行列を、各列の上端がＬ個（Ｌ＝２，３，…，６）ずつ揃った一群のスカイライン行列と、それ以外の一般的なスカイライン行列とに場合分けし、各々の場合ごとに分解を行う「連立一次方程式に関する計算装置」を提案している。
【０００４】
【発明が解決しようとする課題】
浮動小数点レジスタが数多く装備されている計算機装置によってスカイライン行列を三角分解して、そのスカイライン行列を係数行列とする連立一次方程式の数値解を求めようとする場合、浮動小数点レジスタを活用するためには上述したパラレルスカイライン法が有効である。このとき、各列の上端がＬ個（Ｌ＝２，３，…，６）ずつ揃った一群のスカイライン行列では、無駄なゼロ要素の計算を行う必要が発生しない。しかしながら、それ以外の一般的なスカイライン行列では、無駄なゼロ要素の計算を行う必要が発生してしまう。
【０００５】
図７は、無駄なゼロ要素の計算を行う必要が発生するスカイライン行列の一例を概念的に示す図である。同図中、白抜きの矩形部で示す要素は、スカイライン行列におけるゼロ以外の有効な数値要素である。そして、白抜きの矩形部以外のすべての要素（ハッチングした部分を含む）は、上述したスカイライン行列における無駄なゼロ要素である。図７のスカイライン行列において、例えば一度に消去する列幅Ｌ＝４とすると、列の上端がＬ＝４個ずつ揃った一群のスカイライン行列（図７中に符号７１および７５で示した列）については、無駄なゼロ要素の計算を行う必要が発生しない。しかしながら、それ以外の一般的なスカイライン行列（図７中に符号７２〜７４，７６で示した列）については、ハッチングした部分で無駄なゼロ要素の計算を行う必要が発生してしまう。
【０００６】
以上のように、上記従来技術におけるパラレルスカイライン法を用いた行列の三角分解では、無駄なゼロ要素の計算の発生によって十分に浮動小数点レジスタが活用されず、連立一次方程式の数値解を必ずしも効率的に求められるとは限らないという問題点があった。
【０００７】
したがって本発明の目的は、上記の問題点を解決して、パラレルスカイライン法を用いた行列の三角分解において、各列の上端が揃っていない一般的なスカイライン行列が多い場合でも無駄なゼロ要素の計算の発生を抑制し、常に連立一次方程式の数値解を効率的に求めることのできる計算装置を提供することにある。
【０００８】
【課題を解決するための手段】
上記の目的を達成するため、本発明の計算装置は、スカイライン行列の三角分解により、そのスカイライン行列を係数行列とする連立一次方程式の数値解を求める計算装置において、有効な要素のみが格納された一次元の配列データで表される前記係数行列と、前記係数行列を構成する各々の列の先頭に位置している前記配列データのアドレスを保持する列先頭アドレステーブルとに基づき、前記係数行列中で列の上端が連続的に揃っているスカイライン列群をそれぞれ識別するためのスカイライン列情報テーブルを生成し、前記スカイライン列情報テーブルに応じて任意数の列からなるスカイライン列群を順次選択し、そのスカイライン列群を対象として処理を行うようにしたものである。
【０００９】
上記構成としたことにより、本発明の計算装置では、各列の上端が揃っていない一般的なスカイライン行列が多い場合でも無駄なゼロ要素の計算の発生を抑制し、常に連立一次方程式の数値解を効率的に求めることができる。
【００１０】
【発明の実施の形態】
以下、本発明の計算装置の実施の一形態を図面を用いて詳細に説明する。
【００１１】
図１は、本発明の計算装置によって行われるスカイライン行列の三角分解処理の全体的な流れを示すフローチャートである。図２は、図１の処理対象となる一次元の配列データで表されたスカイライン行列の一例を具体的に示す図であり、図２（ａ）は次元数25（25行25列）のスカイライン行列Ａを、図２（ｂ）はスカイライン行列Ａを構成する各々の列の先頭（スカイライン行列Ａの対角位置）における配列データのアドレスを保持する列先頭アドレステーブルＮＰを、それぞれ示す。図３は、図１の三角分解処理から呼び出されるスカイライン列情報テーブル生成ルーチンによる処理の流れを示すフローチャートである。図４は、図２のスカイライン行列に基づいて生成されるスカイライン列情報テーブルの一例を示す図である。
【００１２】
図２（ａ）のスカイライン行列Ａ２０１において、細かな方形で示した要素は計算時に有効な要素（≠０）であり、その他の要素はすべて無効な要素（＝０）である。そこで、有効な要素の各々について、スカイライン行列中の位置アドレスを１次元配列ＮＰに、その具体的な数値データを１次元配列Ａに、それぞれ格納しておく。すなわち、スカイライン行列Ａ２０１における第Ｋ列の対角位置は《ＮＰ（Ｋ）》によって表され（２０２）、対角位置の要素の具体的な数値データは《Ａ（ＮＰ（Ｋ））》によって表されるものとする。したがって、スカイライン行列Ａ２０１における第Ｋ列の上端の位置は、《ＮＰ（Ｋ＋１）−１》によって表される（２０３）。図２（ｂ）に示した列先頭アドレステーブルＮＰ（２０４）は図２（ａ）のスカイライン行列Ａ２０１に対応するものである。列先頭アドレステーブルＮＰの大きさすなわち次元数は、スカイライン行列Ａの次元数Ｎ（＝25）より少なくとも１だけ大きく、《ＮＰ（Ｎ＋１）＝ＮＰ（26）》には、１次元配列Ａに格納されている有効なすべての要素数＋１の値（=187）を格納しておく。
【００１３】
図１に示したスカイライン行列の三角分解処理の冒頭において、上述した列先頭アドレステーブルＮＰを検索して、スカイライン行列Ａ中で列の上端が連続的に揃っているスカイライン列群を抽出し、得られたスカイライン列群の先頭に位置する列を示す番号を一次元配列のスカイライン列情報テーブルＩＴＢＬに格納する（ステップ１０１）。以下、ステップ１０１に相当するスカイライン列情報テーブル生成ルーチンによる処理について、図３のフローチャートを用いて説明する。
【００１４】
図３において、最初に、ＩＴＢＬ用カウンタＫに対して初期値（＝１）を設定する（ステップ３０１）。そして、スカイライン行列Ａの最初に位置する第１列について、ＩＴＢＬ（１）の内容（＝１）とスカイライン列の上端の行番号ＫＲ（＝１）とを設定する（ステップ３０２，３０３）。そして、スカイライン行列Ａ全体についてのループ制御変数である列カウンタＪＪに対して初期値（＝１）を設定して（ステップ３０４）、ステップ３０５以降のループを開始する。ステップ３０５では、列カウンタＪＪの値とスカイライン行列Ａの次元数Ｎ（＝25）とを比較し、列カウンタＪＪが次元数Ｎより大きい場合にはスカイライン列情報テーブル生成ルーチンを終了して図１の処理に戻り、大きくない場合には次の処理を続ける。すなわち、列の上端が揃っているスカイライン列群についてのループ制御変数であるループカウンタＪに対して初期値（＝１）を設定した後（ステップ３０６）、ステップ３０７〜３１１の列群判定ループを開始する。ステップ３０７では、第ＪＪ列のスカイライン列の上端のスカイライン行列Ａにおける行番号ＪＲを設定する。そしてステップ３０８で、前述した行番号ＫＲの値と上記行番号ＪＲの値とを比較し、等しくない場合すなわちスカイライン列の上端が揃っていない場合には列群判定ループから抜けてステップ３１２へジャンプする。列群判定ループを続行する場合には、ステップ３０９で列カウンタＪＪの値をインクリメントさせるとともに、ステップ３１０でループカウンタＪの値をインクリメントさせる。ステップ３１１では、ループカウンタＪの値と定数ＪＭＡＸの値とを比較し、Ｊの値がＪＭＡＸの値を越えていた場合には列群判定ループから抜ける。ここで、定数ＪＭＡＸの値は計算装置ごとに決められており、後述するスカイライン列の消去を行う際に最適なスカイライン列群の列幅である。
【００１５】
列群判定ループから抜けると、スカイライン列情報テーブルＩＴＢＬのカウンタＫをインクリメントさせて（ステップ３１２）、上述した列群判定ループにおける次のスカイライン列群の先頭列番号をＩＴＢＬ（Ｋ）に設定する（ステップ３１３）。そして、第ＪＪ列における新たなスカイライン列の上端の行番号ＫＲを設定する（ステップ３１４）。以上の処理を、列カウンタＪＪの値がスカイライン行列Ａの次元数Ｎ（＝25）を越えるまで繰り返し行う。
【００１６】
図４中の４０１は、上述した図３の処理によって図２のスカイライン行列Ａから生成されたスカイライン列情報テーブルＩＴＢＬの具体例である。ＩＴＢＬの最後には次元数Ｎ＋１（＝26）が必ず設定されるので、第Ｋ番目のスカイライン列群の列数は、《ＩＴＢＬ（Ｋ＋１）−ＩＴＢＬ（Ｋ）》によって表される。なお、上述した実施の形態では定数ＪＭＡＸの値を４としているので、図中に４０２で示す第16〜20列における５列のスカイライン列については、第16〜19列に位置する４列のスカイライン列群と第20列に位置する１列のスカイライン列群とに分割されて、それぞれが図１の三角分解処理の対象となる。
【００１７】
図１において、ステップ１０１におけるスカイライン列情報テーブルＩＴＢＬの生成が完了すると、更新対象のスカイライン列群を指定するループ制御変数Ｉに対して初期値（＝１）を設定して（ステップ１０２）、ステップ１０３以降の上位ループを開始する。そして、更新対象のスカイライン列群を構成しているスカイライン列のうち、先頭に位置するスカイライン列のスカイライン行列Ａにおける列番号を作業変数ＩＢＥに設定する（ステップ１０３）。続くステップ１０４で、ＩＢＥの値とスカイライン行列Ａの次元数Ｎ（＝25）とを比較し、ＩＢＥの値が次元数Ｎより大きい場合には上位ループから抜けてスカイライン行列の三角分解処理を終了し、大きくない場合には次の処理を続ける。すなわち、ループ制御変数Ｉで指定される更新対象のスカイライン列群を構成しているスカイライン列の列数を作業変数ＩＢＥＬに設定し（ステップ１０５）、参照対象のスカイライン列群を指定するループ制御変数Ｊに対して初期値（＝１）を設定して（ステップ１０６）、ステップ１０７〜１１１の下位ループを開始する。そして、参照対象のスカイライン列群を構成しているスカイライン列のうち、先頭に位置するスカイライン列のスカイライン行列Ａにおける列番号を作業変数ＩＢＳに設定する（ステップ１０７）。ステップ１０８では、ＩＢＳの値と上述したＩＢＥの値とを比較し、等しい場合には下位ループから抜けてステップ１１２にジャンプする。また、等しくない場合には、ループ制御変数Ｊで指定される参照対象のスカイライン列群を構成しているスカイライン列の列数を作業変数ＩＢＳＬに設定し（ステップ１０９）、参照対象のスカイライン列群および更新対象のスカイライン列群中から更新対象のスカイライン列群を消去（ステップ１１０）した後、ループ制御変数Ｊをインクリメントさせて（ステップ１１１）、下位ループ冒頭のステップ１０７へ戻る。ステップ１１２では、更新対象のスカイライン列群自身を消去した後、ループ制御変数Ｉをインクリメントさせて（ステップ１１３）上位ループ冒頭のステップ１０３へ戻る。上述中、ステップ１１０および１１２で行われる“スカイライン列群を消去する”処理については、従来から広く知られているので、詳細な説明を省略する。
【００１８】
図５および図６は、図１および図３の三角分解処理中で行われる“スカイライン列群を消去する”処理について概念的に説明するための図である。以下、図２に示したスカイライン行列中から特定のスカイライン列群を消去する場合について、図１，図２，図５および図６を用いて説明する。
【００１９】
図５において、図２（ａ）に示したスカイライン行列は、前述したスカイライン列情報テーブル生成ルーチンによって、図５中に符号５１，５２，……，６１で記した列の上端が連続的に揃っているスカイライン列群にそれぞれ分割され、その分割に関する情報は図４に示したスカイライン列情報テーブルＩＴＢＬに設定される。そして図６（１）〜図６（５）は、図１中でループ制御変数Ｉ＝５の条件下で、上述した下位ループを含むステップ１０５〜１１２によるスカイライン列群の消去に際して参照または更新される（ゼロでない）有効な要素をハッチングで表す。すなわち、ループ制御変数Ｊ＝１のときには、スカイライン列群５１中の図６（１）に示す要素５１ａ（スカイライン列群５１の一部）が参照対象として選択され、これを利用してスカイライン列群５５中の図６（１）に示す要素５５ａ（スカイライン列群５５の一部）が消去される（図１中のステップ１１０）。このときの要素５１ａは、スカイライン行列中における更新対象のスカイライン列群５５の上端の行番号の値が２であることから、スカイライン列群５１に含まれる行番号の値が２以上のものが選択される。そして、ループ制御変数Ｊ＝２のときには、スカイライン列群５２中の図６（２）に示す要素５２ａ（スカイライン列群５２の全部）が参照対象として選択され、これを利用してスカイライン列群５５中の図６（２）に示す要素５５ｂ（スカイライン列群５５の一部）が消去される。
【００２０】
同様に、図６（３）におけるループ制御変数Ｊ＝３のときにはスカイライン列群５３中の要素５３ａ（スカイライン列群５３の全部）を参照対象としてスカイライン列群５５中の要素５５ｃが消去され、図６（４）におけるループ制御変数Ｊ＝４のときにはスカイライン列群５４中の要素５４ａ（スカイライン列群５４の全部）を参照対象としてスカイライン列群５５中の要素５５ｄが消去される。最後に、ループ制御変数Ｊ＝５となると、ステップ１０８の判定によってステップ１１２にジャンプし、スカイライン列群５５中の要素５５ｅ自身を参照対象として要素５５ｅ自身が消去され、スカイライン列群５５を構成するすべての要素の消去が完了する。
【００２１】
【発明の効果】
以上詳しく説明したように、本発明の計算装置によれば、各列の上端が揃っていない一般的なスカイライン行列が多い場合でも、パラレルスカイライン法の適用に際して、上端が揃っている一部のスカイライン列群を相互に消去しておくことで無駄なゼロ要素の計算の発生を抑制し、常に連立一次方程式の数値解を効率的に求めることができるという効果が得られる。このとき、浮動小数点レジスタを数多く装備する計算装置であれば、複数のスカイライン列群を一括して消去することにより、従来の一行一列内積型計算にくらべて必要なＣＰＵ時間を１／２〜１／３程度にまで短縮することができるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の計算装置によって行われるスカイライン行列の三角分解処理の全体的な流れを示すフローチャートである。
【図２】図１の処理対象となる一次元の配列データで表されたスカイライン行列の一例を具体的に示す図である。
【図３】図１の三角分解処理から呼び出されるスカイライン列情報テーブル生成ルーチンによる処理の流れを示すフローチャートである。
【図４】図２のスカイライン行列に基づいて生成されるスカイライン列情報テーブルの一例を示す図である。
【図５】図１および図３の三角分解処理中で行われる“スカイライン列群を消去する”処理について概念的に説明するための図（その１）である。
【図６】図１および図３の三角分解処理中で行われる“スカイライン列群を消去する”処理について概念的に説明するための図（その２）である。
【図７】無駄なゼロ要素の計算を行う必要が発生するスカイライン行列の一例を概念的に示す図である。
【符号の説明】
２０１  スカイライン行列
２０２  スカイライン行列における第Ｋ列の対角位置
２０３  スカイライン行列における第Ｋ列の上端の位置
２０４  列先頭アドレステーブル
４０１  スカイライン列情報テーブル
５１，５２，……，６１  列の上端が連続的に揃っているスカイライン列群
【図１】
0003694939.tif 000002
【図２】
0003694939.tif 000003
【図３】
0003694939.tif 000004
【図４】
0003694939.tif 000005
【図５】
0003694939.tif 000006
【図６】
0003694939.tif 000007
【図７】
0003694939.tif 000008