
316 Designing Scientific Applications on GPUs
Algorithm 16: left-preconditioned GMRES method with restarts
1 Choose an initial guess x
0
;
2 convergence = false;
3 k = 1;
4 r
0
= M
−1
(b − Ax
0
);
5 β = kr
0
k
2
;
6 while ¬convergence do
7 v
1
= r
0
/β;
8 for j = 1 to m do
9 w
j
= M
−1
Av
j
;
10 for i = 1 to j do
11 h
i,j
= (w
j
, v
i
);
12 w
j
= w
j
− h
i,j
v
i
;
13 end
14 h
j+1,j
= kw
j
k
2
;
15 v
j+1
= w
j
/h
j+1,j
;
16 end
17 Set V
m
= {v
j
}
1≤j≤m
and
¯
H
m
= (h
i,j
) is an upper Hessenberg
matrix of size (m + 1) ×m;
18 Solve a least-squares problem of size m: min
y∈IR
m
kβe
1
−
¯
H
m
yk
2
;
19 x
m
= x
0
+ V
m
y
m
;
20 r
m
= M
−1
(b − Ax
m
);
21 β = kr
m
k
2
;
22 if (β < ε) or (k ≥ maxiter) then
23 convergence = true;
24 else
25 x
0
= x
m
;
26 r
0
= r
m
;
27