大規模行列の計算方法と注意点
- 大規模行列を解くプログラムの作成方法について悩んでいます。メモリの制約や非零要素の少なさなどの問題があります。ガウスの消去法は使えない可能性があり、ウェーブ・フロント法も零要素から非零要素への変化を発見する方法がわかりません。
- 大規模行列の計算方法として、ガウスの消去法とウェーブ・フロント法を考えています。しかし、メモリの制約や非零要素の少なさなどの問題があります。ガウスの消去法はメモリの制約を満たさない可能性があり、ウェーブ・フロント法では非零要素から零要素への変化を発見する方法がわかりません。
- 大規模行列を解くプログラムの開発において、ガウスの消去法とウェーブ・フロント法を検討しています。しかし、メモリの制約や非零要素の少なさなどの課題があります。ガウスの消去法はメモリの制約を満たさない可能性があり、ウェーブ・フロント法では零要素から非零要素への変化を発見する方法がわかりません。さらなる解法のアイデアを教えていただきたいです。
- ベストアンサー
大規模行列の計算
10000*10000の大規模行列を解くプログラムを作成したいと考えています。 行列は対称行列で疎行列です。一行あたりの非零要素は10～20程度しかなく、ほとんどが零要素になっています。 メモリの関係上[10000][10000]の配列の形で確保することはまず無理でした。なのでガウスの消去法は使えないかと思います。(使えるのかもしれませんが、要素のうまい記憶方法のアルゴリズムが浮かびません) 解法として、ウェーブ・フロント法を使おうと考えたのですが、計算前の行列内の零要素で上三角行列を求める過程において非零要素となる要素については、あらかじめ記憶しておかなければなりません。しかし、零要素から非零要素に変化する要素を発見するアルゴリズムがわかりません。 その方法や、そのほかの方法で10000*10000の大規模行列を解く方法があれば教えてください！
- matsumai
- お礼率25% (39/151)
- C・C++・C#
- 回答数7
- ありがとう数3
- みんなの回答 （7）
- 専門家の回答
質問者が選んだベストアンサー
非零要素の位置だけを記録して解くのが大規模疎行列を扱う場合の基本です。 計算の過程で発生する非零要素（専門的には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)
訂正。 つまり、番号順にＬＵ分解する場合はまず１が消えるので 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)
#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 の順にすると非零要素がどうなるか実験してみてください。このように非零要素を少なくする順番を求めることをオーダリングと呼びます。
- xcrOSgS2wY
- ベストアンサー率50% (1006/1985)
回答No.2の回答者です。 "sparse matrix"の間違いでした。 恥かしい・・・
- Tacosan
- ベストアンサー率23% (3656/15482)
なんとなく逆反復なんて浮かんだんですが, そもそも「大規模行列を解く」ってどういう意味なんでしょうか?
- xcrOSgS2wY
- ベストアンサー率50% (1006/1985)
疎行列に関するアルゴリズムは多数知られていますので、"spase matrix"で検索してみてはいかがでしょうか。
非零要素を、その座標と値を持つ構造体のリストとして管理して、 配列の要素を参照したり、要素に値をセットするのを、 e=GetElement(x,y) SetElement(x,y,e) こんなふうに、関数化してしまうのはどうでしょう？ あとはどんなアルゴリズムで解いてもよいと思います。
関連するQ&A
- 大規模疎行列の高速な計算方法について
突然の思い付きで大規模疎行列と列ベクトルの積を高速に計算する必要に迫られています。 しかし、右も左もわからない状態です（ついさっき疎行列という言葉を知りました）。 なにか取っ掛かりが欲しいのですが参考になる資料などありましたら是非教えてください。 計算する行列の特徴などを書いておきます ・約2600万×2600の万正方行列です（分割しない場合） ・対角線（左上から右下）に対して対称に分布しています ・対角線上に帯状に分布しています ・ゼロでない要素は全体の0.002%程度です（十分大きい行列の場合） さらに、GPUを使いたいとも思っています。 煮え切らない質問で申し訳ないのですがどうぞよろしくお願いします。
- ベストアンサー
- C・C++・C#
- 次元の行列に関する問題です
次の次元と基底を教えてください。よろしくお願いします。 １、2×２行列 ２、m×n行列 ３、n×n行列すべての構成要素は対角線上をのぞいてすべて０ ４、n×n行列の上三角 ５、2×２の対称行列 ６、３×３の対称行列 ７、n×nの対称行列 英語をやくしているのでちょっとおかしいところとか情報量が足りなかったりしたらごめんなさい。基本的な問題なんだと思いますが、よろしくお願いします。
- 締切済み
- 数学・算数
- 連立一次方程式を解くプログラムについて
数値計算の本を見たら必ず載っている連立1次方程式の解法ですが、どのようなタイプの行列でも解くことができるものにはどのような解法があるでしょうか。もちろん、解くことができる範囲でということではあります。その意味でガウスの消去法（ピボット付）になるでしょうか。ガウスの消去法は解き方に基本的な制約はないですね。一方、共役勾配法の説明を見ると"対称正定値行列の場合、..."となっており、その範囲でしか考えていないということでしょうか。そうなるとかなり絞られることになってしまいます。任意の行列は変換して対称正定値に変換できる、ということでもないと思いますが。 有限要素法に関連した連立方程式解法についても書籍1冊分の解説とかありそうですが。高速化のために長い解説があったとしても前提によって使える範囲が狭いものが多いように思えるのですが。よろしくお願いします。
- 締切済み
- 数学・算数
- 行列演算： 固有ベクトルの解法
現在、対称行列の固有値、固有ベクトルを求めるプログラムを作成し、つい最近完成しました。 しかし、とても使い物にならないプログラムになってしまいました。 理由はとても遅いのです。 解法の手順として、まず固有値を求めてから固有ベクトルを求めるようと考え、入力の対称行列をHouseHolder法により三重対角行列に変換し、それをQR法により対角化してまず固有値を求めました。 固有値を求めることができたので、次に固有ベクトルを求めます。手順として、固有値ごとに入力対称行列の対角成分から固有値を減算した行列をＬＵ分解し、連立一次方程式を解くように固有ベクトルを求めていきます。 この一連の手順で、対称行列の固有値、固有ベクトルを求めることができたのですが、とても時間がかかってしまいます。 ただし、対称行列の固有値を求めるまでの時間はとても高速です。 ５００×５００の行列の固有値、固有ベクトルを求めるのに３０分はかかってしまいますが、その中で固有値を求める時間は２秒しかかかりません。 つまり今固有値がわかっている状態で、固有ベクトルを高速に求めたいと考えています。 なにか高速に固有ベクトルを求める方法（アルゴリズム）はあるでしょうか？
- ベストアンサー
- 数学・算数
- 転置行列への変換が分かりません。
転置行列への変換が分かりません。 現在、type型のrow行column列の行列（row >= 2, column >= 2, row != column）を、要素数がrow * column個ある配列arrayを用いて表現しています。更にR行C列目の要素はrow * C + R番目のarrayの要素で示しています。 そして転置行列ですが、行列type^(row * column)と行列type^(column * row)は要素数が同じなのでarrayと同じサイズの配列を用いて表現が可能ですし、ひとつずつ要素の置換を行えば新しく一時的にtype^(column * row)の行列を作って単純に代入処理をするよりもメモリに負担が掛からないはずです。 よって今は以下のアルゴリズムを考案し実装したのですが、問題が発生しました。 （以下配列i番目の要素をarray[i - 1]、行列matrixのa行b列の要素はmatrix[a - 1][b - 1]と記す。） ---- 入力 matrix in type^(row * column)とresult_matrix in type^(column * row)を示す、row * column個の要素を持つarrayが与えられる。 手順1 変数xに1を、変数yに0を代入する。一時要素領域tmp_elemにmatrix[x][y] = array[x + y * row]を代入する。 手順2 result_matrix[y][x] = array[y + x * column]とtmp_elemを交換する。 手順3 変数tにy + x * columnを代入し、xにtとrowの剰余を、yにtをrowで割った値の整数部を代入する。 手順4 xが1でかつyが0なら終了。そうでなければ手順2から再度処理を実行。 ---- 分かりやすく書くと、与えられた始点の位置にある転置前の行列としての要素を取得し、次に行列を既に転置された形のものとみなしてから、さっき取得した要素を転置後にあるべき場所へと移動させ、そこに元々あった要素に対して更に再帰的に手順を適応する感じです（実装ではループに落としていますが）。終了条件は「交換対象が始点へ戻ってきたとき」です。 しかし、次々と交換していく流れにおいて処理されない要素が出てきました。integer^(10 * 5)における以下の行列 ---- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, ---- の転置（仮） ---- 0, 10, 20, 30, 40, 1, 11, 7, 31, 41, 2, 12, 22, 32, 14, 3, 13, 23, 33, 43, 4, 21, 24, 34, 44, 5, 15, 25, 28, 45, 6, 16, 26, 36, 46, 35, 17, 27, 37, 47, 8, 18, 42, 38, 48, 9, 19, 29, 39, 49, ---- です。 ここではメインの流れmatirx[1][0] -> ... -> matrix[0][1]では走査できない要素の流れとして matrix[5][3] -> matrix[8][2] -> matrix[2][4] -> matrix[4][1] -> matrix[1][2] -> matrix[7][0] が存在しますが、検出できなかったこの流れにどの様な規則性があるのかどうかが分からないままです。 行列を転置行列に一時行列なしで変換する方法と、このアルゴリズムの不完全な部分を教えてください。 ＞＜；
- ベストアンサー
- その他（プログラミング・開発）
- 転置行列
大きさm×ｎの一次元配列に、m×ｎの行列Ａの要素が, Ａ00, Ａ01, Ａ02, ... , Ａ0n-1, Ａ10, Ａ11, Ａ12, ... , A1n-1, ... , Am-1,0, Am-1,1, ..., Am-1,n-1 の順に入っているとき、作業用の配列を使わないで、（あるいは大きさmまたはｎ程度の一次元配列を作業用に使って）、もとの領域に転置行列を入れる、すなわち、 A00, A10, A20, ... , Am-1,0, A01, A11, A21, ... , Am-1,1, ..., A0n-1, A1n-1, ... , Am-1,n-1 の順に要素を入れ替える効率のよい方法を探しています。ご存知の方ご教示ください。
- 締切済み
- C・C++・C#
- 対称行列の対角要素を増加させた場合の固有値について
n次の対称行列Aの一つの対角要素を増加させた対称行列をA'とします． Aの固有値を大きい順にλ1，λ2，・・・λn， A'の固有値を大きい順にλ'1，λ'2，・・・λ'nとします． このとき，λ'1=>λ1，λ'2=>λ2，・・・，λ'n=>λn が成り立つことを証明したいのですが， クーランのミニマックス法（行列の二次形式を最大化し，拘束条件を動かして最小化する方法）を用いる以外の方法で，できるだけ簡単に証明できませんか？ どなたか，よろしくお願い致します．
- 締切済み
- 数学・算数
