## 2 GMRES and GMRES(m)  
The Arnoldi process [2] is often used to orthonormalize the Krylov vectors \(\mathbf{A}^{j}\mathbf{r}_{0}\), \(j=0,\ldots,m-1\) in Equation (4), such that the resultant vectors \(\mathbf{v}_{i},\ i=1,\ldots,m\) satisfy \(\mathbf{v}_{j}=\delta_{ij},\;i,j=1,\ldots,m\), where \(\delta_{ij}\) is the Kronecker delta symbol. The full orthonormalization procedure, known as the Algorithm 1, is set up as follows. ```
1: Select \(m\) and give an initial \(\mathbf{r}_{0}\)
2:\(\mathbf{v}_{1}=\frac{\mathbf{r}_{0}}{\|\mathbf{r}_{0}\|}\)
3: Do \(j=1:m\)
4:\(\mathbf{w}_{j}=\mathbf{Av}_{j}\)
5: Do \(i=1:j\)
6:\(h_{ij}=\mathbf{v}_{i}\cdot\mathbf{w}_{j}\)
7:\(\mathbf{w}_{j}=\mathbf{w}_{j}-h_{ij}\mathbf{v}_{i}\)
8: Enddo of \(i\)
9:\(h_{j+1,j}=\|\mathbf{w}_{j}\|\)
10:\(\mathbf{v}_{j+1}=\frac{\mathbf{w}_{j}}{h_{j+1,j}}\)
11:Enddo of \(j\)
```  
**Algorithm 1**Arnoldi process  
A dot between two vectors represents the inner product, like as \(\mathbf{a}\cdot\mathbf{b}=\mathbf{a}^{\mathrm{T}}\mathbf{b}\). \(\mathbf{V}\) denotes the Arnoldi matrix whose \(j\)th column is \(\mathbf{v}_{j}\):  
\[\mathbf{V}:=[\mathbf{v}_{1},\ldots,\mathbf{v}_{m}]\in\mathbb{R}^{n\times m}. \tag{13}\]  
After \(m\) steps of the Arnoldi process, we can construct an upper Hessenberg matrix, \(\mathbf{H}_{m}\), as follows:  
\[\mathbf{H}_{m}=\left[ \begin{array}{cccc}h_{11}&h_{12}&\ldots&h_{1m}\\ h_{21}&h_{22}&\ldots&h_{2m}\\ h_{32}&\ldots&h_{3m}\\ \ddots&&\vdots\\ &&h_{m,m-1}&h_{mm}\end{array} \right]. \tag{14}\]  
Utilizing \(\mathbf{H}_{m}\), the Arnoldi process can be expressed as a matrix product form:  
\[\mathbf{AV}=\mathbf{VH}_{m}+h_{m+1,m}\mathbf{v}_{m+1}\mathbf{e}_{m}^{\mathrm{ T}}, \tag{15}\]  
where \(\mathbf{H}_{m}\in\mathbb{R}^{m\times m}\), and \(\mathbf{e}_{m}=[0,\ldots,0,1]^{\mathrm{T}}\in\mathbb{R}^{m}\). Now, the augmented Hessenberg upper matrix, \(\bar{\mathbf{H}}_{m}\in\mathbb{R}^{(m+1)\times m}\), can be formulated as  
\[\bar{\mathbf{H}}_{m}=\left[ \begin{array}{cccc}\mathbf{H}_{m}\\ h_{m+1,m}\mathbf{e}_{m}^{\mathrm{T}}\end{array} \right]=\left[ \begin{array}{ ccccc}h_{11}&h_{12}&\ldots&h_{1m}\\ h_{21}&h_{22}&\ldots&h_{2m}\\ h_{32}&\ldots&h_{3m}\\ \ddots&&\vdots\\ &&h_{m,m-1}&h_{mm}\\ 0&\ldots&0&h_{m+1,m}\end{array} \right]. \tag{16}\]  
According to [2], the Algorithm 2 method is given as follows. ```
1:Give \(m_{0}\), \(\mathbf{x}_{0}\), and \(\varepsilon\)
2:Do \(m=m_{0},\ldots\) (\(k=m-m_{0}\)), until \(\|\mathbf{r}_{k}\|<\varepsilon\)
3:\(\mathbf{r}_{k}=\mathbf{b}-\mathbf{Ax}_{k}\)
4:\(\mathbf{v}_{1}^{k}=\frac{\mathbf{r}_{k}}{\|\mathbf{r}_{k}\|}\)
5:\(\mathbf{V}_{k}=[\mathbf{v}_{1}^{k},\ldots,\mathbf{v}_{m}^{k}]\) (by Arnoldi process)
6:Solve \((\mathbf{H}_{k}^{\mathrm{T}}\mathbf{H}_{k})\mathbf{y}_{k}=\|\mathbf{r}_{k}\| \mathbf{\Omega}_{k}^{\mathrm{T}}\mathbf{e}_{1}\)
7:\(\mathbf{x}_{k+1}=\mathbf{x}_{k}+\mathbf{V}_{k}\mathbf{y}_{k}\)
```  
**Algorithm 2**GMRES  
```
1:Give \(m_{0}\), \(\mathbf{x}_{0}\), and \(\varepsilon\)
2:Do \(m=m_{0},\ldots\) (\(k=m-m_{0}\)), until \(\|\mathbf{r}_{k}\|<\varepsilon\)
3:\(\mathbf{r}_{k}=\mathbf{b}-\mathbf{Ax}_{k}\)
4:\(\mathbf{v}_{1}^{k}=\frac{\mathbf{r}_{k}}{\|\mathbf{r}_{k}\|}\)
5:\(\mathbf{V}_{k}=[\mathbf{v}_{1}^{k},\ldots,\mathbf{v}_{m}^{k}]\) (by Arnoldi process)
6:Solve \((\mathbf{H}_{k}^{\mathrm{T}}\mathbf{H}_{k})\mathbf{y}_{k}=\|\mathbf{r}_{k}\| \mathbf{\Omega}_{k}^{\mathrm{T}}\mathbf{e}_{1}\)
7:\(\mathbf{x}_{k+1}=\mathbf{x}_{k}+\mathbf{V}_{k}\mathbf{y}_{k}\)
```  
**Algorithm 3**GMRES  
In the above, \(\mathbf{x}_{k}\) is the \(k\)th step value of \(\mathbf{x}\); \(\mathbf{r}_{k}\) is the \(k\)th residual vector; \(\mathbf{y}_{k}\) is the vector of \(m\) expansion coefficients used in \(\mathbf{V}_{k}\mathbf{y}_{k}\); \(\mathbf{e}_{1}\) is the first column of \(\mathbf{I}_{m+1}\); \(\mathbf{V}_{k}\) denotes the \(k\)th step \(\mathbf{V}\) in Equation (13); \(\bar{\mathbf{H}}_{k}\in\mathbb{R}^{(m+1)\times m}\) is the \(k\)th step augmented Hessenberg upper matrix in Equation (16); and \(\mathbf{V}_{k}\mathbf{y}_{k}\) is the \(k\)th step descent vector.