(57)【要約】【課題】  修正コレスキー分解法を用いた連立一次方程式の解法で使用される仮想記憶におけるページングの発生を抑制して、連立一次方程式の数値解の算出を高速に実行すること。【解決手段】  修正コレスキー分解法に基づく三角分解演算において、メインメモリの空き容量を検出して、メインメモリの記憶容量を越えない範囲で分解済み係数値データの一部をメインメモリ内の分解済係数格納領域Ｌ１に記憶するとともに、分解済み係数値データの残りを２次記憶装置内の分解済係数格納ファイルＬ２に記憶する。【選択図】  図８
2008070928.tif 000002
【特許請求の範囲】
【請求項１】
連立一次方程式に係る係数行列を修正コレスキー分解法に基づいて三角分解することで上三角行列、対角行列および下三角行列を得るとともに、これら上三角行列、対角行列および下三角行列に係る数値演算を実行することで連立一次方程式に係る数値解を算出する数値演算方法であって、
連立一次方程式に係る係数行列内の所定の行数または列数の係数値データを記憶する記憶容量を有する修正コレスキー分解法用記憶領域をアロケートする工程と、
前記修正コレスキー分解法用記憶領域を用いて、所定の行数または列数の係数値データに対して三角分解に係る数値演算を実行する工程と、
メインメモリの空き容量を検出する工程と、
前記メインメモリの空き容量に応じて、前記メインメモリの記憶容量を越えない範囲で分解済み係数値データの一部を前記メインメモリ内の分解済係数格納領域に記憶し、分解済み係数値データの残りを２次記憶装置内の分解済係数格納ファイルに記憶する工程と、
前記メインメモリ内の前記分解済係数格納領域に記憶された係数値データおよび前記２次記憶装置内の前記分解済係数格納ファイルに記憶された係数値データを用いて、上三角行列、対角行列および下三角行列に係る数値演算を実行する工程とを有することを特徴とする数値演算方法。
【請求項２】
修正コレスキー分解法用記憶領域を用いた三角分解が完了する毎に、メインメモリの空き容量を検出し、
前記メインメモリの空き容量が所定の閾値以上であれば、分解済みの１または複数行あるいは１または複数列の係数値データを前記メインメモリ内の分解済係数格納領域に記憶し、前記メインメモリの空き容量が所定の閾値未満であれば、分解済みの１または複数行あるいは１または複数列の係数値データを２次記憶装置内の分解済係数格納ファイルに記憶することを特徴とする請求項１に記載の数値演算方法。
【請求項３】
連立一次方程式に係る係数行列内の非ゼロ要素の係数値データが記憶される帯状記憶領域の最大幅を検出する工程を有し、
前記帯状記憶領域最大幅の２乗の数の係数値データを記憶する記憶容量を有する修正コレスキー分解法用記憶領域をアロケートすることを特徴とする請求項１に記載の数値演算方法。
【請求項４】
修正コレスキー分解法用記憶領域を用いた三角分解が完了する毎に、メインメモリの空き容量を検出し、
前記メインメモリの空き容量が１行分または１列分の係数値データを記憶するための記憶容量以上であれば、分解済みの１行または１列の係数値データを前記メインメモリ内の分解済係数格納領域に記憶し、メインメモリの空き容量が１行分または１列分の係数値データを記憶するための記憶容量未満であれば、分解済みの１行または１列の係数値データを２次記憶装置内の分解済係数格納ファイルに記憶することを特徴とする請求項３に記載の数値演算方法。
【請求項５】
修正コレスキー分解法用記憶領域を用いた三角分解が完了する毎に、前記修正コレスキー分解法用記憶領域において最小行または最小列に係る係数値データが記憶されていた記憶領域に、最小行または最小列から帯状記憶領域最大幅だけ離れた行または列に係る係数値データを記憶することを特徴とする請求項３に記載の数値演算方法。
【請求項６】
修正コレスキー分解法用記憶領域から分解済係数格納領域へ記憶される行毎または列毎の分解済み係数値データについて非ゼロ要素が存在する最小列位置または最小行位置を表す行内最小列番号テーブルまたは列内最小行番号テーブルを参照して、連続するゼロ要素を除いて分解済み係数値データを前記分解済係数格納領域に記憶することを特徴とする請求項１に記載の数値演算方法。
【請求項７】
修正コレスキー分解法に基づく三角分解に係るすべての演算が完了した後に、修正コレスキー分解法用記憶領域をデアロケートすることを特徴とする請求項１に記載の数値演算方法。
【請求項８】
上三角行列、対角行列または下三角行列に係る数値演算を実行する際に、参照方向の行または列において、メインメモリ内の分解済係数格納領域に記憶される係数値データと２次記憶装置内の分解済係数格納ファイルに記憶される係数値データとが混在する所定数の行または所定数の列から構成されるデータ混在領域の係数値データを、各行毎に列方向にまたは各列毎に行方向に連続的に参照できるように、当該係数値データを２次記憶装置内において新たに作成されたファイルに並び替えて記憶することを特徴とする請求項１に記載の数値演算方法。
【請求項９】
メインメモリの空き容量に応じて、該メインメモリ内の分解済係数格納領域に記憶する係数値データの行数または列数を特定する工程を有し、
特定された行数または列数の分解済み係数値データを前記メインメモリ内の前記分解済係数格納領域に記憶し、残りの分解済み係数値データを２次記憶装置内の分解済係数格納ファイルに記憶することを特徴とする請求項１に記載の数値演算方法。
【請求項１０】
連立一次方程式に係る係数行列を修正コレスキー分解法に基づいて三角分解することで上三角行列、対角行列および下三角行列を得るとともに、これら上三角行列、対角行列および下三角行列に係る数値演算を実行することで連立一次方程式に係る数値解を算出する数値演算プログラムであって、
連立一次方程式に係る係数行列内の所定の行数または列数の係数値データを記憶する記憶容量を有する修正コレスキー分解法用記憶領域をアロケートするステップと、
前記修正コレスキー分解法用記憶領域を用いて、所定の行数または列数の係数値データに対して三角分解に係る数値演算を実行するステップと、
メインメモリの空き容量を検出するステップと、
前記メインメモリの空き容量に応じて、前記メインメモリの記憶容量を越えない範囲で分解済み係数値データの一部を前記メインメモリ内の分解済係数格納領域に記憶し、分解済み係数値データの残りを２次記憶装置内の分解済係数格納ファイルに記憶するステップと、
前記メインメモリ内の前記分解済係数格納領域に記憶された係数値データおよび前記２次記憶装置内の前記分解済係数格納ファイルに記憶された係数値データを用いて、上三角行列、対角行列および下三角行列に係る数値演算を実行するステップとを有することを特徴とする数値演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、数値演算方法および数値演算プログラムに係り、特に修正コレスキー分解法を用いた大規模連立一次方程式の解法で使用される仮想記憶におけるページングの回数を低減して演算速度を向上することができる数値演算方法および数値演算プログラムに関する。
【背景技術】
【０００２】
大規模連立一次方程式の高速解法を用いて、多くの科学技術計算が実行されている。代表的な例としては、有限要素法による大規模構造解析が挙げられる。このような大規模構造解析において用いられる係数行列は、対称行列であり、スパースでゼロ係数が多く、非ゼロ係数が対角項周辺に集中し、対角項の係数が非対角項の係数に比べて十分に大きいという特徴を有している。対称行列であることで、対角項を含む左下半分または右上半分の係数行列を記憶するのみでよいが、スパースでゼロ係数が多いために効率的な記憶領域の使用が求められている。
【０００３】
係数行列が対称行列として与えられる大規模連立一次方程式の解法には、修正コレスキー分解法がよく利用される。修正コレスキー分解法を用いた解法では、連立一次方程式の係数行列Ａを、Ａ＝Ｌ・Ｄ・Ｌｔのように分解する。ここで、Ｌは対角項の係数値が１の下三角行列であり、Ｄは対角行列（対角項以外の項の係数値がゼロの行列）であり、ＬｔはＬの転置行列であって上三角行列である。
【０００４】
大規模連立一次方程式がＡ・ｘ＝ｂで与えられるとすると、当該連立一次方程式の数値解は、以下の３つの連立一次方程式を解くことで得られる。なお、ｘ，ｙ，ｚ，ｂはＬ，Ｄ，Ｌｔの次数と同一の要素数を有する列ベクトルである。
１］Ｌ・ｙ＝ｂ
２］Ｄ・ｚ＝ｙ
３］Ｌｔ・ｘ＝ｚ
１］においては前進代入によりｙを演算することができ、２］においてはｚｉ＝ｙｉ／ｄｉｉに基づいてｚを演算することができ、３］においては後退代入によりｘを演算することができる。すなわち、修正コレスキー分解法を用いることで、逆行列を求めることなく数値解ｘを容易に導くことが可能となる。
【０００５】
次に、修正コレスキー分解法の演算手順について説明する。対称行列Ａの要素をＡ（ｉ，ｊ）とし次数をｎとすると、修正コレスキー分解法を用いて下三角行列および対角行列を求める演算手順は、ＦＯＲＴＲＡＮ言語を用いて次のように記述される。
１）  ｄｏ  ｉ＝１，ｎ−１
２）    ｐ＝１／Ａ（ｉ，ｉ）
３）    ｄｏ  ｊ＝ｉ＋１，ｎ
４）      ｐｗ＝Ａ（ｊ，ｉ）＊ｐ
５）      ｄｏ  ｋ＝ｉ＋１，ｊ
６）        Ａ（ｊ，ｋ）＝Ａ（ｊ，ｋ）−ｐｗ＊Ａ（ｋ，ｉ）
７）      ｅｎｄｄｏ
８）      Ａ（ｊ，ｉ）＝ｐｗ
９）    ｅｎｄｄｏ
１０）ｅｎｄｄｏ
【０００６】
図１は、修正コレスキー分解法に基づく三角分解の演算手順を説明する図である。１）では、ピボットとして与えられる対角項要素Ａ（１，１）から対角項要素Ａ（ｎ−１，ｎ−１）まで、２）〜９）の演算を繰り返し実行することが示される。２）では、対角項要素を示す変数ｉの値が１ずつ増分されるループ１）において、対角項要素Ａ（ｉ，ｉ）の逆数をｐとすることが示される。３）では、ｉ＋１行からｎ行まで、４）〜８）の演算を繰り返し実行することが示される。４）では、行を示す変数ｊの値が１ずつ増分されるループ３）において、ｊ行ｉ列の要素Ａ（ｊ，ｉ）の係数値とｐとを乗じた値をｐｗとすることが示されている。５）では、ｉ＋１列からｊ列まで、６）の演算を繰り返し実行することが示されている。６）では、列を示す変数ｋの値が１ずつ増分されるループ５）において、ｊ行ｋ列の要素Ａ（ｊ，ｋ）の係数値から、ｋ行ｉ列の要素Ａ（ｋ，ｉ）の係数値とｐｗとの積を減じた値を要素Ａ（ｊ、ｋ）の新たな係数値とすることが示される。すなわち、図１に示されるｊ行においては、ｉ＋１列の要素Ａ（ｊ、ｉ＋１）からｊ列の要素Ａ（ｊ，ｊ）のそれぞれの係数値から、ｉ列のｉ＋１行の要素（ｉ＋１，ｉ）からｊ行の要素Ａ（ｊ，ｉ）のそれぞれの係数値にｐｗを乗じた値を減ずる演算が実行される。８）では、ｊ行ｉ列の要素Ａ（ｊ，ｉ）の係数値をｐｗとすることが示される。
【０００７】
上述した演算手順によれば、ループ１）内での対角項要素Ａ（ｉ，ｉ）をピボットとする演算では、行方向（縦方向）に延びるそれぞれの要素（Ａ（ｉ＋１，ｉ）からＡ（ｊ，ｉ））の係数値に基づいて、列方向（横方向）に延びるそれぞれの要素（Ａ（ｊ，ｉ＋１）からＡ（ｊ，ｊ））の係数値が変更される。すなわち、ｉ列の要素の係数値により、ｉ列より右側にある要素の係数値が変更される。また、行方向に延びるそれぞれの要素の係数値も、８）により、ｐｗに変更される。すなわち、ループ１）内での対角項要素Ａ（ｉ，ｉ）をピボットとする演算により係数値が変更される要素は、ｉ列およびｉ列より右側の要素に限られる。この場合、ｉ列より左側の要素の係数値が変更されることはない。したがって、修正コレスキー分解法において、ループ１）内で対角項要素Ａ（ｉ，ｉ）をピボットとする演算が完了してピボットが対角項要素Ａ（ｉ＋１，ｉ＋１）に移行する段階になれば、ｉ列の要素およびｉ列より左側の要素から成る領域は、分解済領域となる。この分解済領域内の要素については、対角項要素Ａ（ｉ，ｉ）をピボットとする演算が完了した後の演算において、その係数値が変更されることはない。
【０００８】
修正コレスキー分解法では、係数行列の対称性を利用して、対角項を含む左下半分または右上半分の係数行列のみを使用する。また、上述したように、大規模構造解析等で使用される係数行列では、非ゼロ係数が対角項周辺に集中しているという特徴を有する。このような場合には、メモリの節減を意図して、スカイライン記憶方式（可変帯状記憶方式）が用いられることが多い。図２は、スカイライン記憶方式を説明する図である。図２に例として示されている１２＊１２の係数行列においては、非ゼロ要素とゼロ要素とを区別するために、非ゼロ要素には番号が付されている。非ゼロ要素は対角項周辺に集中しており、効率的な記憶方式を採ることが求められる。スカイライン記憶方式では、非ゼロ要素が、矢印で示される番号順に一次元配列のａ（ｋ）（ｋは配列内での記憶位置、すなわちアドレスを示す）に記憶される。例えば、要素Ａ（４，３）の係数値データは、ａ（９）に記憶される。
【０００９】
また、スカイライン記憶方式では、ｉ行ｊ列の要素Ａ（ｉ，ｊ）の係数値が、一次元配列ａ（ｋ）内のどのアドレスに記憶されるかを特定できるように、各行についての先頭アドレスを示す一次元配列ｉａ（ｉ）（ｉは行番号を示す）、並びに各行において最初に非ゼロ要素が存在する列位置を示す一次元配列ｉｂ（ｉ）（ｉは行番号を示す）が設定されている。図２に示されるように、例えば７行目については、４列目から７列目にかけて非ゼロ要素が存在し、それぞれに２０から２３のアドレスが割り当てられている。この場合、先頭のアドレスが２０であるので、ｉａ（７）＝２０となる。また、非ゼロ要素が４列目から現れるので、ｉｂ（７）＝４となる。ｉ行ｊ列の要素Ａ（ｉ，ｊ）の係数値データが記憶される一次元配列ａ（ｋ）内のアドレスｋは、ｋ＝ｉａ（ｉ）＋ｊ−ｉｂ（ｉ）で与えられる。上述したようなスカイライン記憶方式を採用することで、記憶領域を大幅に節減することが可能となる。
【００１０】
修正コレスキー分解法を用いた大規模連立一次方程式の解法において、演算の高速化を実現するために種々の演算方法が開発されている。例えば、特許第２９５３９２９号公報では、修正コレスキー分解法を適用する対象となる係数行列を複数のブロック行列に分割して、対角行列および下三角行列（または上三角行列）の生成を、ブロック行列の計算に帰着させる方法が開示されている。この演算方法を採用した場合、修正コレスキー分解法に係る演算速度は、与えられた係数行列Ａの次数およびブロックサイズＭに関連付けられる。使用する電子計算機の仕様に応じて、与えられた係数行列Ａの次数について演算効率が最適となるブロックサイズＭが存在する。上記公報に記載された発明では、係数行列Ａの次数に対応する最適なブロックサイズＭをデータ記憶部に記憶するとともに、最適なブロックサイズを自動的に選択することで、修正コレスキー分解法に係る演算速度の向上を図っている。
【００１１】
また、特開平９−１４６９２５号公報には、スカイライン記憶方式を用いて一次元配列に記憶された係数行列を三角分解して得られた三角行列等に基づいて連立一次方程式の数値解を算出する計算装置において、演算効率が最適となるように任意数のスカイライン列群を選択し、当該スカイライン列群を対象として分解処理を実行する方法が開示されている。この方法においては、係数行列を構成する各々の列の先頭に位置している非ゼロ要素の係数値データが記憶される一次元配列内のアドレスを保持する列先頭アドレステーブルに基づいて、係数行列中で列の上端が揃っているスカイライン列群を識別する。上端の揃っているスカイライン列群を対象として分解処理を実行することで、ゼロ要素に係る無駄な計算の発生を抑制して、コレスキー分解法に係る演算速度の向上を図っている。
【００１２】
【特許文献１】特許第２９５３９２９号公報
【特許文献２】特開平９−１４６９２５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
係数行列Ａの帯状記憶領域内の係数値データが記憶される一次元配列ａ（）が大きな記憶容量を必要とする場合には、連立一次方程式に係る数値解を算出する演算において、ＯＳの管理の下に仮想記憶が使用される。この仮想記憶を使用する際には、メインメモリとハードディスク等の２次記憶装置との間において、「ページ」という単位でデータがやり取りされる。仮想記憶を使用する際のメモリの管理方式としてＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｒｙ  Ｕｓｅｄ）アルゴリズムが使用される場合には、未使用の時間がもっとも長いブロック（ページ）を選択して、当該ブロックをメインメモリから２次記憶装置へ移行（ページアウト）するとともに、新たなブロックを２次記憶装置からメインメモリへ移行（ページイン）する。したがって、メインメモリが一次元配列ａ（）を展開するのに十分な記憶容量を備えていない場合には、修正コレスキー分解法における三角分解演算や三角行列を用いた前進代入および後退代入による数値解の算出に係る演算等において、頻繁にページングが発生して、連立一次方程式の数値解を算出するのに時間を要するという課題があった。
【００１４】
図３は、連立一次方程式の数値解を算出する演算においてページングが発生する例を示す図である。図３の（ａ１），（ａ２），（ｂ１），（ｂ２）において、斜線で囲まれる領域は、非ゼロ要素が存在する帯状記憶領域を示す。この帯状記憶領域内の要素の係数値データは、スカイライン記憶方式を用いて一次元配列ａ（）に記憶される。修正コレスキー分解法を用いた三角分解演算や、上三角行列を用いて１］のＬ・ｙ＝ｂに係る数値演算を実行する際には、図３の（ａ１）および（ａ２）に記載される矢印に示されるように、演算に使用されるデータ領域が左上から右下に移行する。図３の（ａ１）におけるＭ１および（ａ２）におけるＭ２は、一次元配列ａ（）内の係数値データのなかでメインメモリに記憶される範囲を示す境界線として与えられるものである。なお、Ｌ・ｙ＝ｂに係る数値演算は、順次ｙｉ＝ｂｉ−Σｌｊ・ｙｊを算出することで実行される。
【００１５】
修正コレスキー分解法に基づく三角分解演算や、上三角行列を用いてＬ・ｙ＝ｂに係る数値演算を実行する際には、境界線Ｍ１までは、帯状記憶領域の左上の領域から右下の領域へ順次メインメモリ内に係数値データを記憶させて演算を実行する。境界線Ｍ１を越えて演算を実行すると、メインメモリの記憶容量を越えるので、一次元配列ａ（）内の新たな係数値データを含んだブロックを２次記憶装置からメインメモリへページインする毎に、未使用の時間が最も長いブロックすなわち左上の領域のブロックから順にメインメモリから２次記憶装置へページアウトする。帯状記憶領域全体についての演算が完了した時点では、図３の（ａ２）に示されるように、境界線Ｍ２より左上の領域のブロックはメインメモリから２次記憶装置へページアウトされている。
【００１６】
また、対角行列および下三角行列を用いて２］および３］のＤ・ｚ＝ｙおよびＬｔ・ｘ＝ｚに係る数値演算を実行する際には、図３の（ｂ１）および（ｂ２）に記載される矢印に示されるように、演算に使用されるデータ領域が右下から左上に移行する。図３の（ｂ１）におけるＭ３および（ｂ２）におけるＭ４は、一次元配列ａ（）内の係数値データのなかでメインメモリに記憶される範囲を示す境界線として与えられるものである。これらの演算を実行する場合にも、境界線Ｍ３を越えて演算を実行すると、メインメモリの記憶容量を越えるので、一次元配列ａ（）内の新たな数値データを含んだブロックをページインする毎に、未使用の時間が最も長いブロックすなわち右下のブロックから順にページアウトする。帯状記憶領域全体についての演算が完了した時点では、図３の（ｂ２）に示されるように、境界線Ｍ４より右下の領域のブロックはページアウトされている。なお、Ｄ・ｚ＝ｙおよびＬｔ・ｘ＝ｚに係る数値演算は、順次ｘｉ＝（ｙｉ−Σｌｊ・ｘｊ）／ｄｉｉを算出することで実行される。
【００１７】
本願発明は、上記課題を解決するためになされたものであり、修正コレスキー分解法を用いた連立一次方程式の解法で使用される仮想記憶におけるページングの発生を抑制して、連立一次方程式の数値解の算出を高速に実行することを可能とする数値演算方法および数値演算プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
上記の技術的課題を解決するために、本願発明に係る数値演算方法（数値演算プログラム）は、連立一次方程式に係る係数行列を修正コレスキー分解法に基づいて三角分解することで上三角行列、対角行列および下三角行列を得るとともに、これら上三角行列、対角行列および下三角行列に係る数値演算を実行することで連立一次方程式に係る数値解を算出する数値演算方法（数値演算プログラム）において、連立一次方程式に係る係数行列内の所定の行数または列数の係数値データを記憶する記憶容量を有する修正コレスキー分解法用記憶領域をアロケートする工程（ステップ）と、修正コレスキー分解法用記憶領域を用いて、所定の行数または列数の係数値データに対して三角分解に係る数値演算を実行する工程（ステップ）と、メインメモリの空き容量を検出する工程（ステップ）と、メインメモリの空き容量に応じて、メインメモリの記憶容量を越えない範囲で分解済み係数値データの一部をメインメモリ内の分解済係数格納領域に記憶し、分解済み係数値データの残りを２次記憶装置内の分解済係数格納ファイルに記憶する工程（ステップ）と、メインメモリ内の分解済係数格納領域に記憶された係数値データおよび２次記憶装置内の分解済係数格納ファイルに記憶された係数値データを用いて、上三角行列、対角行列および下三角行列に係る数値演算を実行する工程（ステップ）とを有するようにしたものである。
これにより、修正コレスキー分解法に基づく三角分解に係る数値演算並びに上三角行列、対角行列および下三角行列に係る数値演算を実行する際に、係数値データをメインメモリ内の分解済係数格納領域と２次記憶装置内の分解済係数格納ファイルとに分けて記憶する構成としたので、メインメモリの記憶容量を越えて係数値データをメインメモリに記憶することに起因するページングの発生を防止することが可能となり、連立一次方程式の数値解の算出を高速に実行することができる。
なお、上記のそれぞれの工程（ステップ）は、必ずしも記載された順序で実行される必要はない。前に記載された工程（ステップ）を後に記載された工程（ステップ）よりも後で実行するようにしてもよく、前に記載された工程（ステップ）と後に記載された工程（ステップ）とを並列的に実行するようにしてもよい。例えば、メインメモリの空き容量を検出した後に、修正コレスキー分解法用記憶領域を用いて、所定の行数または列数の係数値データに対して三角分解に係る数値演算を実行して、分解済み係数値データを記憶するようにしてもよい。
【００１９】
また、本願発明に係る数値演算方法は、修正コレスキー分解法用記憶領域を用いた三角分解が完了する毎に、メインメモリの空き容量を検出し、メインメモリの空き容量が所定の閾値以上であれば、分解済みの１または複数行あるいは１または複数列の係数値データをメインメモリ内の分解済係数格納領域に記憶し、メインメモリの空き容量が所定の閾値未満であれば、分解済みの１または複数行あるいは１または複数列の係数値データを２次記憶装置内の分解済係数格納ファイルに記憶するようにしたものである。
これにより、１または複数行（列）分の分解済み係数値データを単位として少量のデータ毎にメインメモリ内に記憶するので、メインメモリ内の記憶領域の大部分を使用して係数値データ等のデータを記憶することが可能となり、メインメモリに記憶された係数値データを用いての演算の割合が増加して、連立一次方程式の数値解の算出をさらに高速に実行することができる。
【００２０】
また、本願発明に係る数値演算方法は、連立一次方程式に係る係数行列内の非ゼロ要素の係数値データが記憶される帯状記憶領域の最大幅を検出する工程を有し、帯状記憶領域最大幅の２乗の数の係数値データを記憶する記憶容量を有する修正コレスキー分解法用記憶領域をアロケートするようにしたものである。
これにより、修正コレスキー分解法に基づく三角分解演算を実行するために必要とされる最小限の記憶領域をアロケートして演算を実行するので、メインメモリの記憶領域を効率的に利用することができる。
【００２１】
また、本願発明に係る数値演算方法は、修正コレスキー分解法用記憶領域を用いた三角分解が完了する毎に、メインメモリの空き容量を検出し、メインメモリの空き容量が１行分または１列分の係数値データを記憶するための記憶容量以上であれば、分解済みの１行または１列の係数値データを前記メインメモリ内の分解済係数格納領域に記憶し、メインメモリの空き容量が１行分または１列分の係数値データを記憶するための記憶容量未満であれば、分解済みの１行または１列の係数値データを２次記憶装置内の分解済係数格納ファイルに記憶するようにしたものである。
これにより、１行または１列分の分解済み係数値データを単位としてメインメモリ内に記憶するので、メインメモリ内の記憶領域の概ね全ての部分を使用して係数値データ等のデータを記憶することが可能となり、メインメモリに記憶された係数値データを用いての演算の割合が増加して、連立一次方程式の数値解の算出をさらに高速に実行することができる。
【００２２】
また、本願発明に係る数値演算方法は、修正コレスキー分解法用記憶領域を用いた三角分解が完了する毎に、修正コレスキー分解法用記憶領域において最小行または最小列に係る係数値データが記憶されていた記憶領域に、最小行または最小列から帯状記憶領域最大幅だけ離れた行または列に係る係数値データを記憶するようにしたものである。
これにより、修正コレスキー分解法用記憶領域の記憶容量を変更することなく、修正コレスキー分解法に基づいた三角分解演算を逐次的に実行することが可能となり、メインメモリの記憶領域を効率的に利用することができる。
【００２３】
また、本願発明に係る数値演算方法は、修正コレスキー分解法用記憶領域から分解済係数格納領域へ記憶される行毎または列毎の分解済み係数値データについて非ゼロ要素が存在する最小列位置または最小行位置を表す行内最小列番号テーブルまたは列内最小行番号テーブルを参照して、連続するゼロ要素を除いて分解済み係数値データを分解済係数格納領域に記憶するようにしたものである。
これにより、無駄なゼロ要素が分解済係数格納領域に記憶されることを防止することが可能となり、メインメモリの記憶領域を効率的に利用することができる。
【００２４】
また、本願発明に係る数値演算方法は、修正コレスキー分解法に基づく三角分解に係るすべての演算が完了した後に、修正コレスキー分解法用記憶領域をデアロケートするようにしたものである。
これにより、上三角行列、対角行列および下三角行列に係る数値演算を実行する際に利用できるメインメモリ内の記憶領域を増加することが可能となり、連立一次方程式の数値解の算出をさらに高速に実行することができる。
【００２５】
また、本願発明に係る数値演算方法は、上三角行列、対角行列または下三角行列に係る数値演算を実行する際に、参照方向の行または列において、メインメモリ内の分解済係数格納領域に記憶される係数値データと２次記憶装置内の分解済係数格納ファイルに記憶される係数値データとが混在する所定数の行または所定数の列から構成されるデータ混在領域の係数値データを、各行毎に列方向にまたは各列毎に行方向に連続的に参照できるように、当該係数値データを２次記憶装置内において新たに作成されたファイルに並び替えて記憶するようにしたものである。
これにより、上三角行列、対角行列または下三角行列に係る数値演算を実行する際に、データ混在領域において、連続的に係数値データを参照することが可能となるから、連立一次方程式の数値解の算出をさらに高速に実行することができる。
【００２６】
また、本願発明に係る数値演算方法は、メインメモリの空き容量に応じて、メインメモリ内の分解済係数格納領域に記憶する係数値データの行数または列数を特定する工程を有し、特定された行数または列数の分解済み係数値データをメインメモリ内の分解済係数格納領域に記憶し、残りの分解済み係数値データを２次記憶装置内の分解済係数格納ファイルに記憶するようにしたものである。
これにより、修正コレスキー分解法用記憶領域を用いた三角分解が完了する毎にメインメモリの空き容量を検出する必要がなくなり、分解済係数格納領域に記憶する係数値データの行数または列数を適切に選定することで、連立一次方程式の数値解の算出をさらに高速に実行することができる。
【発明の効果】
【００２７】
本願発明によれば、メインメモリの空き容量を検出して、メインメモリの記憶容量を越えない範囲で係数値データの一部をメインメモリ内の分解済係数格納領域に記憶するとともに、係数値データの残りを２次記憶装置内の分解済係数格納ファイルに記憶する構成としたので、修正コレスキー分解法に基づく三角分解に係る数値演算並びに上三角行列、対角行列および下三角行列に係る数値演算を実行する際に、メインメモリの記憶領域を越えて係数値データをメインメモリに記憶することに起因するページングの発生を防止することが可能となり、連立一次方程式の数値解の算出を高速に実行することができるという効果を奏する。また、修正コレスキー分解法用記憶領域の記憶容量を変更しないように構成すること、また分解済係数格納領域における係数値データの記憶にスカイライン記憶方式を適用すること等により、メインメモリの記憶領域を効率的に利用することが可能となる。
【発明を実施するための最良の形態】
【００２８】
以下、添付の図面を参照して、本願発明に係る実施の形態を説明する。
実施の形態１．
実施の形態１に係る数値演算は、大別して、修正コレスキー分解法に基づく三角分解演算と、１］のＬ・ｙ＝ｂ、２］のＤ・ｚ＝ｙおよび３］のＬｔ・ｘ＝ｚについてそれぞれの数値解を算出する数値演算とに分けられる。本願発明は、修正コレスキー分解法に基づく三角分解において、メインメモリ内の修正コレスキー分解法用記憶領域と分解済係数格納領域との記憶容量の合計が、仮想記憶においてページングを発生しない記憶容量以下となるように、メインメモリへの記憶制御を実行することを特徴とする。そこで、修正コレスキー分解法に基づく三角分解に係る具体的な演算手順を説明する前に、修正コレスキー分解法用記憶領域および分解済係数格納領域について説明する。なお、修正コレスキー分解法用記憶領域を一次元（または二次元）配列Ｂで表し、分解済係数格納領域を一次元配列Ｃで表すものとする。
【００２９】
図４は、任意のピボットについて修正コレスキー分解法に基づく三角分解演算が実行される領域を示す図である。図４において、Ｐは修正コレスキー分解法を適用する際に逐次的に設定されるピボット、Ｍは係数行列Ａに係る帯状記憶領域、ｍは帯状記憶領域Ｍの最大幅を示す。図１を参照して説明した修正コレスキー分解法に基づく三角分解の演算手順では、ピボットを対角要素Ａ（ｉ，ｉ）とした場合に、ｉ＋１行からｎ行までにおいて演算が実行される。但し、ｊ（ｊ＝ｉ＋１〜ｎ）行に係る演算において、要素Ａ（ｊ，ｉ）の係数値がゼロである場合には、当該ｊ行の係数値が変更されることはない。要素Ａ（ｊ，ｉ）の係数値が非ゼロである場合にのみ、図４の矢印で示されるように、列方向の各要素の係数値を変更する演算が実行される。したがって、図４に示されるピボットをＰに設定した場合の三角分解演算は、ピボットが位置する行を含めてｍ行分の演算を実行するのみで足りる。これにより、ｍ＊ｍの係数値データを記憶する記憶容量を有する記憶領域を修正コレスキー分解法用記憶領域としてアロケートすれば、任意に設定されたピボットＰに係る三角分解演算を実行することができる。
【００３０】
図５は、修正コレスキー分解法用記憶領域を示す図である。図５において、ピボットとして設定された対角項要素Ａ（ｉ，ｉ）は斜線で示されている。ｉ列の要素のＡ（ｊ，ｉ）の係数値を基にして、矢印に示されるように、ｉ列より右側の要素の係数値を変更するとともにｉ列の要素自体の係数値を変更する演算が逐次的に実行される。ｉ列より左側の要素の値は、分解済みであり変更されることはない。対角項要素Ａ（ｉ，ｉ）をピボットとして設定した演算が完了すれば、ｉ列より左側の要素は、全て分解済領域に含まれる。すなわち、ｉ行のｍ個のデータが分解済領域に含まれることになる。これにより、ｉ行の分解済み係数値データを分解済係数格納領域に書き込むことが可能となる。また、修正コレスキー分解法用記憶領域において、ｉ行のｍ個のデータが記憶されていた領域には、２次記憶装置から読み出されたｉ＋ｍ行のｍ個のデータが記憶される。なお、ｍ＊ｍの要素数を有する修正コレスキー分解用記憶領域については、一次元配列または二次元配列として与えられる。
【００３１】
上記のように、ｉ行のデータに代えてｉ＋ｍ行のデータを記憶するように構成することで、修正コレスキー分解用記憶領域の記憶容量はｍ＊ｍに維持され、新たな記憶領域をアロケートする必要がない。但し、修正コレスキー分解用記憶領域内に各行のデータが昇順または降順に記憶されるわけではないので、行番号に応じて修正コレスキー分解用記憶領域内のどの位置（アドレス）に当該行に係るデータが記憶されているかを特定できるように、プログラムを構成する必要がある。すなわち、ｍ＊ｍの配列を有する修正コレスキー分解法用記憶領域において、上から順にｉ行からｉ＋ｍ−１行の係数値データが記憶されるのは、ｍ回に１回の割合しかない。それ以外の場合では、上から順に、ｉ＋ｎ行からｉ＋ｍ−１行の係数値データが記憶され、その下側にｉ行からｉ＋ｎ−１行の係数値データが記憶される。ここで、ｎは１からｍ−１までの任意の整数である。
【００３２】
分解済係数格納領域は、一次元配列Ｃとして与えられる。分解済係数格納領域Ｃには、修正コレスキー分解用記憶領域Ｂを用いての対角項要素Ａ（ｉ，ｉ）をピボットとしての三角分解演算が完了してｉ行の分解済み係数値データが分解済領域に含まれるようになる毎に、分解済み係数値データが１行ずつ書き込まれる。修正コレスキー分解用記憶領域Ｂの記憶容量は一定であるので、分解済係数格納領域Ｃに１行分の係数値データが新たに記憶される前には、後述するように、メインメモリに１行分の係数値データを記憶することができる空き容量が存在するか否かを判定する。また、メインメモリ内の記憶領域をより効率的に使用するために、分解済係数格納領域Ｃにスカイライン記憶方式を適用するのが好適である。すなわち、それぞれの行毎に、非ゼロ要素が存在する最小列番号を表す行内最小列番号テーブルＴを設定する。それぞれの行の最小列番号をＴ（ｉ）とすると、ｉ行については、Ｔ（ｉ）列からｉ列までの要素の係数値データを記憶すれば十分である。帯状記憶領域の最大幅をｍとすれば、それぞれの行毎に、（ｉ−ｍ＋１）列から（Ｔ（ｉ）−１）列までの要素の係数値データを記憶する必要がなくなり、分解済係数格納領域Ｃの記憶容量を節減することが可能となる。
【００３３】
図６および図７は、この実施の形態１による修正コレスキー分解法に基づく三角分解の演算手順を示すフローチャートである。まず、連立一次方程式に係る係数行列Ａの次数および帯状記憶領域の最大幅ｍを検出する（ステップＳ１）。この係数行列Ａの係数値データは、ハードディスク等の２次記憶装置内に順編成データファイルとして記憶される。次に、修正コレスキー分解法用記憶領域として、ｍ＊ｍの係数値データを記憶する記憶容量を有する一次元（または二次元）配列Ｂをアロケートする（ステップＳ２）。また、三角分解演算を実行する際のピボット位置を示す変数ｉとして１を設定する（ステップＳ３）。修正コレスキー分解法用記憶領域Ｂがアロケートされれば、２次記憶装置内に順編成データとして記憶されている係数行列Ａに係る帯状記憶領域内の１行目からｍ行目までの係数値データを読み出して、読み出された係数値データを修正コレスキー分解法用記憶領域Ｂに書き込む（ステップＳ４）。
【００３４】
修正コレスキー分解法用記憶領域Ｂに三角分解演算の対象となるｍ行分の係数値データが設定されれば、対角項要素Ａ（ｉ，ｉ）をピボットとして、三角分解に係る演算を実行する（ステップＳ５）。この数値演算については、既に詳細に説明したので、ここではその説明を省略する。対角項要素Ａ（ｉ，ｉ）をピボットとした三角分解に係る演算が完了すれば、メインメモリの空き容量を検出する（ステップＳ６）。
【００３５】
メインメモリの空き容量の検出については、例えばＷｉｎｄｏｗｓ（登録商標）系のパーソナルコンピュータを使用する場合には、Ｗｉｎ３２ＡＰＩの関数ＧｌｏｂａｌＭｅｍｏｒｙＳｔａｔｕｓを利用することで、メモリに係る種々の情報を取得することができる。この関数を利用することで、１）物理メモリの使用率、２）物理メモリ量、３）使用可能物理メモリ量、４）仮想メモリ量および５）使用可能仮想メモリ量に係る情報を得ることができる。Ｆｏｒｔｒａｎ９０仕様には関数ＧｌｏｂａｌＭｅｍｏｒｙＳｔａｔｕｓは含まれていないが、Ｗｉｎ３２ＡＰＩの関数をｃａｌｌする仕組みがコンパイラのベンダにより提供されているものもある。ベンダに依存しない方法としては、ｃ言語またはｃ＋＋言語を用いて、コマンドラインで上記の５項目に係る情報を標準出力へ出力するプログラムを作成し、Ｆｏｒｔｒａｎ９０プログラムから該当情報を取り込む方法がある。
【００３６】
メインメモリの空き容量が検出されれば、メインメモリの空き容量が、ｍ行分の係数値データを記憶する修正コレスキー分解法用記憶領域Ｂ内の１行分の係数値データを記憶するための記憶容量以上であるか否かを判定する（ステップＳ７）。ここで、１行分の係数値データを記憶するための記憶容量とは、係数行列Ａに係る帯状記憶領域の最大幅がｍであるので、ｍ個の係数値データを記憶するための記憶容量を越えることはない。上述したように、分解済係数格納領域Ｃについてスカイライン記憶方式を適用する場合には、行内最小列番号テーブルＴを参照して、ｉ−ｍ＋１列目から連続するゼロ要素の個数をｍから減じた個数の要素の係数値データを記憶するための記憶容量を、１行分の係数値データを記憶するための記憶容量として設定するようにしてもよい。
【００３７】
ステップＳ７において、メインメモリの空き容量が１行分の係数値データを記憶するための記憶容量以上であると判定された場合には、分解済係数格納領域Ｃについて、新たに１行分の係数値データを記憶するための記憶領域をアロケートする（ステップＳ８）。係数行列Ａの１行目に係る分解済み係数値データを記憶する場合には、分解済係数格納領域を与える一次元配列Ｃを宣言するとともに１行分の係数値データを記憶するための記憶領域をアロケートする。係数行列Ａの２行目以降の各行に係る分解済み係数値データを記憶する場合には、既存の一次元配列Ｃについて、新たに１行分の係数値データを記憶するための記憶領域をアロケートする。
【００３８】
分解済係数格納領域Ｃについて新たに１行分の係数値データを記憶するための記憶領域がアロケートされれば、三角分解演算の完了により分解済領域に含まれることとなったｉ行の分解済み係数値データを分解済係数格納領域Ｃに書き込む（ステップＳ９）。この際、上述したように、スカイライン記憶方式を用いて分解済係数格納領域Ｃに係数値データを記憶するのが好適である。この場合、行内最小列番号テーブルＴを参照して、ｉ−ｍ＋１列目から連続するゼロ要素が存在する場合には、当該ゼロ要素の係数値データを分解済係数格納領域Ｃに記憶しないようにして、分解済係数格納領域Ｃに係る記憶容量を節減する。
【００３９】
ステップＳ７において、メインメモリの空き容量が１行分の係数値データを記憶するための記憶容量未満であると判定された場合には、ｉ行の分解済み係数値データを２次記憶装置内の分解済係数格納ファイルに記憶する（ステップＳ１０）。２次記憶装置内では、それぞれの行毎の係数値データを、書式なし順編成ファイルに記憶する。以下では、係数値データが記憶される当該順編成ファイルを分解済係数格納ファイルと称するものとする。これにより、修正コレスキー分解法を用いて三角分解された係数値データは、メインメモリ内の分解済係数格納領域Ｃと２次記憶装置内の順編成ファイルから成る分解済係数格納ファイルに分けて記憶されることになる。分解済み係数値データをメインメモリの記憶容量を越えてメインメモリに記憶することがなくなるので、三角分解に係る演算を実行する際に仮想記憶におけるページングの発生が防止される。
【００４０】
ステップＳ９またはステップＳ１０において、ｉ行の係数値データの記憶が完了すれば、修正コレスキー分解法用記憶領域Ｂにおいて、ｉ行の係数値データが記憶されていた記憶領域にｉ＋ｍ行の係数値データを記憶する。（ステップＳ１１）。この際、２次記憶装置内に順編成ファイルとして記憶されている係数行列Ａからｉ＋ｍ行の係数値データを読み出して、当該係数値データを修正コレスキー分解法用記憶領域Ｂ内の所定の記憶領域に書き込む。なお、ｉ＋ｍが係数行列Ａの次数ｎよりも大きい場合には、読み出す係数値データが存在しないので、係数値データの上書きが実行されることはない。
【００４１】
修正コレスキー分解法用記憶領域Ｂにおけるｉ＋ｍ行の係数値データの書き込みが完了すれば、変数ｉの値を１増分する（ステップＳ１２）。次に、変数ｉの値が係数行列Ａの次数ｎに等しいか否かを判定する（ステップＳ１３）。変数ｉの値が次数ｎに等しくなければ、新たに対角項要素Ａ（ｉ，ｉ）をピボットとした三角分解演算を実行するために、処理をステップＳ５へ移行する。変数ｉの値が次数ｎに等しければ、三角分解に係る全ての演算が完了したと認められるので、修正コレスキー分解法用記憶領域Ｂをデアロケートする（ステップＳ１４）。
【００４２】
次に、１］のL・ｙ＝ｂ、２］のD・ｚ＝ｙおよび３］のＬｔ・ｘ＝ｚに係るそれぞれの数値解を算出する演算について説明する。図８は、修正コレスキー分解法に基づく三角分解により得られた三角行列および対角行列の各要素に係る記憶態様を示す図である。図８の（ａ）には、修正コレスキー分解法に基づく三角分解により得られた下三角行列Ｌおよび対角行列Ｄが示されている。三角分解演算により得られた係数値データについては、上述したようにメインメモリの記憶容量を越える範囲の係数値データを２次記憶装置に記憶する。ＬＢは、下三角行列Ｌおよび対角行列Ｄについて、メインメモリ内の分解済係数格納領域Ｃに記憶されるデータ領域Ｌ１と２次記憶装置内の分解済係数格納ファイルに記憶されるデータ領域Ｌ２との境界を示している。
【００４３】
図８（ｂ）には、修正コレスキー分解法に基づく三角分解により得られた上三角行列Ｌｔおよび対角行列Ｄが示されている。上三角行列Ｌｔは、対角行列Ｄを基準として、下三角行列Ｌに対称である。この対称性を利用して、上三角行列Ｌｔの係数値データとして、下三角行列Ｌについて記憶された係数値データを使用する。ＬｔＢは、ＬＢと同様に、上三角行列Ｌｔおよび対角行列Ｄについて、メインメモリ内の分解済係数格納領域Ｃに記憶されるデータ領域Ｌｔ１と２次記憶装置内の分解済係数格納ファイルに記憶されるデータ領域Ｌｔ２との境界を示している。また、境界ＬＭ１と境界ＬＭ２との間のデータ領域（以下、データ混在領域と称する）においては、それぞれの行について、メインメモリ内の分解済係数格納領域Ｃに記憶されるデータと２次記憶装置内の分解済係数格納ファイルに記憶されるデータとが混在する。
【００４４】
１］のＬ・ｙ＝ｂに係る数値演算では、前進代入によりｙの各要素の数値を求める。この数値演算では、上方の行から下方の行へ向けて、順次ｙｉ＝ｂｉ−Σｌｊ・ｙｊを算出する。この数値演算においては、下三角行列内の係数値データの参照方向は、メインメモリ内の分解済係数格納領域Ｃおよび２次記憶装置内の分解済係数格納ファイルに係数値データが記憶された記憶方向と一致している。これにより、記憶領域内の連続する係数値データを基にして数値演算を実行することが可能となり、キャッシュのヒット率が向上して高速演算を実現することができる。
【００４５】
２］のＤ・ｚ＝ｙに係る数値演算では、ｚｉ＝ｙｉ／ｄｉｉに基づいてｚの各要素の数値を求める。また、３］のＬｔ・ｘ＝ｚに係る数値演算では、後退代入によりｘの各要素の数値を求める。この２］および３］の数値演算では、下方から上方の行へ向けて、順次ｘｉ＝（ｙｉ−Σｌｊ・ｘｊ）／ｄｉｉを算出する。図８（ｂ）に示されるように、この数値演算においては、上三角行列および対角行列の係数値データの参照方向は、メインメモリ内の分解済係数格納領域Ｃおよび２次記憶装置内の分解済係数格納ファイルに係数値データが記憶された記憶方向と異なっている。このために、行方向に係数値データを参照する際に、係数値データが記憶されている記憶手段の種別および当該記憶手段上における記憶位置（アドレス）を特定できるように、プログラムを構成する必要がある。
【００４６】
上述したように、境界ＬＭ１と境界ＬＭ２との間のデータ混在領域においては、それぞれの行について、メインメモリ内の分解済係数格納領域Ｃに記憶される係数値データと２次記憶装置内の分解済係数格納ファイルに記憶される係数値データとが混在する。このために、データ混在領域における数値演算には、特に時間を要する。この問題を解決するために、データ混在領域に存在する係数値データについては、２次記憶装置内に作成した新たなファイルに並び替えて記憶するものとする。この混在領域用ファイルは、順編成ファイルとして与えられ、メインメモリ内の分解済係数格納領域Ｃに記憶される係数値データおよび２次記憶装置内の分解済係数格納ファイルに記憶される係数値データを各行毎に列方向に連続的に参照できるように、当該係数値データを並び替えて書き込むことで作成される。これにより、上三角行列Ｌｔおよび対角行列Ｄに含まれる要素全体から成るデータ領域は、メインメモリ内の分解済係数格納領域Ｃに記憶されるデータ領域ＬＤ１と、２次記憶装置内の混在領域用ファイルに記憶されるデータ領域ＬＤ２と、２次記憶装置内の分解済係数格納ファイルに記憶されるデータ領域ＬＤ３とに分割される。数値演算を実行する際の参照方向と同じ方向に係数値データが記憶される混合領域用ファイルを作成することで、２］のＤ・ｚ＝ｙに係る数値演算および３］のＬｔ・ｘ＝ｚに係る数値演算を高速に実行することが可能となる。
【００４７】
なお、上記の実施の形態１では、修正コレスキー分解法に基づく三角分解に係る演算並びに上三角行列、対角行列および下三角行列に係る数値演算において、基本的に行毎に係数値データを列方向に参照する構成を採っているが、基本的に列毎に係数値データを行方向に参照する構成としてもよい。修正コレスキー分解法用記憶領域における係数値データの入れ替えについても、列単位で実行するようにしてもよい。分解済み係数値データの分解済係数格納領域または分解済係数格納ファイルへの記憶についても、行を単位に記憶する構成を採っているが、列を単位に記憶する構成としてもよい。分解済み係数値データを列を単位として分解済係数格納領域または分解済係数格納ファイルへ記憶する際に、スカイライン記憶方式を適用する場合には、列毎の係数値データのなかで非ゼロ要素が存在する最小行位置を表す列内最小行番号テーブルを設けるようにする。さらに、データ混在領域の係数値データを並び替えて構成される混在領域用ファイルについても、列方向に参照できるような構成を採っているが、行方向に参照できるような構成としてもよい。
【００４８】
また、上記の実施の形態１では、修正コレスキー分解法用記憶領域の記憶容量を帯状記憶領域最大幅ｍの２乗の数の係数値データを記憶できる記憶容量としているが、さらに大きな記憶容量をアロケートするように構成してもよい。この場合、修正コレスキー分解法用記憶領域を用いて、ｍより大きな所定数の行または列の係数値データを対象として三角分解演算を実行する。この三角分解演算により分解済みとなった２以上の行または列の係数値データを、連続して分解済係数格納領域または分解済係数格納ファイルへ記憶するようにしてもよい。修正コレスキー分解法用記憶領域における係数値データの入れ替えについても、２以上の行または列の係数値データを連続して入れ替えるようにしてもよい。また、検出されたメインメモリの空き容量と１行（列）分の係数値データを記憶するための記憶容量とを比較する構成としているが、分解済係数格納領域に連続して記憶される係数値データの行または列の数やメインメモリ等の仕様等に基づいて予め所定の閾値を設定し、検出されたメインメモリの空き容量と当該所定の閾値とを比較する構成としてもよい。
【００４９】
以上のように、この実施の形態１による数値演算方法によれば、メインメモリの空き容量を検出して、メインメモリの記憶容量を越えない範囲で係数値データの一部をメインメモリ内の分解済係数格納領域に記憶するとともに、係数値データの残りを２次記憶装置内の分解済係数格納ファイルに記憶する構成としたので、修正コレスキー分解法に基づく三角分解に係る数値演算並びに上三角行列、対角行列および下三角行列に係る数値演算を実行する際に、メインメモリの記憶容量を越えて係数値データをメインメモリに記憶することに起因するページングの発生を防止することが可能となり、連立一次方程式の数値解の算出を高速に実行することができる。
【００５０】
また、修正コレスキー分解用記憶領域を用いて対角項要素Ａ（ｉ，ｉ）をピボットとする三角分解演算が完了する毎に、メインメモリの空き容量を検出して、当該空き容量に応じて、分解済み係数値データをメインメモリ内の分解済係数格納領域または２次記憶装置内の分解済係数格納ファイルに記憶するように構成したので、所定数の行または列に係る係数値データを単位として少量のデータ毎にメインメモリ内にデータを記憶できるから、メインメモリ内の記憶領域の大部分を使用して係数値データ等のデータを記憶することが可能となり、メインメモリに記憶された係数値データを用いての演算の割合が増加して、連立一次方程式の数値解の算出をさらに高速に実行することができる。
【００５１】
また、係数行列内の非ゼロ要素の係数値データが記憶される帯状記憶領域の最大幅ｍの２乗の数の係数値データを記憶する記憶容量を有する修正コレスキー分解法用記憶領域を用いた三角分解演算が完了する毎に、分解済みの行または列に係る係数値データが記憶されていた記憶領域に、新たな行または列に係る係数値データを記憶するように構成したので、三角分解演算を実行するために必要とされる最小限の記憶容量を有する修正コレスキー分解法用記憶領域の記憶容量を変更することなく、修正コレスキー分解法に基づいた三角分解演算を逐次的に実行することが可能となり、メインメモリの記憶領域を効率的に利用することができる。
【００５２】
また、三角分解演算により分解済みの係数値データを、行内最小列番号テーブルを参照して、スカイライン記憶方式により分解済係数格納領域に記憶するように構成したので、無駄なゼロ要素が分解済係数格納領域に記憶されることを防止することが可能となり、メインメモリの記憶領域を効率的に利用することができる。
【００５３】
また、修正コレスキー分解法に基づく三角分解に係るすべての演算が完了した後に、修正コレスキー分解法用記憶領域をデアロケートするように構成したので、上三角行列、対角行列および下三角行列に係る数値演算を実行する際に利用できるメインメモリ内の記憶領域を増加することが可能となり、連立一次方程式の数値解の算出をさらに高速に実行することができる。
【００５４】
また、参照方向の行または列においてメインメモリ内の分解済係数格納領域に記憶される係数値データと２次記憶装置内の分解済係数格納ファイルに記憶される係数値データとが混在するデータ混在領域の係数値データを、２次記憶装置内において新たに作成された混在領域用ファイルに並び替えて記憶するように構成したので、上三角行列、対角行列または下三角行列に係る数値演算を実行する際に、データ混在領域において、連続的に係数値データを参照することが可能となるから、連立一次方程式の数値解の算出をさらに高速に実行することができる。
【００５５】
図６および図７に示されるフローチャートに記載された各工程を実行する修正コレスキー分解法に基づく三角分解演算プログラムや、上三角行列、対角行列および下三角行列に係る数値演算プログラム等から構成される連立一次方程式に係る数値解を算出する数値演算プログラムは、当該数値演算プログラムが記憶されたＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の情報記憶媒体を入手することで、あるいは当該数値演算プログラムが格納された外部のサーバからダウンロードすることで利用することが可能である。情報記憶媒体から読み出されるか、あるいは外部のサーバからダウンロードされた数値演算プログラムは、ワークステーションやパーソナルコンピュータ等の電子計算機内の２次記憶装置にインストールされる。２次記憶装置にインストールされメインメモリにロードされた数値演算プログラムを、電子計算機のＣＰＵ（制御部）により実行することで、実施の形態１において説明した数値演算方法を実現することができる。
【００５６】
なお、上記の実施の形態１により説明される数値演算方法および数値演算プログラムは、本願発明を限定するものではなく、例示することを意図して開示されているものである。本願発明の技術的範囲は特許請求の範囲により定められるものであり、特許請求の範囲に記載された発明の技術的範囲内において種々の設計的変更が可能である。例えば、上記実施の形態では、修正コレスキー分解法用記憶領域を用いた三角分解が完了する毎にメインメモリの空き容量を検出する構成としているが、三角分解に係る演算を実行する前にメインメモリの空き容量を検出し、メインメモリの空き容量に応じてメインメモリ内の分解済係数格納領域に記憶する係数値データの行数または列数を特定し、特定された行数または列数の分解済み係数値データをメインメモリ内の分解済係数格納領域に記憶し、残りの分解済み係数値データを２次記憶装置内の分解済係数格納ファイルに記憶するように構成してもよい。この場合、修正コレスキー分解法用記憶領域を用いた三角分解が完了する毎にメインメモリの空き容量を検出する必要がなくなり、分解済係数格納領域に記憶する係数値データの行数または列数を適切に選定することで、連立一次方程式の数値解の算出をさらに高速に実行することができる。
【産業上の利用可能性】
【００５７】
本願発明は、修正コレスキー分解法を用いた連立一次方程式の解法に適用できるものである。
【図面の簡単な説明】
【００５８】
【図１】修正コレスキー分解法に基づく三角分解の演算手順を説明する図である。
【図２】スカイライン記憶方式を説明する図である。
【図３】連立一次方程式の数値解を算出する演算においてページングが発生する例を示す図である。
【図４】任意のピボットついて修正コレスキー分解法に基づく三角分解演算が実行される領域を示す図である
【図５】修正コレスキー分解法用記憶領域を示す図である。
【図６】実施の形態１による修正コレスキー分解法に基づく三角分解の演算手順を示すフローチャートである。
【図７】実施の形態１による修正コレスキー分解法に基づく三角分解の演算手順を示すフローチャートである。
【図８】修正コレスキー分解法により得られた三角行列および対角行列の各要素に係る記憶態様を示す図である。
【符号の説明】
【００５９】
Ｐ  ピボット、Ｍ  帯状記憶領域、ｍ  帯状記憶領域最大幅、Ｌ  下三角行列、Ｄ  対角行列、Ｌｔ  上三角行列
【図１】
2008070928.tif 000003
【図２】
2008070928.tif 000004
【図３】
2008070928.tif 000005
【図４】
2008070928.tif 000006
【図５】
2008070928.tif 000007
【図６】
2008070928.tif 000008
【図７】
2008070928.tif 000009
【図８】
2008070928.tif 000010