+La méthode native GMRES ou "Generalized Minimal Residual", développée par Saad et Schultz en 1986, est une des méthodes itératives les plus utilisées pour résoudre un système d'équations linéaires ou non [3,4,43,44,45]. Elle est basée sur la minimisation de la norme euclidienne d'un vecteur résidu obtenu à chaque itération par une projection sur un espace de Krylov. Plus précisement, soit le système d'équations \eqref{eq:2}. Un sous-espace de Krylov d'ordre {m} est défini comme suit :
+
+\begin{equation}
+\label{eq:Krylov}
+K_m = Vect \{ b, Ab, A^2b, ..., A^{m-1}b \}
+\end{equation}
+
+où : Vect désigne l'espace généré par les vecteurs en argument.
+
+Il est démontré [3,..] que le vecteur projeté $x_m$ sur $K_m$ donne une valeur approchée de la solution exacte du système d'équations en minimisant le résidu $r_m$ tel que :
+
+\begin{equation}
+\label{eq:residu}
+r_m = Ax_m - b
+\end{equation}
+On suppose que les vecteurs de l'équation \eqref{eq:Krylov} sont linéairement indépendants. Comme le montre cette équation, la taille des vecteurs de base augmente linéairement avec m qui varie de 0 à $n-1$ (n étant la taille initiale de la matrice A) entrainant à chaque itération un besoin de stockage de plus en plus grand. \\
+
+Afin de réduire et optimiser l'algorithme, on peut combiner avec d'autres méthodes telles que les itérations de Arnoldi [] utilisant la procédure d'orthogonalisation de Gram-Shmidt [] pour trouver une base orthonormée de l'espace $K_m$ notée $Q_m = [q_1, ..., q_m]$. On peut donc écrire :
+
+\begin{equation}
+\label{eq:proj}
+\forall x_m \in K_m, x_m = Q_m y
+\end{equation}
+
+et le résidu dont la norme est à minimiser peut s'écrire :
+\begin{equation}
+\label{eq:residu}
+r_m = A Q_m y - b
+\end{equation}
+
+D'après cette procédure, il existe une matrice de Hessenberg $H_m$ de taille m telle que :
+\begin{equation}
+\label{eq:hessen}
+H_m = Q^T_m A Q_m
+\end{equation}
+En introduisant la matrice notée $\tilde{H}_m$ obtenue par l'ajout d'une ligne supplémentaire à $H_m$ avec la seule valeur non nulle est celle à la position (m+1,m), on démontre qu'on a la relation suivante [3,43,44,45] :
+
+\begin{equation}
+\label{eq:hessen1}
+A Q_m = Q_{m+1} \tilde{H}_m
+\end{equation}
+
+Ainsi, le résidu donné par l'équation \eqref{eq:residu} peut s'écrire en utilisant \eqref{eq:hessen1} :
+\begin{equation*}
+\label{eq:residu1}
+(r_m = Q_{m+1} \tilde{H}_m y - b) \\
+\Leftrightarrow (\|r_m\| = \|Q_{m+1} \tilde{H}_m y - b\|)
+\end{equation*}
+
+Comme la norme ne change pas après la multiplication avec la matrice unitaire $Q^{-1}_m$, on a :
+\begin{equation*}
+\label{eq:norme1}
+\|r_m\| = \|Q_{m+1} \tilde{H}_m y - b\| = \|Q^{-1}_m Q_{m+1} \tilde{H}_m y - Q^{-1}_m b\|
+\end{equation*}
+
+Ou :
+
+\begin{equation}
+\label{eq:norme2}
+\|r_m\| = \|\tilde{H}_m y - Q^{-1}_m b\|
+\end{equation}
+
+Or :
+\begin{equation}
+\label{eq:q_1}
+Q^{-1}_m b = \left( \begin{array}{c}
+q^{-1}_1 b \\
+q^{-1}_2 b \\
+\vdots \\
+q^{-1}_{m+1} b
+\end{array}\right)
+\end{equation}
+
+Et comme les colonnes $q_j$ de $Q_m$ forment une base orthonormale de l'espace de Krylov $K_m$, on a :
+
+\begin{equation*}
+\label{eq:q1}
+q_1 = \frac{b}{\|b\|}
+\end{equation*}
+et :
+\begin{equation*}
+\label{eq:q_1j}
+\forall j > 1, q^{-1}_{j} b = 0 \text { et } q^{-1}_1 b = \|b\|
+\end{equation*}
+Donc, l'équation \eqref{eq:q_1} peut s'ecrire :
+
+\begin{equation}
+\label{eq:q_f}
+Q^{-1}_m b = \|b\| e_1 \text{ avec } e_1 = (1,0, ..., 0)^T
+\end{equation}
+
+Finalement, la norme du résidu à minimiser peut s'écrire à partie de \eqref{eq:norme2} et \eqref{eq:q_f} :
+
+\begin{equation}
+\label{eq:norme3}
+\|r_m\| = \| \tilde{H}_m y - \text { } \|b\| \text { } e_1 \|
+\end{equation}
+La méthode des moindres carrés peut être utilisée pour effectuer cette minimisation et trouver $y$. On utilise après la relation \eqref{eq:proj} pour déterminer la valeur approchée de la solution à l'itération m.
+
+\begin{equation*}
+\label{eq:proj1}
+x_m = Q_m y
+\end{equation*}
+L'algorithme de GMRES repose sur ces deux dernières equations.
+Une autre amélioration de l'algorithme, surtout en terme de réduction des vecteurs à maintenir en mémoire mais aussi en termes de temps de calcul pour atteindre la convergence, est le "redémarrage" [43]. Il s'agit de "redémarrer" l'algorithme après une tranche de k itérations, k étant fixé par l'utilisateur au départ. A chaque redémarrage, la valeur initiale $x_0$ est remplacée par le dernier $x_m$ trouvé et $r_0$ par le dernier $r_m$. \\
+
+Le pseudo-code de l'algorithme GMRES optimisé avec les itérations d'Arnoldi avec un redémarrage est donné à la Figure~\ref{algo:02}.
+
+\begin{figure}[!t]
+\begin{algorithmic}[1]
+\Input \\
+$A_{ij}$ (Matrice d'entrée), $b_{i}$ (Vecteur du membre droit), $n$ (Taille des vecteurs) et des matrices, \\
+$m$ (Nombre d'itérations avant redémarrage), $h_{ij}$ (Matrice de Hessenberg), \\
+$q_i$(Suite de vecteurs constituant une base orthonormée de l'espace de Krylov $K_i$), \\
+$w_i$ (variable intermédiaire)
+\Output $x_{m}$ (Vecteur solution)\medskip
+
+\State Charger $A_{ij}$, $b_{i}$, $n$,
+\State Assigner la valeur initiale $x^0$
+\State $r_0 \leftarrow b - Ax_0$
+\State $q_1 \leftarrow \frac{r_0}{\|r_0\|}$
+\State \textbf{repeat}
+\For {$j=0,1,2,\ldots m$}
+\For {$i=1,2,\ldots j$}
+\State $h_{i,j} = (A q_j, q_i)$
+\State $x_i \leftarrow 0$
+\State $w_{j+1} = A q_j - \sum_{i=1}^j h_{i,j} q_i$
+\State $h_{j+1,j} = \| w_{j+1} \|$
+\State $h_{i,j} = \frac {w_{j+1}} {h_{j+1,j}}$
+\EndFor
+\EndFor
+\State Calculer la solution approchée $x_{m}$
+\State $x_{m} = x_0 + Q_m y_m \hspace{0.1cm} tel \hspace{0.1cm} que \hspace{0.1cm} y_m \hspace{0.1cm} minimise \hspace{0.1cm} \| \tilde{H}_m y - \hspace{0.1cm} \|b\| \hspace{0.1cm} e_1 \|, y \in R^m.$
+\State Redémarrage
+\State $r_m \leftarrow b - Ax_m$
+\State Réinitialiser pour le redémarrage
+\State $x_0 \leftarrow x_m$
+\State $r_0 \leftarrow r_m$
+\State $q_1 \leftarrow \frac{r_0}{\|r_0\|}$
+\State \textbf{Until} {( Obtention de la condition de convergence : $\| r_m \|$ \hspace{0.1cm} est satisfaisant )}
+\Statex
+\end{algorithmic}
+\caption{Algorithme itératif GMRES avec redémarrage}
+\label{algo:02}
+\end{figure}
