Thesis (in progress): Acceleration of Newton-like methods for nonlinear algebraic systems by preflattening techniques
The numerical discretization of physical models in many fields leads to very large nonlinear algebraic systems. The resolution of these systems, which is usually done by successive linearizations like Newton’s method, must be fast in order to increase the efficiency of the software. However, one of the obstacles to this speed is the more or less strong nonlinearity of the system considered. Indeed, it is known that when the system is linear, Newton’s method converges in a single iteration (at least in exact arithmetic). The best theoretical results available to date for Newton show that its convergence speed depends on two constants specific to the problem, one of which is similar to a measure of local nonlinearity. For about twenty years, preconditioning techniques have been introduced in order to accelerate the resolution of nonlinear systems. They consist in solving an equivalent system judiciously constructed by analogy with the linear case. However, unlike the linear case, it cannot be guaranteed that the new system will be more suitable for Newtonian resolution than the initial one, even if this is generally attested by numerical experiments. The reason is that in the linear case, it is the conditioning of the matrix that governs the convergence speed of the linear solver and we can be sure that the new conditioning will be more favorable. In the nonlinear case, this is no longer the case. We do not know exactly what scalar quantity has decreased between the old system and the new one. Thus, even if nonlinear preconditioning works, its basis remains heuristic. Starting from this observation, we propose to explore transformations of the initial system into an equivalent system that is ’less nonlinear’ in a quantitative sense to be specified in relation to Newton’s convergence speed. To distinguish this approach (which only acts on the external nonlinear level), from classical nonlinear preconditioning (which acts simultaneously on both linear and nonlinear levels), we introduce the term pre-flattening. The conceptual clarity provided by the separation of the two levels of iterations then makes it possible to consider targeted and relevant avenues of work.
