大規模行列の計算方法と注意点

2005/07/06 22:27

このQ&Aのポイント

大規模行列を解くプログラムの作成方法について悩んでいます。メモリの制約や非零要素の少なさなどの問題があります。ガウスの消去法は使えない可能性があり、ウェーブ・フロント法も零要素から非零要素への変化を発見する方法がわかりません。
大規模行列の計算方法として、ガウスの消去法とウェーブ・フロント法を考えています。しかし、メモリの制約や非零要素の少なさなどの問題があります。ガウスの消去法はメモリの制約を満たさない可能性があり、ウェーブ・フロント法では非零要素から零要素への変化を発見する方法がわかりません。
大規模行列を解くプログラムの開発において、ガウスの消去法とウェーブ・フロント法を検討しています。しかし、メモリの制約や非零要素の少なさなどの課題があります。ガウスの消去法はメモリの制約を満たさない可能性があり、ウェーブ・フロント法では零要素から非零要素への変化を発見する方法がわかりません。さらなる解法のアイデアを教えていただきたいです。

matsumai
お礼率25% (39/151)

C・C++・C#
回答数7
ありがとう数3

みんなの回答 （7）
専門家の回答

質問者が選んだベストアンサー

ベストアンサー

ChateauAres
ベストアンサー率43% (64/148)

2005/07/07 21:46 回答No.5

非零要素の位置だけを記録して解くのが大規模疎行列を扱う場合の基本です。計算の過程で発生する非零要素（専門的にはfill-inと呼びます）の発生位置は予め計算可能なので、その分のエリアは予め空けておきます。ウエーブ・フロント法は確かfill-inの発生をできるだけ抑制するための変換手法ですよね？この変換手法を「オーダリング」と呼びますが、実は解く問題によってオーダリングの手法は善し悪しがあります。ガウスであればより対角に近い場所に非零要素とfill-inが移動するすようにします。んで、要素のうまい記憶方法ですが、ＬＤＵ分解を用いる解法であれば、Ｄ：対角要素 d[10000] Ｕ：上△要素 U[??] Ｌ：下△要素　L[??] d0, U1, U2, ... Un L1, d1, Un+1, ... L2,Ln+1,d2, ... : : Ln こんな感じに記憶します。（分かりにくいかなぁ）「零要素から非零要素に変化する要素を発見するアルゴリズム」はＬＵ分解を手計算できないと理解は難しいかもしれません。手計算すれば、０だった所に数値が入るタイミングが分かります。また非零要素が対角に近く行列の右下の方に集まっている方がfill-inが少ないことも体感できると思います。私が持っている専門書ですが、行列計算ソフトウェア　小国力　丸善株式会社 ISBN 4-621-03654-8 　\9,270 これがあれば、様々な行列に対する高速解法がプログラムソース付きで解説されています。

その他の回答 (6)

ChateauAres
ベストアンサー率43% (64/148)

2005/07/08 00:09 回答No.7

訂正。つまり、番号順にＬＵ分解する場合はまず１が消えるので 2--5, 4--5, 2--4 の間に非零要素が出現します。 1a0bc a2d**　　*:非零要素 0d3e0 b*e4* c*0*5 5----2　　次に２が消去されると 3-5 に非零要素が出現 |　／..| 4----3 1a0bc a2d**　　*:非零要素 0d3e* b*e4* Uidx = ( 1,3,4,5,6,7,8,9,10 ) c***5 Udat = ( a,b,c,d,*,*,e,*,* ) となれば良い。

ChateauAres
ベストアンサー率43% (64/148)

2005/07/07 23:58 回答No.6

#5の私のウエーブ・フロント法は誤解してました。すみません。お詫びに、できるだけ簡単に fill-in と要素の記憶を方法を説明します。（できるかなぁ） 5---1----2 .　　　|　　　|　　このようなネットワークを行列で表現すると　　　4----3 1a0bc 各ノード（番号）とノード間のコスト（a-e)を a2d00　　とします。 0d3e0 b0e40 対角 d=(1,2,3,4,5) はそのまま記憶します。 c0005 上△に番地を連番で振ります。 *_1_2_3_4　　上△の非零要素の存在する番地は __*_5_6_7　　Uidx = ( 1,3,4,5,8 ) ____*_8_9　　上△行列は ______*_10 　Udat = ( a,b,c,d,e ) ________*　　（_はスペースの調整のため）しかし分解途中で非零要素が発生します。グラフを例に、ノード３を消去する場合はノード２，４が未消去であれば 2--3--4 → 2--4 となりノード２と４の間に線が出現します。これが非零要素です。つまり、番号順にＬＵ分解する場合はまず１が消えるので 2--5, 4--5 の間に非零要素が出現します。 1a0bc a2d0*　　*:非零要素 0d3e0 b*e4* c00*5 5----2　　次に２が消去されると 3-5 に非零要素が出現 |　　　| 4----3 1a0bc a2d0*　　*:非零要素 0d3e* b*e4* Uidx = ( 1,3,4,5,7,8,9,10 ) c0**5 Udat = ( a,b,c,d,*,e,*,* ) となれば良い。ちなみに消去の順番を変更して 5,1,2,3,4 の順にすると非零要素がどうなるか実験してみてください。このように非零要素を少なくする順番を求めることをオーダリングと呼びます。