## 6 Numerical Methods and Algorithms
### Models at the Macro-Scale
#### 6.1.2 Solution of the \"Discrete in Space\"
The most crucial one is that linear system \(\mathbf{M}\mathbf{x}=\mathbf{b}\) must be cheap to solve because the preconditioned algorithms will need to solve linear systems with coefficient matrix \(\mathbf{M}\) at each stage. Furthermore, \(\mathbf{M}\) should be nonsingular and \"_close_\" to matrix \(\mathbf{A}\) in some sense (i.e., \(\mathbf{M}^{-1}\mathbf{A}\approx\mathbf{I}\)) [152]. For example, if the preconditioner \(\mathbf{M}\) is applied from the left, the modification leads to the preconditioned linear system  
\[\text{Find }\delta\in\mathcal{K}_{N}\text{, such that }\mathbf{r}_{0}-\mathbf{A}\delta\perp \mathcal{L}_{N}. \tag{129}\]2  
whose coefficients matrix \(\mathbf{M}^{-1}\mathbf{A}\) should have better numerical features than \(\mathbf{A}\) because it is \"_near_\" the identity matrix \(\mathbf{I}\). An incomplete factorization of the original matrix \(\mathbf{A}\) is one of the easiest ways to define a preconditioner. This involves taking into account the formula \(\mathbf{A}=\mathbf{L}\mathbf{U}-\mathbf{R}\), in which \(\mathbf{R}\) represents the residual or factorization error and \(\mathbf{L}\) and \(\mathbf{U}\) represent the lower and upper portions of \(\mathbf{A}\), respectively, with the same nonzero structure. Calculating this incomplete factorization, often known as \(ILU(0)\), is not too difficult or expensive. More sophisticated preconditioners are available, such as the preconditioners based on Domain Decomposition Methods and those based on Multigrid Methods (i.e., see [152] for the basic panoramic of such tools). It is worth mentioning that if the matrix \(\mathbf{A}\) is symmetric and positive definite, then specialized algorithms exist in the context of KSM: the Conjugate Gradient (CG) method is the most famous among those [152]. **Hierarchical/Multilevel methods**: When solving linear systems resulting from discretized partial differential equations (PDEs), preconditioned Krylov subspace algorithms tend to converge more slowly as the systems get bigger. There is a significant loss of efficiency because of this decline in the convergence rate. The convergence rates that the Multigrid method class can achieve, on the other hand, are theoretically independent of the mesh size. Discretized elliptic PDEs are the primary focus of Multigrid methods, which distinguish them significantly from the preconditioned Krylov subspace approach. Later, the technique was expanded in many ways to address nonlinear PDE problems as well as problems not described by PDEs [152]. The most important contribution in this sense is related to the Algebraic Multigrid (AMG) [154]. The main ingredients of multilevel methods to solve (125) are as follows. 1. A hierarchy \[\text{Find }\delta\in\mathcal{K}_{N}\text{, such that }\mathbf{r}_{0}-\mathbf{A}\delta\perp \mathcal{L}_{N}. \tag{129}\]3 (138) of \(H\) problems along with restriction \(\mathbf{I}^{h}_{h+1}\) and prolongation \(\mathbf{I}^{h+1}_{h}\) operators to move between levels, where \[\text{Find }\delta\in\mathcal{K}_{N}\text{, such that }\mathbf{r}_{0}-\mathbf{A}\delta\perp \mathcal{L}_{N}. \tag{129}\]4 (139) and where \[\text{Find }\delta\in\mathcal{K}_{N}\text{, such that }\mathbf{r}_{0}-\mathbf{A}\delta\perp \mathcal{L}_{N}. \tag{129}\]5 (140) \[\text{Find }\delta\in\mathcal{K}_{N}\text{, such that }\mathbf{r}_{0}-\mathbf{A}\delta\perp \mathcal{L}_{N}. \tag{129}\]6 (141) \[\text{Find }\delta\in\mathcal{K}_{N}\text{, such that }\mathbf{r}_{0}-\mathbf{A}\delta\perp \mathcal{L}_{N}. \tag{129}\]7 (142) with \[\text{Find }\delta\in\mathcal{K}_{N}\text{, such that }\mathbf{r}_{0}-\mathbf{A}\delta\perp \mathcal{L}_{N}. \tag{129}\]8 for each \(h=0,\ldots,H-1\); 2. A relaxation operator, \(S\left(\mathbf{A}_{h},\mathbf{f}^{h},\mathbf{f}^{h}_{0},\mathbf{b}^{h}\right)\), for \"_smoothing_\".