(57)【特許請求の範囲】
【請求項１】
行列を格納する記憶装置を備え、係数行列が疎行列である連立一次方程式の数値解を計算する連立一次方程式求解装置における連立一次方程式求解方法において、
ゼロ要素を含む疎行列の係数行列要素及び右辺ベクトル要素の全要素を配列として前記記憶装置に格納し、
前記記憶装置に格納された配列を参照して該配列中の各列における終端非ゼロ要素の行番号と各行の終端非ゼロ要素の列番号とを表す非ゼロ構造特定インデクステーブルを作成して前記記憶装置に格納し、
前記記憶装置に格納された非ゼロ構造特定インデクステーブルを参照して該非ゼロ構造特定インデクステーブルで示される範囲内の要素に対して三角分解処理を実行し、
前記三角分解処理の実行された係数行列要素と前記配列に格納した右辺ベクトル要素に対して前進・後退代入処理を実行して解を算出し、該算出した解を前記記憶装置に格納することを特徴とする連立一次方程式求解方法。
【請求項２】
前記記憶装置に格納された配列における各列の終端非ゼロ要素の行番号が前列の終端非ゼロ要素の行番号よりも小さい場合に、その列の終端非ゼロ要素の行番号を前列の終端非ゼロ要素の行番号と等しい値に更新し、前記各行の終端非ゼロ要素の列番号が前行の終端非ゼロ要素の列番号よりも小さい場合に、その行の終端非ゼロ要素の列番号を前行の終端非ゼロ要素の列番号と等しい値に更新することを特徴とする請求項１に記載された連立一次方程式求解方法。
【請求項３】
前記非ゼロ構造特定インデクステーブルに終端非ゼロ要素の行番号及び列番号を更新するかどうかを示す指定要求の入力に応じて、該指定要求で更新を行わない指定が入力された場合に、前記記憶装置に格納された非ゼロ構造特定インデクステーブルに当該係数行列の最大の行番号及び列番号を設定することを特徴とする請求項１または請求項２のいずれかに記載された連立一次方程式求解方法。
【請求項４】
行列を格納する記憶装置を備え、係数行列が疎行列である連立一次方程式の数値解を計算する連立一次方程式求解装置において、
ゼロ要素を含む疎行列の係数行列要素及び右辺ベクトル要素の全要素を配列として前記記憶装置に格納する係数行列入力処理部と、前記記憶装置に格納された配列を参照して該配列中の各列における終端非ゼロ要素の行番号と各行の終端非ゼロ要素の列番号とを表す非ゼロ構造特定インデクステーブルを作成して前記記憶装置に格納する非ゼロ要素構造計算処理部と、
前記記憶装置に格納された非ゼロ構造特定インデクステーブルを参照して該非ゼロ構造特定インデクステーブルで示される範囲内の要素に対して三角分解処理を実行する三角分解処理部と、前記三角分解処理の実行された係数行列要素と前記配列に格納した右辺ベクトル要素に対して前進・後退代入処理を実行して解を算出し、該算出した解を前記記憶装置に格納する前進・後退代入処理部とを備えることを特徴とする連立一次方程式求解装置。
【請求項５】
行列を格納する記憶装置を備え、係数行列が疎行列である連立一次方程式の数値解を計算する連立一次方程式求解装置としてコンピュータを機能させる為のプログラムを記録したコンピュータ読み取り可能な記録媒体において、
ゼロ要素を含む疎行列の係数行列要素及び右辺ベクトル要素の全要素を配列として前記記憶装置に格納する係数行列入力処理部と、前記記憶装置に格納された配列を参照して該配列中の各列における終端非ゼロ要素の行番号と各行の終端非ゼロ要素の列番号とを表す非ゼロ構造特定インデクステーブルを作成して前記記憶装置に格納する非ゼロ要素構造計算処理部と、
前記記憶装置に格納された非ゼロ構造特定インデクステーブルを参照して該非ゼロ構造特定インデクステーブルで示される範囲内の要素に対して三角分解処理を実行する三角分解処理部と、前記三角分解処理の実行された係数行列要素と前記配列に格納した右辺ベクトル要素に対して前進・後退代入処理を実行して解を算出し、該算出した解を前記記憶装置に格納する前進・後退代入処理部としてコンピュータを機能させる為のプログラムを記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は連立一次方程式の数値解を計算する連立一次方程式求解装置に関し、特に係数行列が疎行列である連立一次方程式の数値解を計算する連立一次方程式求解装置に適用して有効な技術に関するものである。
【０００２】
【従来の技術】
従来、密行列を係数行列とする連立一次方程式を求解する解法として、小国 力編著「行列計算ソフトウェアーＷＳ、スーパーコン、並列計算機」（丸善）で論じられている様に、ガウス法やクラウト法等多くの解法が存在している。係数行列が疎行列と既に分かっている場合、係数行列の非ゼロ要素の構造に着目したデータ格納方法及びそのデータ格納方法に向いた、疎行列を係数行列とする連立一次方程式を求解する解法として、スカイライン法を始めとし多くの解法が存在している。データ格納に要するリソース量及びゼロ要素の無駄な計算を削減する為に、係数行列の非ゼロ要素の構造によって最適な解法を選択することが重要である。この選択には経験的、専門的知識を要している。
【０００３】
【発明が解決しようとする課題】
前記従来の連立一次方程式の数値解法において、疎行列を係数行列とする連立一次方程式を求解する場合には、最適な解法の選択に経験的、専門的知識を要していた為、経験的、専門的知識を有していない利用者が疎行列を係数行列とする連立一次方程式を解くのは困難なことが多いという問題があった。
【０００４】
また、従来の連立一次方程式の数値解法において、解く連立一次方程式の係数行列が疎行列である場合に密行列向けの解法を利用するのは、データを格納する為に必要なリソース量及び計算量共に疎行列向けの解法を使用する場合と比較し、多くの無駄を生じていた。近年、分散メモリ型並列計算機等に代表される大容量メモリを搭載した装置では、上述のゼロ要素格納の無駄は、深刻な問題とならなくなってきている。
【０００５】
本発明の目的は上記問題を解決し、連立一次方程式の数値解を計算する情報処理装置の操作性の向上を図り、求解に必要な計算量を削減することが可能な技術を提供することにある。
【０００６】
【課題を解決するための手段】
本発明は、係数行列が疎行列である連立一次方程式の数値解を計算する連立一次方程式求解装置において、ゼロ要素を含む疎行列の全要素を密行列と同様に配列に格納した後、それらの非ゼロ要素の範囲内について三角分解処理及び前進・後退代入処理を行って解を求めるものである。
【０００７】
本発明では、ゼロ要素を含む疎行列の係数行列要素及び右辺ベクトル要素の全要素を、密行列の場合と同様にして配列に格納する。
【０００８】
次に前記格納した配列中の値を調べ、前記配列中の各列の終端非ゼロ要素の行番号と各行の終端非ゼロ要素の列番号とを表す非ゼロ構造特定インデクステーブルを作成する。
【０００９】
そして前記配列中の係数行列要素の内、前記作成された非ゼロ構造特定インデクステーブルで示される非ゼロ要素の範囲内について三角分解処理を行い、前記三角分解処理の行われた係数行列要素と前記配列に格納した右辺ベクトル要素に対して前進・後退代入処理を行って解を求める。
【００１０】
前記の様に本発明によれば、ゼロ要素格納の無駄を許容し、係数行列の非ゼロ要素の構造に依存せずに、いずれの係数行列も密行列と同様のデータ格納方法を採用することで操作性の向上を図っており、前記作成された非ゼロ構造特定インデクステーブルで示される範囲内の要素についてのみ計算を行うので、計算量を削減した連立一次方程式の求解を行うことが可能である。
【００１１】
以上の様に本発明の連立一次方程式求解装置によれば、ゼロ要素を含む疎行列の全要素を密行列と同様に配列に格納した後、それらの非ゼロ要素の範囲内について三角分解処理及び前進・後退代入処理を行って解を求めるので、連立一次方程式の数値解を計算する情報処理装置の操作性の向上を図り、求解に必要な計算量を削減することが可能である。
【００１２】
【発明の実施の形態】
以下に係数行列が疎行列である連立一次方程式の数値解を計算する一実施形態の連立一次方程式求解装置について説明する。
【００１３】
図１は本実施形態の連立一次方程式求解装置１００の概略構成を示す図である。図１に示す様に本実施形態の連立一次方程式求解装置１００は、ＣＰＵ１０１と、メモリ１０２と、磁気ディスク装置１０３と、入力装置１０４と、出力装置１０５と、ＣＤ−ＲＯＭ装置１０６と、非ゼロ構造特定インデクステーブル１０７とを有している。
【００１４】
ＣＰＵ１０１は、連立一次方程式求解装置１００全体の動作を制御する装置である。メモリ１０２は、連立一次方程式求解装置１００全体の動作を制御する際にその為の各種処理プログラムやデータをロードする記憶装置である。
【００１５】
磁気ディスク装置１０３は、前記各種処理プログラムやデータを格納しておく記憶装置である。入力装置１０４は、疎行列の連立一次方程式の数値解を計算する為の各種入力を行う装置である。出力装置１０５は、疎行列の連立一次方程式の数値解の計算に伴う各種出力を行う装置である。
【００１６】
ＣＤ−ＲＯＭ装置１０６は、前記各種処理プログラムを記録したＣＤ−ＲＯＭの内容を読み出す装置である。非ゼロ構造特定インデクステーブル１０７は、配列中の係数行列要素の内で指定された列の終端非ゼロ要素の行番号と指定された行の終端非ゼロ要素の列番号とを格納するテーブルである。
【００１７】
また連立一次方程式求解装置１００は、係数行列入力処理部１１０と、非ゼロ要素構造計算処理部１１１と、三角分解処理部１１２と、前進・後退代入処理部１１３とを有している。
【００１８】
係数行列入力処理部１１０は、ゼロ要素を含む疎行列の係数行列要素及び右辺ベクトル要素の全要素を、その非ゼロ要素の構造に依存せず、密行列と同様にして配列に格納する処理部である。非ゼロ要素構造計算処理部１１１は、前記配列中の各列の終端非ゼロ要素の行番号と各行の終端非ゼロ要素の列番号とを非ゼロ構造特定インデクステーブル１０７に格納する処理部である。
【００１９】
三角分解処理部１１２は、前記作成された非ゼロ構造特定インデクステーブル１０７で示される範囲内の要素に対して三角分解処理を行い、解の精度を向上する為の行交換による部分軸交換によって軸の交換が発生した場合には、非ゼロ構造特定インデクステーブル１０７の内容を更新する処理部である。前進・後退代入処理部１１３は、前記三角分解処理の行われた係数行列要素と前記配列に格納した右辺ベクトル要素に対して前進・後退代入処理を行って解を求める処理部である。
【００２０】
連立一次方程式求解装置１００を係数行列入力処理部１１０、非ゼロ要素構造計算処理部１１１、三角分解処理部１１２及び前進・後退代入処理部１１３として機能させる為のプログラムは、ＣＤ−ＲＯＭ等の記録媒体に記録され磁気ディスク等に格納された後、メモリにロードされて実行されるものとする。なお前記プログラムを記録する記録媒体はＣＤ−ＲＯＭ以外の他の記録媒体でも良い。
【００２１】
本実施形態の連立一次方程式求解装置１００の係数行列入力処理部１１０は、Ａｘ＝Ｂで表される疎行列の係数行列要素Ａ及び右辺ベクトル要素Ｂの値を入力し、ゼロ要素を含む疎行列の係数行列要素Ａの全要素を、その非ゼロ要素の構造に依存せず、密行列と同様にして連立一次方程式求解装置１００のメモリ上の２次元配列Ａに格納し、右辺ベクトルの要素を１次元配列Ｂに格納する。
【００２２】
連立一次方程式求解装置１００の非ゼロ要素構造計算処理部１１１は、前記配列に格納された係数行列要素Ａの値を参照し、前記配列中の係数行列要素Ａの内、指定された列の終端非ゼロ要素の行番号と指定された行の終端非ゼロ要素の列番号とを表す非ゼロ構造特定インデクステーブル１０７を作成する。
【００２３】
図２は本実施形態の非ゼロ構造特定インデクステーブル１０７の形式例を示す図である。図２では、非ゼロ要素構造計算処理部１１１で作成される非ゼロ構造特定インデクステーブル１０７の形式例を表している。
【００２４】
インデクスＩＭＴＢ２０１は第Ｊ列の終端非ゼロ要素の行番号を表すインデクスであり、インデクスＪＭＴＢ２０２は第Ｉ行の終端非ゼロ要素の列番号を表すインデクスである。ここで、Ｉ、Ｊは１から係数行列の次元数Ｎ迄の範囲をとる。第Ｊ列の終端非ゼロ要素とは、第Ｊ列において行番号が最も大きい非ゼロ要素を指しており、同様に、第Ｉ行の終端非ゼロ要素とは、第Ｉ行において列番号が最も大きい非ゼロ要素を指している。インデクスＩＭＴＢ２０１及びインデクスＪＭＴＢ２０２で構成されるテーブルを非ゼロ構造特定インデクステーブル１０７とする。
【００２５】
図３は本実施形態のインデクスＩＭＴＢ２０１及びインデクスＪＭＴＢ２０２の一例を示す図である。図３では、次元数８の疎行列３０１におけるインデクスＩＭＴＢ２０１及びインデクスＪＭＴＢ２０２を表している。
【００２６】
図３において印「●」で示された非ゼロ要素３０２は、疎行列３０１の係数行列要素の内でその値が非ゼロである要素を示し、破線で表した計算範囲３０３は、インデクスＩＭＴＢ２０１及びインデクスＪＭＴＢ２０２の値で囲まれた要素の範囲を示しており、印「○」は、計算範囲３０３中のゼロ要素を表している。
【００２７】
終端非ゼロ要素行番号例３０４は、インデクスＩＭＴＢ（３）に設定されている数値例を示しており、第３列の終端非ゼロ要素の行番号が「６」であるので、ＩＭＴＢ（３）＝６となる。終端非ゼロ要素列番号例３０５は、インデクスＪＭＴＢ（４）に設定されている数値例を示している。第４行の終端非ゼロ要素の列番号は「６」であるが、本実施形態では、軸交換による非ゼロ構造の変化に対してもインデクスの変更が最小で済む様に、ＩＭＴＢ（Ｊ）≧ＩＭＴＢ（Ｊ−１）、ＪＭＴＢ（Ｉ）≧ＪＭＴＢ（Ｉ−１）（Ｉ、Ｊ＝２、…、Ｎ）となる様に設定している為、ＪＭＴＢ（４）＝７となる。
【００２８】
図４は本実施形態の非ゼロ要素構造計算処理の処理手順を示すフローチャートである。まず非ゼロ要素構造計算処理部１１１は、非ゼロ要素の構造を計算するかどうかを示す、外部から指定可能な変数ＩＳＷの値を入力し、ＩＳＷの値が「１」であるかどうかを判定する（ステップ４０１）。ここでＩＳＷが「１」ではない場合には、係数行列の全要素が非ゼロであり、非ゼロ要素の構造を計算する必要が無いことを表しているものとする。このＩＳＷを設けることで、係数行列の全要素が非ゼロと分かっている場合、ステップ４０３〜ステップ４１５を省略することが可能である。
【００２９】
ステップ４０１でＩＳＷの値を判定した結果、非ゼロ要素の構造を計算しない場合、すなわちＩＳＷが「１」でない場合にはステップ４０２へ進み、インデクスＩＭＴＢ、ＪＭＴＢの値を全てＮに設定する。
【００３０】
またステップ４０１でＩＳＷが「１」であり、非ゼロ要素の構造を計算する場合には、以降に示すステップ４０３〜ステップ４１５を実行する。すなわち、まずステップ４０３では、インデクスＩＭＴＢ、ＪＭＴＢの値を全て「０」に初期化する。
【００３１】
次にステップ４０４では、インデクスＩＭＴＢを計算する。ステップ４０４は、Ｊを１からＮ迄１づつ増加させながら繰り返す処理（ステップ４０５）の内側に、ＩをＮから１迄１づつ減少させながら繰り返す処理（ステップ４０６）があり、更に内側では、行番号Ｉ、列番号Ｊで与えられる係数行列の要素Ａ（Ｉ、Ｊ）が「０」でないかどうかを判定し（ステップ４０７）、「０」でないならばＩＭＴＢ（Ｊ）にＩを設定してステップ４０６の繰り返し処理を終了する（ステップ４０８）。
【００３２】
ステップ４０９では、インデクスＪＭＴＢを計算する。ステップ４０９は、Ｉを１からＮ迄１づつ増加させながら繰り返す処理（ステップ４１０）の内側に、ＪをＮから１迄１づつ減少させながら繰り返す処理（ステップ４１１）があり、更に内側では、行番号Ｉ、列番号Ｊで与えられる係数行列の要素Ａ（Ｉ、Ｊ）が「０」でないかどうかを判定し（ステップ４１２）、「０」でないならばＪＭＴＢ（Ｉ）にＪを設定してステップ４１１の繰り返し処理を終了する（ステップ４１３）。
【００３３】
次にステップ４１４では、インデクスＩＭＴＢまたはＪＭＴＢ中に値が「０」であるものが存在するかどうかを判定し、「０」が存在している場合には、ゼロ要素のみで構成される行または列が存在することから、与えられた係数行列は特異行列であると判定して処理を終了する（ステップ４１６）。
【００３４】
インデクスＩＭＴＢ及びＪＭＴＢ中に値「０」が存在していない場合、軸交換による、非ゼロ構造の変化に対してもインデクスの変更が最小で済む様に、ＩＭＴＢ（Ｊ）≧ＩＭＴＢ（Ｊ−１）、ＪＭＴＢ（Ｉ）≧ＪＭＴＢ（Ｉ−１）（Ｉ、Ｊ＝２、…、Ｎ）となる様にインデクスＩＭＴＢ及びＪＭＴＢ中の値を設定する（ステップ４１５）。
【００３５】
なお、係数行列の要素が全て非ゼロ要素である密行列でステップ４０３〜ステップ４１５の処理を行った場合には、インデクスＩＭＴＢ及びＪＭＴＢの値は全てＮに設定される。
【００３６】
図５は従来の三角分解処理の処理手順を示すフローチャートである。図５では、非ゼロ構造特定インデクステーブル１０７を使用しないで、密行列に対するガウス法を行う三角分解処理の処理手順を表している。
【００３７】
この三角分解処理では、ステップ５０１でＫを１からＮ迄１づつ増加させながらステップ５０２〜ステップ５０７の処理を繰り返す。
【００３８】
ステップ５０２では、軸列Ａ（Ｉ、Ｋ）（Ｉ＝Ｋ＋１、…、Ｎ）の値を参照し、その絶対値の値が最大である要素のＩの値を変数ＫＰＩＶに代入する。次にＫＰＩＶとＫの値を比較し（ステップ５０３）、同じ値でないならば、ＫＰＩＶ行目のＡ（ＫＰＩＶ、Ｊ）（Ｊ＝Ｋ、…、Ｎ）とＫ行目のＡ（Ｋ、Ｊ）（Ｊ＝Ｋ、…、Ｎ）を交換する（ステップ５０４）。ステップ５０５では、第Ｋ段で選択した軸行ＫＰＩＶの値を配列ＩＰ（Ｋ）に格納して保持する。この情報は前進・後退代入処理で利用される。
【００３９】
次にステップ５０６では、軸列のＡ（Ｉ、Ｋ）（Ｉ＝Ｋ＋１、…、Ｎ）を軸要素Ａ（Ｋ、Ｋ）で消去、すなわち図５のステップ５０６に示した数式の様にＡ（Ｉ、Ｋ）にＡ（Ｉ、Ｋ）／Ａ（Ｋ、Ｋ）を代入してＡ（Ｉ、Ｋ）の値を更新する。この様に本実施形態において、用語「消去」は「更新」を表すものとする。ステップ５０７では、図５のステップ５０７に示した数式の様に軸列Ａ（Ｉ、Ｋ）（Ｉ＝Ｋ＋１、…、Ｎ）及び軸行Ａ（Ｋ、Ｊ）（Ｊ＝Ｋ＋１、…、Ｎ）からＡ（Ｉ、Ｊ）を消去する（ステップ５０７）。
【００４０】
図６は本実施形態の三角分解処理の処理手順を示すフローチャートである。図６では、図５の処理とは異なり、非ゼロ構造特定インデクステーブル１０７を使用し、疎行列の行列要素に対して密行列と同様にガウス法を適用した三角分解処理の処理手順を表している。
【００４１】
本実施形態の三角分解処理部１１２では、ステップ６０１でＫを１からＮ迄１づつ増加させながらステップ６０２〜ステップ６０８の処理を繰り返す。
【００４２】
ステップ６０２では、軸列Ａ（Ｉ、Ｋ）（Ｉ＝Ｋ＋１、…、ＩＭＴＢ（Ｋ））の値を参照し、その絶対値の値が最大である要素のＩの値を変数ＫＰＩＶに代入する。このステップ６０２の処理では、ステップ５０２と比較して選択範囲がＮからＩＭＴＢ（Ｋ）迄に減少している。
【００４３】
次にＫＰＩＶとＫの値を比較し（ステップ６０３）、同じ値でないならば、ＫＰＩＶ行目のＡ（ＫＰＩＶ、Ｊ）（Ｊ＝Ｋ、…、ＪＭＴＢ（ＫＰＩＶ））とＫ行目のＡ（Ｋ、Ｊ）（Ｊ＝Ｋ、…、ＪＭＴＢ（ＫＰＩＶ））を交換する（ステップ６０４）。このステップ６０４の処理では、ステップ５０４と比較して選択範囲がＮからＪＭＴＢ（ＫＰＩＶ）に減少している。
【００４４】
ステップ６０５では、軸交換に伴いインデクスＪＭＴＢの値を更新する。また、ＪＭＴＢ（Ｉ）≧ＪＭＴＢ（Ｉ−１）（Ｉ＝２、…、Ｎ）を満たす様に、ＪＭＴＢ（Ｉ）（Ｉ＝Ｋ＋１、…、Ｎ）の値を設定する。ここで、本実施形態では、ＩＭＴＢ（Ｊ）≧ＩＭＴＢ（Ｊ−１）（Ｊ＝２、…、Ｎ）を満たす様にインデクスＩＭＴＢの値を設定しているので、軸交換による非ゼロ構造の変化に対してインデクスＩＭＴＢの値を更新する必要がなく、インデクスの変更に必要な演算回数を減らすことができる。
【００４５】
ステップ６０６では、第Ｋ段で選択した軸行ＫＰＩＶの値を配列ＩＰ（Ｋ）に格納して保持する。この情報は前進・後退代入処理部１１３で利用される。
【００４６】
次にステップ６０７では、図６のステップ６０７に示した数式の様に軸列のＡ（Ｉ、Ｋ）（Ｉ＝Ｋ＋１、…、ＩＭＴＢ（Ｋ））を軸要素Ａ（Ｋ、Ｋ）で消去する。この処理では、ステップ５０６と比較して消去範囲がＮからＩＭＴＢ（Ｋ）に減少している。ステップ６０８では、図６のステップ６０８に示した数式の様に軸列Ａ（Ｉ、Ｋ）（Ｉ＝Ｋ＋１、…、ＩＭＴＢ（Ｋ））及び軸行Ａ（Ｋ、Ｊ）（Ｊ＝Ｋ＋１、…、ＪＭＴＢ（Ｋ））からＡ（Ｉ、Ｊ）を消去する。この処理では、ステップ５０７と比較して消去範囲がＮからＩＭＴＢ（Ｋ）、ＪＭＴＢ（Ｋ）に減少している。
【００４７】
図７は本実施形態の前進・後退代入処理の処理手順を示すフローチャートである。図７では、非ゼロ構造特定インデクステーブル１０７を使用した前進・後退代入処理の処理手順を表している。
【００４８】
本実施形態の前進・後退代入処理部１１３は、ステップ７０１でＫを１からＮ−１迄１づつ増加させながらステップ７０２からステップ７０５の処理を繰り返す。
【００４９】
ステップ７０２では、ステップ６０６で設定された第Ｋ段で選択した軸行ＫＰＩＶの値を配列ＩＰ（Ｋ）から取り出して変数ＫＰＩＶに代入する。
【００５０】
次に、前記取出したＫＰＩＶとＫの値を比較し（ステップ７０３）、同じ値でないならば、Ｂ（ＫＰＩＶ）とＢ（Ｋ）を交換する（ステップ７０４）。ここでＢは右辺ベクトルの値を格納しておいた配列である。
【００５１】
ステップ７０５では、図７のステップ７０５に示した数式の様にＢ（Ｋ）及びＡ（Ｉ、Ｋ）（Ｉ＝Ｋ＋１、…、ＩＭＴＢ（Ｋ））からＢ（Ｉ）（Ｉ＝Ｋ＋１、…、ＩＭＴＢ（Ｋ））を消去する。この処理では、インデクスＩＭＴＢを使用することで、消去範囲がＮからＩＭＴＢ（Ｋ）に減少している。
【００５２】
ステップ７０６では、ＫをＮから１迄１づつ減少させながらステップ７０７の処理を繰り返す。ステップ７０７では、図７のステップ７０７に示した数式の様にＢ（Ｊ）、Ａ（Ｋ、Ｊ）（Ｊ＝Ｋ＋１、…、ＪＭＴＢ（Ｋ））及びＡ（Ｋ、Ｋ）から、連立一次方程式の解を算出してＢ（Ｋ）に格納する。ここでステップ７０７の（Ｊ＝Ｋ＋１、…、ＪＭＴＢ（Ｋ））の繰り返し処理は、ＪをＫ＋１からＪＭＴＢ（Ｋ）迄１づつ増加させる処理である。なお、ＫがＮの場合にはＪがＪＭＴＢ（Ｋ）よりも大きくなるので、前進・後退代入処理部１１３は、この繰り返し処理を行うことなくＳ＝０のままＢ（Ｎ）の計算を行い、Ｂ（Ｎ）にＢ（Ｎ）／Ａ（Ｎ、Ｎ）を代入する。この処理では、インデクスＪＭＴＢを使用することで計算範囲がＮからＪＭＴＢ（Ｋ）に減少している。
【００５３】
前記の様に本実施形態によれば、ゼロ要素格納の無駄を許容し、係数行列の非ゼロ要素の構造に依存せずに、いずれの係数行列も密行列と同様のデータ格納方法を採用することで、経験的、専門的知識を要することなく、係数行列の非ゼロ要素の構造を意識せずに、いずれの係数行列も密行列として与えることが可能である。このことにより、従来の様な係数行列の非ゼロ要素の構造毎に専用の連立一次方程式求解プログラムを選択するという作業がなくなり、操作性を向上させることができる。また本実施形態では、前記作成された非ゼロ構造特定インデクステーブルで示される範囲内の要素についてのみ計算を行うので、計算量を削減した連立一次方程式の求解を行うことが可能である。
【００５４】
以上説明した様に本実施形態の連立一次方程式求解装置によれば、ゼロ要素を含む疎行列の全要素を密行列と同様に配列に格納した後、それらの非ゼロ要素の範囲内について三角分解処理及び前進・後退代入処理を行って解を求めるので、連立一次方程式の数値解を計算する情報処理装置の操作性の向上を図り、求解に必要な計算量を削減することが可能である。
【００５５】
【発明の効果】
本発明によればゼロ要素を含む疎行列の全要素を密行列と同様に配列に格納した後、それらの非ゼロ要素の範囲内について三角分解処理及び前進・後退代入処理を行って解を求めるので、連立一次方程式の数値解を計算する情報処理装置の操作性の向上を図り、求解に必要な計算量を削減することが可能である。
【図面の簡単な説明】
【図１】本実施形態の連立一次方程式求解装置の概略構成を示す図である。
【図２】本実施形態の非ゼロ構造特定インデクステーブル１０７の形式例を示す図である。
【図３】本実施形態のインデクスＩＭＴＢ２０１及びインデクスＪＭＴＢ２０２の一例を示す図である。
【図４】本実施形態の非ゼロ要素構造計算処理の処理手順を示すフローチャートである。
【図５】従来の三角分解処理の処理手順を示すフローチャートである。
【図６】本実施形態の三角分解処理の処理手順を示すフローチャートである。
【図７】本実施形態の前進・後退代入処理の処理手順を示すフローチャートである。
【符号の説明】
１００…連立一次方程式求解装置、１０１…ＣＰＵ、１０２…メモリ、１０３…磁気ディスク装置、１０４…入力装置、１０５…出力装置、１０６…ＣＤ−ＲＯＭ装置、１０７…非ゼロ構造特定インデクステーブル、１１０…係数行列入力処理部、１１１…非ゼロ要素構造計算処理部、１１２…三角分解処理部、１１３…前進・後退代入処理部、２０１…インデクスＩＭＴＢ、２０２…インデクスＪＭＴＢ、３０１…疎行列、３０２…非ゼロ要素、３０３…計算範囲、３０４…終端非ゼロ要素行番号例、３０５…終端非ゼロ要素列番号例。
【図１】
0003827941.tif 000002
【図２】
0003827941.tif 000003
【図３】
0003827941.tif 000004
【図４】
0003827941.tif 000005
【図５】
0003827941.tif 000006
【図６】
0003827941.tif 000007
【図７】
0003827941.tif 000008