大規模行列の計算

10000*10000の大規模行列を解くプログラムを作成したいと考えています。

行列は対称行列で疎行列です。一行あたりの非零要素は10～20程度しかなく、ほとんどが零要素になっています。

メモリの関係上[10000][10000]の配列の形で確保することはまず無理でした。なのでガウスの消去法は使えないかと思います。(使えるのかもしれませんが、要素のうまい記憶方法のアルゴリズムが浮かびません)

解法として、ウェーブ・フロント法を使おうと考えたのですが、計算前の行列内の零要素で上三角行列を求める過程において非零要素となる要素については、あらかじめ記憶しておかなければなりません。しかし、零要素から非零要素に変化する要素を発見するアルゴリズムがわかりません。

その方法や、そのほかの方法で10000*10000の大規模行列を解く方法があれば教えてください！

No.5 ベストアンサー 回答者： ChateauAres 回答日時： 2005/07/07 21:46

非零要素の位置だけを記録して解くのが大規模疎行列を扱う場合の基本です。

計算の過程で発生する非零要素（専門的には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
これがあれば、様々な行列に対する高速解法がプログラムソース付きで解説されています。

No.7 回答者： ChateauAres 回答日時： 2005/07/08 00:09

訂正。

つまり、番号順にＬＵ分解する場合はまず１が消えるので
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,*,* ) となれば良い。

No.6 回答者： ChateauAres 回答日時： 2005/07/07 23:58

#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 の順にすると非零要素がどうなるか実験してみてください。このように非零要素を少なくする順番を求めることをオーダリングと呼びます。

No.4 回答者： xcrOSgS2wY 回答日時： 2005/07/07 19:44

回答No.2の回答者です。

"sparse matrix"の間違いでした。
恥かしい・・・

No.3 回答者： Tacosan 回答日時： 2005/07/07 13:07

なんとなく逆反復なんて浮かんだんですが, そもそも「大規模行列を解く」ってどういう意味なんでしょうか?

No.2 回答者： xcrOSgS2wY 回答日時： 2005/07/06 23:36

疎行列に関するアルゴリズムは多数知られていますので、"spase matrix"で検索してみてはいかがでしょうか。

No.1 回答者： YAMAMAYA#2 回答日時： 2005/07/06 22:37

非零要素を、その座標と値を持つ構造体のリストとして管理して、

配列の要素を参照したり、要素に値をセットするのを、
e=GetElement(x,y)
SetElement(x,y,e)
こんなふうに、関数化してしまうのはどうでしょう？
あとはどんなアルゴリズムで解いてもよいと思います。