# GMRES vs Newton-GMRES for Solving nonlinear PDE's

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

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.
• 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? – Rasmus Jun 4 '19 at 7:54
• 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. – bgav Jun 4 '19 at 18:27