## 7 Algorithms for HPC Systems in the Exascale Era
### Parallel Solvers for Exascale Computing
#### 7.2.2 Composite Nonlinear Solver  
An key part of contemporary simulations is large-scale algebraic solvers for nonlinear problems. Newton's techniques begin with the nonlinear operator's global linearization. After linearization, a huge sparse linear system is produced, and the matrix can be implicitly represented by several _\"matrix-free\"_ techniques or explicitly represented by storing the nonzero coefficients [165]. As a stand-alone solver, Newton's approach has a number of shortcomings. Memory bandwidth and communication limitations are caused by the repetitive linearization construction and solution [174]. According to Brune et al. [174] we consider a collection of solvers for nonlinear equations of the type  
\[\mathbf{F}(\mathbf{u})=\mathbf{b}. \tag{194}\]  
A small set of algorithmic building blocks is shown, which, through composite combinations or nonlinear preconditioning, yield a wide range of solvers with varying convergence and performance characteristics. This is an easily understood comparison to the situation of linear solvers. Implementations of this kind of solvers are available in the PETSc software library and may be brought to bear on many relevant applications. The history of the _\"Portable, Extensible Toolkit for Scientific computing (PETSc)\"_[27; 175] began in the early 1990s and has always focused on the largest-scale parallel systems available at the time. PETSc had the original goal to develop efficient algebraic solvers and provide the ability to use any appropriate solver for any suitable set of PDEs and can be considered one of the most important and widely used mathematical software libraries. New advances in PETSc software library are now available to accomplish the needs of the emerging extreme-scale architecture [176]. Let us express the action of a stationary nonlinear solver that employs the solution technique \(M\) as follows: \(\mathbf{u}_{i+1}=M(\mathbf{F},\mathbf{u}_{i},\mathbf{b})\). A sequence or series of two (or more) solution techniques \(M\) and \(N\), which both provide an approximate solution to (194), make up a nonlinear composite combination. On the other hand, by using inner technique \(N\), nonlinear preconditioning can be expressed as a modification of the function \(\mathbf{F}\). After that, an outer solver \(M\) receives the modified function and uses it to solve the preconditioned system. In general, composite and preconditioning combinations of different solution methods can be considered as an effective acceleration strategy to be used in approximate solutions of Problem (194). A compact representation for nonlinear composite combinations and preconditioning is described in Table 10. A list of solution methods \(M\) that can be considered as building blocks for different combinations are listed in Brune et al. [174]. In these works, we describe just the Newton-Krylov solution methods (_\" NEWT-K\"_) since they are _\"... often the workhorse of simulations requiring solution of nonlinear equations...\"_[174]. In Algorithm 11, the Newton-Krylov solution methods are described: details about the cited (see line 7 in Algorithm 11) \"line search\" algorithm (or other _\"globalization strategies\"_) can be found in Brune et al. [174] or in Pawlowski et al. [177]. Newton-Krylov's basic method is very sensitive to the initial iterate and may diverge if it is not sufficiently close to the solution. Generally, globalization strategies seek directions \(\Delta\mathbf{u}\) and step lengths \(\lambda\) in such a way that such convergence problems can be reduced [177]. An extremely important class of methods comprises nonlinear variants of domain decomposition and multilevel algorithms. The convergence of the decomposition solvers is not guaranteed. Although they may converge, since the decomposition solvers provide additional opportunities for parallelism, the logical extension is to employ them in conjunction with the global solvers as nonlinear preconditioners or accelerators.