![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?5a7ff87)
10000*10000の大規模行列を解くプログラムを作成したいと考えています。
行列は対称行列で疎行列です。一行あたりの非零要素は10~20程度しかなく、ほとんどが零要素になっています。
メモリの関係上[10000][10000]の配列の形で確保することはまず無理でした。なのでガウスの消去法は使えないかと思います。(使えるのかもしれませんが、要素のうまい記憶方法のアルゴリズムが浮かびません)
解法として、ウェーブ・フロント法を使おうと考えたのですが、計算前の行列内の零要素で上三角行列を求める過程において非零要素となる要素については、あらかじめ記憶しておかなければなりません。しかし、零要素から非零要素に変化する要素を発見するアルゴリズムがわかりません。
その方法や、そのほかの方法で10000*10000の大規模行列を解く方法があれば教えてください!
No.5ベストアンサー
- 回答日時:
非零要素の位置だけを記録して解くのが大規模疎行列を扱う場合の基本です。
計算の過程で発生する非零要素(専門的には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
これがあれば、様々な行列に対する高速解法がプログラムソース付きで解説されています。
No.7
- 回答日時:
訂正。
つまり、番号順に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,*,* ) となれば良い。
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 )
________* (_はスペースの調整のため)
しかし分解途中で非零要素が発生します。
グラフを例に、ノード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 の順にすると非零要素がどうなるか実験してみてください。このように非零要素を少なくする順番を求めることをオーダリングと呼びます。
![](http://oshiete.xgoo.jp/images/v2/common/profile/M/noimageicon_setting_10.png?5a7ff87)
No.1
- 回答日時:
非零要素を、その座標と値を持つ構造体のリストとして管理して、
配列の要素を参照したり、要素に値をセットするのを、
e=GetElement(x,y)
SetElement(x,y,e)
こんなふうに、関数化してしまうのはどうでしょう?
あとはどんなアルゴリズムで解いてもよいと思います。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Visual Basic(VBA) VBAで大量データの処理 3 2022/11/15 21:53
- Perl perlで2次元配列をサブルーチンに値渡しで渡す 5 2022/12/17 18:49
- C言語・C++・C# このプログラミングの問題を教えてほしいです。 キーボードからデータ数nとn個のデータを入力し、平均値 3 2022/12/19 22:51
- その他(プログラミング・Web制作) パイソンのプログラミングについての質問です 2 2023/05/22 12:39
- Excel(エクセル) エクセルの大きなシートでグラフを見つける 4 2022/07/28 10:07
- C言語・C++・C# C言語の課題が出たのですが自力でやっても分かりませんでした。 要素数がnであるint型の配列v2の並 3 2022/11/19 17:41
- 数学 行列Xの2ノルムと行列Xの要素の絶対値の最大のものだったら行列2ノルムの方が大きくなると思いますが、 2 2022/05/11 13:57
- その他(ソフトウェア) PowerAutomateDesktop UI要素に文字列を入力するには 1 2023/06/03 14:16
- Java javaでのプログラム(配列)について質問です. 2 2022/10/14 22:27
- C言語・C++・C# このプログラミングの問題を教えて欲しいです。 キーボードから整数kを入力し、kが配列aの中に何個存在 2 2022/12/19 22:50
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
動的にメモリを確保した配列の...
-
HPビルダー2001で選んで流す。
-
大規模行列の計算
-
XMLはなぜ普及したのか?
-
使用しない要素を無視するには...
-
[MS-Word2002] 「変更履歴の記...
-
head要素
-
東芝のDynabookなのですがアン...
-
ルート要素ノードが2個ある場合?
-
バッチファイルでテキストファ...
-
あるノードリストに、特定の名...
-
VB6でXMLを処理するには
-
XSLでXMLデータをタブ区切りデ...
-
動的な構造体配列の初期化
-
CPUの考え方を教えてください ...
-
コンテキストメニュークリック...
-
Excel-VBAでXMLの複数ノードの...
-
ASPで型宣言
-
XPathで途中に名前空間が設定さ...
-
MSXMLを使ってノードを削除した...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
Listからのnull要素を削除方法は?
-
getElementsByNameの要素数が取...
-
ASP.NETでツリービューを作成し...
-
MFCでのタブコントロールに...
-
■XSLT■複数のノードを違う属性...
-
head要素
-
hana no namae osiete kudasai.
-
wikipediaに記述されている関係...
-
DOMでの要素名の変更
-
RSS2.0でitemが空の場合の記述
-
element of surprise
-
2つの行動の違い
-
CPUの考え方を教えてください ...
-
東芝のDynabookなのですがアン...
-
XMLで要素が記述された順番に意...
-
昔Winnyってありましたけど、あ...
-
UTF-8でエンコーディングとはど...
-
バッチファイルでテキストファ...
-
ルート要素ノードが2個ある場合?
-
Excel-VBAでXMLの複数ノードの...
おすすめ情報