## 7 Algorithms for HPC Systems in the Exascale Era
### Parallel Solvers for Exascale Computing
#### 7.2.2 Composite Nonlinear Solver
Among these kinds of methods, we introduce the _\"Nonlinear Additive Schwarz Method (NASM)\"_[178] for its properties concerning computational \"granularity,\" which is desirable in a parallel computing context. ```
1:procedureNewtonKrylovSolver(\(\mathbf{F}\), \(\mathbf{b}\), \(\mathbf{u}_{0}\), \(N\), \(\mathbf{u}_{N}\))
2:Input:\(\mathbf{G}\), \(\mathbf{b}\), \(\mathbf{u}_{0}\), \(N\)
3:Output:\(\mathbf{u}_{N}\)
4:for\(n=0\) to \(N-1\)do
5:\(\mathbf{r}(\mathbf{n}_{n})\leftarrow\) Compute \(\mathbf{F}(\mathbf{u}_{n})-\mathbf{b}\)
6:\(J_{n}\leftarrow\) Compute \(J_{n}\)
7:\(\Delta\mathbf{u}_{n}\leftarrow\) Solve \(J_{n}\Delta\mathbf{u}_{n}=\mathbf{r}(\mathbf{u}_{n})\triangleright\) The linear system is solved by a Krylov method
8:\(\mathbf{u}_{n+1}\leftarrow\) Compute \(\mathbf{u}_{n+1}=\mathbf{u}_{n}+\lambda\Delta\mathbf{u}_{n}\) \(\triangleright\)\(\lambda\) is determined by line search
9:endfor
10:endprocedure
```  
**Algorithm 11** The algorithm implementing the \"Newton-Krylov methods\" for the approximate solution of Equation (194). **Definition 4**. : _The Nonlinear Additive Schwarz Method (NASM)_  
_Let us consider the solution of problem (194) where \(\mathbf{u}\in\Re^{n}\), and let \(\{\mathcal{A}_{d}\}_{d=1,...,N}\) be a set of subsets of \(\mathcal{I}=\{1,\ldots,n\}\) whose overall union coincides with \(\mathcal{I}\) (i.e., \(\bigcup_{d=1,...,N}\mathcal{I}_{d}=\mathcal{I}\)). Each index subset \(\mathcal{I}\) defines a subdomain \(\mathfrak{D}_{d}\subseteq\Re^{n_{d}}\) of dimension \(n_{d}=|\mathcal{I}_{d}|\) of \(\Re^{n}\)._  
_Let us consider the two sets \(\{\mathbf{R}_{d}\}_{d=1,...,N}\) and \(\{\mathbf{P}_{d}\}_{d=1,...,N}\). of \"restriction\" and \"_prolongation\" operators, respectively, with the assumption that \(\mathbf{R}_{d}\) and \(\mathbf{P}_{d}\) satisfy \(\sum_{d=1,...,N}\mathbf{P}_{d}\mathbf{R}_{d}=I\)._  
_Examples for \(\mathbf{R}_{d}\) and \(\mathbf{P}_{d}\), related with disjoint subsets \(\mathcal{I}_{j}\) (i.e., \(\mathcal{I}_{j}\cap\mathcal{I}_{i}=\emptyset\), \(\forall i\
eq j\)), are, respectively,_  
\[\mathbf{R}_{d}:\mathbf{u}\in\Re^{n}\mapsto\mathbf{u}^{d}\in\Re^{n_{d}}\]  
_where \(\mathbf{u}^{d}=\{\mathbf{u}_{k}\}_{k\in\mathcal{I}_{d}}^{T}\)_ \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Composite** & \\ \hline
**Type** & **Statement** & **Abbreviation** \\ \hline Additive & \(\mathbf{u}_{i+1}=\mathbf{u}_{i}+\alpha_{M}(M(\mathbf{F},\mathbf{u}_{i},\mathbf{b})-\mathbf{u}_{i})+a_{N} (N(\mathbf{F},\mathbf{u}_{i},\mathbf{b})-\mathbf{u}_{i})\) & \(M+N\) \\ Multiplicative & \(\mathbf{u}_{i+1}=M(\mathbf{F},N(\mathbf{F},\mathbf{u}_{i},\mathbf{b}),\mathbf{b})\) & \(M*N\) \\ \hline \multicolumn{3}{c}{**Preconditioning**} \\ \hline
**Type** & **Statement** & **Abbreviation** \\ \hline Left & \(\mathbf{u}_{i+1}=M(\mathbf{u}_{i}-N(\mathbf{F},\mathbf{u}_{i},\mathbf{b}),\mathbf{u}_{i},\mathbf{b})\) & \(M-_{i}N\) \\ Right & \(\mathbf{u}_{i+1}=M(\mathbf{F}(N(\mathbf{F},\mathbf{u}_{i},\mathbf{b}),\mathbf{u}_{i},\mathbf{b}))\) & \(M-_{R}N\) \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Nonlinear composite combinations and preconditioning given outer and inner solver \(M\) and \(N\). \[\mathbf{P}_{d}:\mathbf{u}^{d}\in\Re^{n_{d}}\mapsto\mathbf{u}\in\Re^{n}\qquad\qquad\qquad\text{ where }\mathbf{u}_{k}=\left\{ \begin{array}{ll}\mathbf{u}_{k}^{d}&\text{if }k\in\Im_{d}\\ 0&\text{if }k\
otin\Im_{d}\end{array}