How can I precondition a non-linear problem before linearization?

Question

When I think of solving non-linear equations, I generally think of linearizing first, then applying a preconditioner to the linear matrix. The thought occurred to me that it might be possible to condition the non-linear equations BEFORE they are linearized. Are there any general strategies to precondition non-linear equations that are independent of the structure of the system of equations?

Answer 1

Sure, any approximate nonlinear solver can be used as a nonlinear preconditioner. For example, if your system has directional stiffness, you could use a 1D shooting method as a preconditioner. Cai and Keyes' (2002) Nonlinearly preconditioned inexact Newton algorithms provide another useful example.

In PETSc, nonlinear methods such as quasi-Newton, nonlinear conjugate gradients, nonlinear GMRES (aka. Anderson acceleration), and nonlinear Richardson can be used with a nonlinear preconditioner. The nonlinear preconditioner is any other SNES implementation, perhaps a user-defined "shell" implementation.

Answer 2

When using a nonlinear conjugate gradient method to solve a square system $F(x)=0$ by minimizing the residual squared norm $\|F(x)\|_2^2$, it usually pays to precondition the system by means of a linear transformation, e.g., computed by an approximate factorization $LU$ of an approximate Jacobian at the starting point. (Often such an approximate Jacobian is available from a simplification of the problem.) Thus one minimizes instead $\|B F(x)\|_2^2$, where $B=(LU)^{-1}$, and $r=BF(x)$ is computed by solving $LUr=F(x)$.

At more expense (one new approximate factorization per iteration), one can also minimize $B(x)F(x)$.