【手続補正書】
【提出日】平成17年8月23日(2005.8.23)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
対称な非零構造を持つN（Ｎ：２以上の整数）次元の行列Aを係数行列とし、ベクトルｂを定数項とする連立一次方程式Ax=bを、p（ｐ：２以上の整数）台のプロセッサとメモリと入力装置と出力装置とを備えた並列計算機システムを用いてLU分解により解く方法であって、
（１）入力装置より係数行列A、右辺ベクトルbをプロセッサに入力し、
（２）以下の条件(2-1)と(2-2)を満たすように、１からNまでの数の集合I={1、 2、 ... N}を互いに重なりのない2p+1個の集合IA1、 IA2、 ... 、 IAp、 IB1、 IB2、 ... 、   IBp、 ICに分割し、
(2-1) 行番号が集合IA1、 IA2、 ... IApのいずれかに属する行列Aの行iに対し    ては、行iの属する集合をIAkとしたとき、行ｉの任意の非零要素の列番号が   集合IAkもしくは集合IBkに含まれる、
(2-2) 行番号が集合IB1、 IB2、 ... 、 IBpのいずれかに属する行列Aの行iに対    しては、行iの属する集合をIBkとしたとき、行ｉの任意の非零要素の列番号   がIAkもしくはIBkもしくはICに含まれる、
（３）行列Aの行および列を、集合IA1、 IA2、 ... 、 IAp、 IB1、 IB2、 ... 、 IBp、 ICの順に並べ替え、
（４）第1、 2、 ... 、 p番目のプロセッサで独立にそれぞれ列集合IA1、 IA2、 ... 、   IApに対応する小行列のピボット選択付きLU分解を行い、
（５）該ＬＵ分解の結果に基づき少なくとも一部のプロセッサで列集合IB1、IB2、   ... 、 IBp、 ICに対応する小行列のピボット選択付きLU分解を行い、
（６）該LU分解の結果に基づき前進消去演算と後退代入演算とを行って上記解ベクトルxを求め、
（７）求めた解ベクトルxを上記出力装置より出力する、
ことを特徴とする並列計算機システムを用いた連立一次方程式の求解方法。
【請求項２】
上記（２）の分割する処理は、
上記行列Aが三重対角行列であるとき上記条件(2-1)と(2-2)を満たすように、
１. それぞれが３以上N-2以下で、かつ互いに４以上離れたp-1個の増加する整  数の列IC1、 IC2、 ... 、 ICp-1を選んでIC={IC1、 IC2、 ... ICp-1}とし、
２. IB1={IC1-1}、IBp={ICp-1+1}、２≦k≦p-1のときIBk={ICk-1+1、 ICk-1}とし、３．IA1={1、 ... 、 IB1-1}、 IAp={ IBp+1、 ... 、 N}、 ｂQ≦k≦p-1のときIAk={ICk-1+  2、 ICk-2}とする、
処理を有する請求項１記載の並列計算機システムを用いた連立一次方程式の求解方法。
【請求項３】
対称な非零構造を持つN（Ｎ：２以上の整数）次元の行列Aを係数行列とし、ベクトルｂを定数項とする連立一次方程式Ax=bを、p（ｐ：２以上の整数）台のプロセッサとメモリと入力装置と出力装置とを備えた並列計算機システムを用いてLU分解により解く方法であって、
（１）入力装置より係数行列A、右辺ベクトルbをプロセッサに入力し、
（２）以下の条件(2-1)と(2-2)を満たすように、１からNまでの数の集合I={1、 2、 ... N}を互いに重なりのない2p+1個の集合IA1、 IA2、 ... 、 IAp、 IB1、IB2、 ... 、   IBp、 ICに分割し、
(2-1) 行番号が集合IA1、 IA2、 ... IApのいずれかに属する行列Aの行iに対し    ては、行iの属する集合をIAkとしたとき、行ｉの任意の非零要素の列番号が   集合IAkもしくは集合IBkに含まれる、
(2-2) 行番号が集合IB1、 IB2、 ... 、 IBpのいずれかに属する行列Aの行iに対しては、行iの属する集合をIBkとしたとき、行ｉの任意の非零要素の列番号 がIAkもしくはIBkもしくはICに含まれる、
上記行列Aが有限要素法もしくは差分法により生じる剛性行列であるときに上記
条件(2-1)と(2-2)を満たすように、
１. 該有限要素法もしくは差分法で用いるメッシュを、異なる部分領域に属する  節点どうしがメッシュ上で隣接することのないように、p個の部分領域、およびそれらの境界の領域ICに分割し、
２. 上記p個の部分領域のそれぞれにおいて、境界点に接する節点のみからなる  集合をそれぞれIB1、 IB2、 ... IBｐとし、
３  それ以外の節点の集合をそれぞれIA1、 IA2、 ... 、 IApとする、
（３）行列Aの行および列を、集合IA1、 IA2、 ... 、 IAp、 IB1、 IB2、 ... 、 IBp、ICの順に並べ替え、
（４）第1、 2、 ... 、 p番目のプロセッサで独立にそれぞれ列集合IA1、 IA2、 ... 、   IApに対応する小行列のピボット選択付きLU分解を行い、
（５）該ＬＵ分解の結果に基づき少なくとも一部のプロセッサで列集合IB1、IB2、   ... 、 IBp、 ICに対応する小行列のピボット選択付きLU分解を行い、
（６）該LU分解の結果に基づき前進消去演算と後退代入演算とを行って上記解ベクトルxを求め、
（７）求めた解ベクトルxを上記出力装置より出力する、
ことを特徴とする並列計算機システムを用いた数値シミュレーション実行方法。
【請求項４】
対称な非零構造を持つN（Ｎ：２以上の整数）次元の回路網行列Aを係数行列とし、電流源を表すベクトルｂを定数項として回路網内のある節点における未知電圧ｘに関する連立一次方程式Ax=bを、p（ｐ：２以上の整数）台のプロセッサとメモリと入力装置と出力装置とを備えた並列計算機システムを用いてLU分解により解く回路シミュレーション実行方法であって、
（１）回路網の節点間のインピーダンスの逆数を表す係数行列A、各節点に流れ
込む外部からの電流を表す右辺ベクトルbを入力装置よりプロセッサに入力し、
（２）上記行列に対応する回路を、異なる部分回路に属する節点どうしが１個の
素子で結ばれることのないように、p個の部分回路とそれらの境界部分の回路に
分割し、
（３）上記境界部分の回路に含まれる節点の集合をICとし、上記p個の部分回路のそれぞれにおいて、境界部分の回路に属する節点に１個の素子を通して接続する節点のみからなる節点の集合をそれぞれIB1、 IB2、 ... IBpとし、それ以外の節点の集合をそれぞれIA1、 IA2、 ... 、 IApとし、
（４）行列Aの行および列を、集合IA1、 IA2、 ... 、 IAp、 IB1、 IB2、 ... 、 IBp、ICの順に並べ替え、
（５）第1、 2、 ... 、 p番目のプロセッサで独立にそれぞれ列集合IA1、 IA2、 ... 、   IApに対応する小行列のピボット選択付きLU分解を行い、
（６）該ＬＵ分解の結果に基づき少なくとも一部のプロセッサで列集合IB1、IB2、   ... 、 IBp、 ICに対応する小行列のピボット選択付きLU分解を行い、
（７）該LU分解の結果に基づき前進消去演算と後退代入演算とを行って上記解ベクトルxを求め、
（８）求めた解ベクトルxを上記出力装置より出力する、
ことを特徴とする並列計算機システムを用いた回路シミュレーション実行方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
【発明が解決しようとする課題】
上記のND法による連立一時方程式の解法では、三重対角行列の行と列とを入れ替えて図７のような形に変形することにより、並列性を確保していた。しかし、LU分解を用いて連立一次方程式を解く場合、解に誤差が入りやすい悪条件の問題でも正しく解くためには、一般にピボット選択という操作を取り入れなければならない。ピボット選択とは、第K列に対するLU分解の演算AIJ=AIJ-AIK*AKJ/AKKにおいて、右辺の分母に来る値AKKがなるべく大きくなるように、第K列の第K行目以降の要素の中で最大の絶対値を持つ要素A K′Kを選び、第K行と第K′行とを入れ替えて以降の計算を行う方法である。