## 6 Numerical Methods and Algorithms
### Models at the Macro-Scale
#### 6.1.2 Solution of the \"Discrete in Space\"
Then, condition (129) (or equivalently the condition (131)) is satisfied by \(\tilde{\mathbf{x}}_{N}=\mathbf{x}_{0}+\mathbf{V}_{N}\tilde{\mathbf{\vartheta}}\) if, and only if, \(\tilde{\mathbf{\vartheta}}\) is the solution to the following minimum problem (see Proposition 5.3 in Saad [152]):\[\tilde{\mathbf{\vartheta}}=argmin_{\mathbf{\vartheta}\in\mathcal{K}_{N}}J_{N}(\mathbf{\vartheta}). \tag{134}\]  
A schema for the GMRES iterative algorithm, useful to compute the approximation \(x_{N}\) of the solution for problem (125), is represented in Algorithm 5. ```
1:procedureGMRES(\(\mathbf{A}\), \(\mathbf{y}\), \(\mathbf{x}_{0}\), \(N\), \(\mathbf{x}_{N}\))
2:Input:\(\mathbf{A}\), \(\mathbf{x}_{0}\), \(N\)
3:Output:\(\mathbf{x}_{N}\)
4:\(\mathbf{r}_{0}\leftarrow\)Compute \(\mathbf{r}_{0}=\mathbf{A}\mathbf{x}_{0}-\mathbf{y}\)
5:\(\mathbf{V}_{0}\leftarrow\)Assign \(\mathbf{[r_{0}]}\)
6:for\(n=1\) to \(N\)do
7:\(\mathbf{V}_{n}\leftarrow\)Compute an orthonormal basis \(\mathbf{[}V_{n-1},\mathbf{v}_{n}]\) for \(\mathcal{K}_{n}(\mathbf{A},\mathbf{r}_{0})\)
8:\(\mathbf{\vartheta}_{n}\leftarrow\)Compute \(\tilde{\mathbf{\vartheta}}_{n}=argmin_{\mathbf{\vartheta}\in\mathcal{K}_{N}}J_{n}( \mathbf{\vartheta})\)
9:\(\mathbf{u}_{n}\leftarrow\)Compute \(\mathbf{x}_{n}=\mathbf{x}_{n-1}+V_{n}\tilde{\mathbf{\vartheta}}_{n}\)
10:endfor
11:endprocedure
```  
**Algorithm 5** The GMRES iterative algorithm. Different methods can be used to perform steps at line 7 of Algorithm 5. The most common ones are related with the Gram-Schmidt or Householder procedures, which both compute, at the step \(n\), both the matrix \(V_{n}\) and the \((n+1)\times n\) upper Hessenberg matrix (see [153] for the definition of upper Hessenberg matrix) \(\bar{\mathbf{H}}_{n}\), for which the following relation is valid [152]:  
\[\mathbf{A}\mathbf{V}_{n}=\mathbf{V}_{n+1}\bar{\mathbf{H}}_{n}. \tag{135}\]  
Thanks to Equation (135) (see Proposition 6.5 in Saad [152]), the function \(J_{n}(\mathbf{\vartheta})\) can be rewritten as  
\[\text{Find }\delta\in\mathcal{K}_{N}\text{, such that }\mathbf{r}_{0}-\mathbf{A}\delta\perp \mathcal{L}_{N}. \tag{129}\]0  
where \(\mathbf{c}\) is the constant \(n+1\) vector defined as \(\mathbf{c}=[\|\mathbf{r}_{0}\|_{2},0,\ldots,0,0]^{T}\). The solution to the minimum problem at line 8 of Algorithm 5 is easy and inexpensive to compute since it requires the solution of an \((n+1)\times n\) least-squares problem where \(n\) is typically small and where the coefficient matrix \(\bar{\mathbf{H}}_{n}\) is an upper triangular matrix. Although KS methods are well founded theoretically, they are all likely to experience slow convergence when dealing with problems arising from applications where the numerical features of the coefficient matrix \(\mathbf{A}\) are not \"_good_\". The matrix's \"_condition number_\" is the primary parameter that describes its numerical \"goodness\". The condition number of a square matrix \(\mathbf{A}\) is defined as  
\[\text{Find }\delta\in\mathcal{K}_{N}\text{, such that }\mathbf{r}_{0}-\mathbf{A}\delta\perp \mathcal{L}_{N}. \tag{129}\]1  
In numerical analysis, the condition number of a matrix \(\mathbf{A}\) is a way of describing how well or badly a linear system with \(\mathbf{A}\) as a coefficient matrix could be numerically solved in an effective way: if \(\kappa(\mathbf{A})\) is small, the problem is well-conditioned; otherwise, the problem is rather ill-conditioned and it can hardly be solved numerically in an effective way [147]. In these situations, preconditioning is essential to the effectiveness of Krylov subspace algorithms. Preconditioners, in general, are modifications to initial linear systems that make them \"_easier_\" to solve. Identifying a preconditioning matrix \(\mathbf{M}\) is the first stage in the preconditioning process. The matrix \(\mathbf{M}\) can be defined in a variety of ways, but it must meet a few minimal requirements.