今だけ人気マンガ100円レンタル特集♪

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

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

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


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

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

A 回答 (1件)

対称バンド行列とベクトルの積で検索すればいろいろとでてきます。


BALSのLevel2に?SBMVというルーチンがあります。
http://www.rcs.arch.t.u-tokyo.ac.jp/kusuhara/fsw …
疎行列の計算についてはsparseというライブラリがあります。(これについては名前だけしか知りません)

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

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

ありがとうございます。
なんとなくつかめてきました。
ただ、中間試験の勉強でしばらく手が付けられないのが残念です。

お礼日時:2013/05/20 21:10

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

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

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

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

Q大規模行列の計算

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

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

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

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

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

Aベストアンサー

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

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

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

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

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

...続きを読む

QFORTRAN で出力した文字の 左寄せについて

C Pad for Salford FTN77というコンパイラを使っております。
下記の様にOPENで開いてCLOSEでとじたTEXT文についてですが…

WRITE(*,*) '入力した数に1プラスされます。'
READ (*,*) A
B=A+1
OPEN(UNIT=10,FILE='C:\001.txt')
WRITE(10,100) '入力したのは',A
WRITE(10,100) '1たすと',B
100 FORMAT(A)
CLOSE(10)
STOP

…計算もされず、左寄せにもなりません。
仮に「100 FORMAT(A)」を消して(10,100)を(10,*)にすると左寄せにはなりませんが 計算して結果は表示されます。

計算して結果を左寄せにするにはどうすればよいでしょうか。
ご存知の方、アドバイスをお願いします。

Aベストアンサー

私が知っているfortranは77なのでもしかすると違っているかもしれませんが、

先ず変数Aは型宣言がないので実数扱いになります。

B=A+1(正確に記述するなら1ではなく1.)
が計算されることからもそういえます。

つぎに、FORMAT(A)の中のAは文字型を出力する際にし要するものですので、変数の型が一致していません。だから出力されないのだと思います。またAの後に桁数を示す数字が必要です。

実数に対してはFORMAT(F8.1)とかFORMAT(E8.3)とかのFやEを使用する必要があります。

また数値型の場合プラスマイナスの記号が入ることから、正値の場合+記号が省略されて、代わりにブランクが出力されたと思います。すなわち1つ目はブランクになります。
FORMAT(F1.0)等とすると桁オーバーを意味する*が出力されます。

整数型にしておけば1桁の場合FORMAT(I1)としておけば、左の1桁目に数字が出ますが、2桁以上やマイナス値のある数字の場合この方法は使用できません。

ブランクを取りたい場合、文字型で出力しなければなりませんが、たしかfortranには数値型データを文字型データに変換するコマンドがありません。

他の方法もあるかもしれませんが、そこで、一度数値データとしてファイルに出力して、そのファイルから文字型データとして1文字ずつ読み取るという方法で私自身は対処していました。

たしかこんな感じでした。
CHARACTER*1 H(8) 文字型と配列宣言
WRITE (10,601) A
601 FORMAT(F8.2)
BACKSPACE(10)
READ(10,602) (H(I),I=1,8)
602 FORMAT(8A1)

この後H(I)がブランクなら出力しない、ブランクでなければ出力するという判定作業を行って、ブランク以外の値が入っているI番目から後ろの値全部を文字型出力をします。

記憶が薄いので、上のとおりしてもうまくいきませんかもしれませんが、数値データを文字型データにうまく変換してやればできると思います。

私が知っているfortranは77なのでもしかすると違っているかもしれませんが、

先ず変数Aは型宣言がないので実数扱いになります。

B=A+1(正確に記述するなら1ではなく1.)
が計算されることからもそういえます。

つぎに、FORMAT(A)の中のAは文字型を出力する際にし要するものですので、変数の型が一致していません。だから出力されないのだと思います。またAの後に桁数を示す数字が必要です。

実数に対してはFORMAT(F8.1)とかFORMAT(E8.3)とかのFやEを使用する必要があります。

ま...続きを読む

Q不完全LU分解前処理つき双共役勾配法についておしえてください。

連立方程式を解くために不完全LU分解前処理つき双共役勾配法
について勉強しています。

前処理の際に、行列Aを不完全LU分解しその逆行列(LU)^(-1)というのを使用します。LU分解まではできたのですが、この逆行列は普通にLU分解+直接法という形でもとめるのでしょうか。だとしたら、直接法をつかっていてあまり高速化が期待できない様な気がしました。

不完全コレスキー分解つき共役勾配法(ICCG)のときは、不完全コレスキー分解後、間接的にAの逆行列をもとめて使用する方法がありましたのでなにかいい方法があるのかと思い質問しました。

はじめてのプログラミングで見当違いなことをいっているかもしれませんがよろしくおねがいします。

Aベストアンサー

あと、p.115の
6.2代入計算
の方が参考になるかもしれません。


人気Q&Aランキング