8
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.