2
$\begingroup$

Consider a nonlinear system of the form $\boldsymbol{f}(\boldsymbol{x}) = \boldsymbol{0}_{\mathbb{R}^n}$ for $\boldsymbol{x} \in \mathbb{R}^n$, where the function $\boldsymbol{f}$ is given by \begin{equation} \boldsymbol{f}(\boldsymbol{x}) := \boldsymbol{g}(\boldsymbol{x}) + \boldsymbol{\underline{A}} \boldsymbol{x} + \boldsymbol{b} \in \mathbb{R}^n, \quad \boldsymbol{x} \in \mathbb{R}^n. \end{equation} Here, the function $\boldsymbol{g}$ is differentiable. Moreover, the functions $g_i$ depend only on $x_i$, i. e. $\frac{\partial g_i}{\partial x_j} \equiv 0$, $i \neq j$. The matrix $\boldsymbol{\underline{A}} \in \mathbb{R}^{n \times n}$ is large, sparse, non-symmetric, and invertible.

Can we take advantage of the purely diagonal nonlinearity in $\boldsymbol{f}$ somehow when solving the nonlinear system?

The assembly of the Jacobian matrix $\boldsymbol{\underline{J}_f}(\boldsymbol{x}) = \boldsymbol{\underline{J}_g}(\boldsymbol{x}) + \boldsymbol{\underline{A}}$ is cheap since $\boldsymbol{\underline{J}_g}(\boldsymbol{x})$ is a diagonal matrix. Therefore, Newton's method appears to be a natural choice, but other methods are also acceptable.

If we use Newton's method, then I guess my question boils down to whether we can take advantage of the special form of $\boldsymbol{\underline{J}_f}$ when computing the updates $\boldsymbol{\Delta x}$ in each Newton step, $\boldsymbol{\underline{J}_f}(\boldsymbol{x}_k) \boldsymbol{\Delta x} = - \boldsymbol{f}(\boldsymbol{x}_k)$?

$\endgroup$
  • $\begingroup$ Probably not. See also this question and Geoff Oxberry's answer. $\endgroup$ – wim Dec 17 '18 at 23:24
  • $\begingroup$ Nevertheless, you can try to use the $LU$ factorization (with partial pivoting?) of $\boldsymbol{\underline{J}_f}(\boldsymbol{x}_0)$ as a preconditioner for $\boldsymbol{\underline{J}_f}(\boldsymbol{x}_1) \boldsymbol{\Delta x} = - \boldsymbol{f}(\boldsymbol{x}_1)$, and solve this linear system with preconditioned GMRES. This might work well if the non-linear term is relatively small. You can try to use the same preconditioner for computing $\boldsymbol{x}_2$, etc. Recompute the preconditioner if GMRES stops converging after a few Newton steps. $\endgroup$ – wim Dec 17 '18 at 23:41

Your Answer

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

Browse other questions tagged or ask your own question.