2
$\begingroup$

Often when numerically solving nonlinear PDE's using method of lines approach with an implicit integrator a system of nonlinear equations have to be solved. To be more specific, let's say we have simple backward Euler method: \begin{align} y^{n}=y^{n+1}-h f(y^{n+1},t)= G(y^{n+1},t) \end{align} From the available literature, it seems the most common approach is using an Newton-GMRES method to solve the nonlinear system, especially if it is stiff. As far as I can understand GMRES is used because it is a matrix-free method and so also works with vector functions which is good when approximating the Jacobian with finite differences.

My question is then, why not just use the GMRES to solve the initial problem? I see no reason why GMRES couldn't solve this for $y^{n+1}$ when for the Newton-GMRES we solve the system: \begin{align} H(y^{n+1}_k) &= y^{n+1}_k-y^{n}-h f(y^{n+1}_k,t)\rightarrow 0 \text{ for } k\rightarrow \infty\\ Jv &\simeq \frac{H(y^{n+1}_k+\epsilon v)-H(y^{n+1}_k))}{\epsilon} \simeq -H(y^{n+1}_k)\\ y^{n+1}_{k+1}&=y^{n+1}_k+v \end{align} where the GMRES is used for the second part to find $v$. I don't see why solving for $v$ with GMRES followed by the Newton step should be easier/better than solving the general system in the top for $y^{n+1}$ using GMRES? Does the finite difference approximation to the Jacobian have better properties compared the the general system $y^n=G(y^{n+1},t)$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

The reason is that GMRES can only be used for solving linear equations, i.e. equations of the form $Ax=b$, where $A$ is some matrix and $x,b$ are vectors. What GMRES does, essentially, is it approximates multiplication by the matrix $A^{-1}$ using a matrix polynomial of $A$.

In this case (I assume) $f(y^{n+1},t)$ is not necessarily linear in the vector $y^{n+1}$, and so $y^n=G(y^{n+1},t)$ can't be written in the form $y^n=A(t)y^{n+1}$, where $A(t)$ is a matrix-valued function of time. So you can't use GMRES directly.

The "Newton step" is actually the formation of the linear system of equations with the Jacobian; the point of Newton's method is that it approximates the solution of a nonlinear equation with the solution of a sequence of linear equations. GMRES is just a tool that is used to implement Newton's method.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But isn't the function evaluations $H(y^{n+1}_k(+\epsilon v))$ used in the Jacobian approximation also non-linear? Or is this OK, since it approximates a linear operator J and if so couldn't you argue that there is some linear operator $L$ such that $Ly^{n+1}\simeq G(y^{n+1},t)$ such that you in effect solve that system instead? $\endgroup$
    – Rasmus
    Jun 4, 2019 at 7:54
  • 1
    $\begingroup$ Approximating $G(y^{n+1},1)$ with a linear operation $Ly^{n+1}$ is kind of what you're doing by using the Jacobian; what you're doing here is you're saying that $$ H(y^{n+1}_k)=G(y^{n+1}_k,t)-y^{n}\approx H(y^{n+1}_{k-1})+J(y^{n+1}_{k-1})(y^{n+1}_{k}-y^{n+1}_{k-1}) $$ By taking the Jacobian of $H$ evaluated at $y^{n+1}_{k-1}$, you're linearizing the function $H$ around the point $y^{n+1}_{k-1}$. You can't do this just once, though; that linear approximation is only valid in the neighborhood around the point $y^{n+1}_{k-1}$, so you need to iterate in $k$ to solve the problem. $\endgroup$
    – bgav
    Jun 4, 2019 at 18:27
  • $\begingroup$ Ahh, i see. That makes sense to me, thank you very much :) $\endgroup$
    – Rasmus
    Jun 5, 2019 at 6:44

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.

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