Acceleration of Newton-like methods for nonlinear 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 achieved by successive linearization like Newton's method, needs to be fast in order to increase software efficiency. However, one of the obstacles to this speed is precisely the degree of non-linearity of the system under consideration. 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 rate of convergence depends on two problem-specific constants, one of which can be viewed as a measure of local nonlinearity.

Over the last two decades, preconditioning techniques have been introduced to speed up the resolution of nonlinear systems. They rely on solving an equivalent system that is judiciously built by analogy with the linear case. However, unlike the linear case, there is no guarantee that the new system will be more suitable for Newtonian solution than the original one, even though this is generally observed in numerical experiments. This is because, in the linear case, it is the conditioning of the matrix that governs the rate of convergence 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 which scalar quantity has decreased between the old and new systems. So, even if preconditioning works, its foundation remains heuristic.

Based on this observation, we propose to explore transformations of the original system into an equivalent system that is "less nonlinear" in a quantitative sense to be specified in relation to Newton's speed of convergence. To distinguish this approach (which acts only on the external non-linear level) from classical non-linear preconditioning (which acts simultaneously on both the linear and non-linear levels), we introduce the term pre-flattening. The conceptual clarity afforded by separating the two iteration levels would enable us to envisage targeted and relevant avenues of work.

Keywords: nonlinear systems, Newton’s method, rate of convergence, conditioning, preconditioning, nonlinearity measure, preflattening, reactive transport, porous media

Academic supervisors: Quang Huy TRAN (IFPEN) and Clément CANCÈS (INRIA Lille)

Other supervisor: Ibtihel BEN GHARBIA (IFPEN)

Doctoral School: ED STIC 580, University Paris-Saclay