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

  • $\begingroup$ Probably not. See also this question and Geoff Oxberry's answer. $\endgroup$
    – wim
    Dec 17, 2018 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, 2018 at 23:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.