個人事業主の方必見!確定申告のお悩み解決

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

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

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

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

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

このQ&Aに関連する最新のQ&A

A 回答 (7件)

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



計算の過程で発生する非零要素(専門的にはfill-inと呼びます)の発生位置は予め計算可能なので、その分のエリアは予め空けておきます。

ウエーブ・フロント法は確かfill-inの発生をできるだけ抑制するための変換手法ですよね?
この変換手法を「オーダリング」と呼びますが、実は解く問題によってオーダリングの手法は善し悪しがあります。
ガウスであればより対角に近い場所に非零要素とfill-inが移動するすようにします。

んで、要素のうまい記憶方法ですが、LDU分解を用いる解法であれば、
D:対角要素 d[10000]
U:上△要素 U[??]
L:下△要素 L[??]

d0, U1, U2, ... Un
L1, d1, Un+1, ...
L2,Ln+1,d2, ...
: :
Ln

こんな感じに記憶します。(分かりにくいかなぁ)

「零要素から非零要素に変化する要素を発見するアルゴリズム」はLU分解を手計算できないと理解は難しいかもしれません。

手計算すれば、0だった所に数値が入るタイミングが分かります。また非零要素が対角に近く行列の右下の方に集まっている方がfill-inが少ないことも体感できると思います。

私が持っている専門書ですが、
行列計算ソフトウェア 小国力 丸善株式会社
ISBN 4-621-03654-8  \9,270
これがあれば、様々な行列に対する高速解法がプログラムソース付きで解説されています。
    • good
    • 0

訂正。



つまり、番号順にLU分解する場合はまず1が消えるので
2--5, 4--5, 2--4 の間に非零要素が出現します。

1a0bc
a2d**  *:非零要素
0d3e0
b*e4*
c*0*5

5----2  次に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,*,* ) となれば良い。
    • good
    • 0

#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 )
________*  (_はスペースの調整のため)

しかし分解途中で非零要素が発生します。
グラフを例に、ノード3を消去する場合はノード2,4が未消去であれば
2--3--4 → 2--4 となりノード2と4の間に線が出現します。これが非零要素です。
つまり、番号順にLU分解する場合はまず1が消えるので
2--5, 4--5 の間に非零要素が出現します。

1a0bc
a2d0*  *:非零要素
0d3e0
b*e4*
c00*5

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

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


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

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

    • good
    • 0

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

    • good
    • 0

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


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

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q大規模疎行列の高速な計算方法について

突然の思い付きで大規模疎行列と列ベクトルの積を高速に計算する必要に迫られています。
しかし、右も左もわからない状態です(ついさっき疎行列という言葉を知りました)。
なにか取っ掛かりが欲しいのですが参考になる資料などありましたら是非教えてください。

計算する行列の特徴などを書いておきます
・約2600万×2600の万正方行列です(分割しない場合)
・対角線(左上から右下)に対して対称に分布しています
・対角線上に帯状に分布しています
・ゼロでない要素は全体の0.002%程度です(十分大きい行列の場合)

さらに、GPUを使いたいとも思っています。


煮え切らない質問で申し訳ないのですがどうぞよろしくお願いします。

Aベストアンサー

対称バンド行列とベクトルの積で検索すればいろいろとでてきます。
BALSのLevel2に?SBMVというルーチンがあります。
http://www.rcs.arch.t.u-tokyo.ac.jp/kusuhara/fswiki/wiki.cgi?page=%BF%F4%C3%CD%B7%D7%BB%BB%A5%E9%A5%A4%A5%D6%A5%E9%A5%EA
疎行列の計算についてはsparseというライブラリがあります。(これについては名前だけしか知りません)

cuBLASとcuSPARSEという上記に対応したGPU版がありますのでそれを使うのがよいと思います。
https://developer.nvidia.com/gpu-accelerated-libraries

また自分でGPU用のプログラムを作るのでしたら、最近ではopenACCに対応したコンパイラが出ていますのでそれを使う手も

QC言語 配列の長さの上限

C言語で配列Array[N]の長さNの上限っていくらなんでしょうか?
もし可能なのであれば上限を2147483647にしたいのですが、方法を教えてください。

Aベストアンサー

そもそもWindowsの32bit版はアプリが仮想メモリ空間を2GBしか使えません。2GBを超えるには64bit版が必要です。
たとえ64bit版OSだとしても添え字が2147483647って、単純なintの配列だとしても4x2147483647=8GB必要ですね。実メモリ16GBとかのPCを用意しますか?
そもそも配列で2147483647個必要なアルゴリズムに問題ありだと思います。


人気Q&Aランキング