X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/book_gpu.git/blobdiff_plain/4932967a1c684dc3f7ed04c19144101278b79972..be4f0c2285aefdeaab115857dd8d77d7aabe6c25:/BookGPU/Chapters/chapter16/gpu.tex?ds=sidebyside

diff --git a/BookGPU/Chapters/chapter16/gpu.tex b/BookGPU/Chapters/chapter16/gpu.tex
index bcfc686..f4f62f1 100644
--- a/BookGPU/Chapters/chapter16/gpu.tex
+++ b/BookGPU/Chapters/chapter16/gpu.tex
@@ -77,6 +77,36 @@ a preset tolerance~\cite{Golub:Book'96}.
 %% \end{algorithmic}
 %% \end{algorithm}
 
+\begin{algorithm}
+\caption{Standard GMRES\index{GMRES} algorithm.} \label{alg:GMRES}
+  \KwIn{ $ A \in \mathbb{R}^{N \times N}$, $b \in \mathbb{R}^N$,
+      and initial guess $x_0 \in \mathbb{R}^N$}
+  \KwOut{ $x \in \mathbb{R}^N$: $\| b - A x\|_2 < tol$}
+
+  $r = b - A x_0$\;
+  $h_{1,0}=\left \| r \right \|_2$\;
+  $m=0$\;
+
+  \While{$m < max\_iter$} {
+    $m = m+1$;
+    $v_{m} = r / h_{m,m-1}$\;
+    \label{line:mvp} $r = A v_m$\;
+    \For{$i = 1\ldots m$} {
+      $h_{i,m} = \langle v_i, r \rangle$\;
+      $r = r - h_{i,m} v_i$\;
+    }
+    $h_{m+1,m} = \left\| r \right\|_2$\label{line:newnorm} \;
+    %\STATE Generate Givens rotations to triangularize $\tilde{H}_m$
+    %\STATE Apply Givens rotations on $h_{1,0}e_1$ to get residual $\epsilon$
+    Compute the residual $\epsilon$\;
+    \If{$\epsilon < tol$} {
+      Solve the problem: minimize $\|b-Ax_m\|_2$\;
+      Return $x_m = x_0 + V_m y_m$\;
+    }
+  }
+\end{algorithm}
+
+
 At a first glance, the cost of using standard GMRES directly to
 solve the Newton update in Eq.~\eqref{eq:Newton}
 seems to come mainly from two parts: the