1. x_1 : 初期値
s_1 : - gradient of F at x_1
k = 1; 2. || gradient of F at x_k || が十分小さければ終了。 3. F(x_k + alpha_k s_k) で線形探索して,alpha_kを求める。
x_{k+1} = x_k + alpha_k s_k 4. lambda_k = || gradient of F at x_{k+1} ||^2 / || gradient of F at x_k ||^2
(Fletcher Reeves を使う場合) 5. s_{k+1} = - gradient of F at x_{k+1} + lambda_k s_k 6. k = k + 1, go to 2.
共役勾配法は行列積もなく,単純だから逆に速かったのかな (スコア:2)
共役勾配法は,行列とベクトルの掛け算も不要です。
ベクトルとベクトルの和,スカラー積,内積で済んでしまうから,メモリアクセスの速さが効いたということではないでしょうか。
GPU系は,GPUへのデータの配分とその結果を集めるところがボトルネックになったのでしょうか。
Re: (スコア:0)
> 共役勾配法は,行列とベクトルの掛け算も不要です。
いろいろ勘違いしてますよ
まず掛け算は必要です
https://ja.wikipedia.org/wiki/%E5%85%B1%E5%BD%B9%E5%8B%BE%E9%85%8D%E6%B3%95 [wikipedia.org]
ここの例だと,行列Aとベクトルa_k 及び p_kの積が複数回必要です
次に,内積は,行列とベクトルの掛け算の特殊な形で,1行N列の行列とN次元ベクトルの積です
言い換えると,内積を繰り返せば行列の積が得られます
ですから「行
Re:共役勾配法は行列積もなく,単純だから逆に速かったのかな (スコア:2)
F(x) を最小化するとします。
1. x_1 : 初期値
s_1 : - gradient of F at x_1
k = 1;
2. || gradient of F at x_k || が十分小さければ終了。
3. F(x_k + alpha_k s_k) で線形探索して,alpha_kを求める。
x_{k+1} = x_k + alpha_k s_k
4. lambda_k = || gradient of F at x_{k+1} ||^2 / || gradient of F at x_k ||^2
(Fletcher Reeves を使う場合)
5. s_{k+1} = - gradient of F at x_{k+1} + lambda_k s_k
6. k = k + 1, go to 2.
ですので,一般には行列とベクトルの掛け算は不要です。
Wikipediaでは,F(x)が2次関数ですので,gradientの計算に行列とベクトルの積が出てきたのだと思います。
計算量に比べてデータの移動が多そうですので,メモリアクセスと書いたのですが,
Tofuが有効だったということでしょうか。
Re:共役勾配法は行列積もなく,単純だから逆に速かったのかな (スコア:1)
最新のじゃないけど、この資料見れば実際にどんなことしてるのか書いてあるよ。
https://www.ssken.gr.jp/MAINSITE/event/2014/20140826-hpcf/lecture-04/S... [ssken.gr.jp]
疎行列ベクトル積は入ってるっぽいね。