Confusion regarding the Adam-Moulton and Backwards Differentiation Formula (BDF) of the VODE solver

Question

I am exploring the Method of Lines as a way of time stepping semi-discretised PDEs with ODE time-integration solvers. For an excellent introduction to this technique see the scholarpedia.org article. A popular ODE solver is VODE from http://www.netlib.org/ode/vode.f. It is also possible to access this solver by the scipy.integrate.ode set of solvers if you use Python.

I wish to solve an extremely stiff set of non-linear PDEs so I am interested in implicit methods because they offer stability and unrestricted time-step. I had planned to time-step the nonlinear system using a Newton iteration at every time step. However, I recently became aware of the Method of Lines (MOL).

The MOL technique seems a very powerful technique for time stepping semi-discretised PDEs because one can rely on robust and well tested ODE solver code that are well integrated with modern languages such as Python etc.

Question 1 How does the standard implicit Newton time-stepping method relate to the implicit Adams-Moulton technique used by the VODE solver?

To my current understanding the only difference is that Adams-Moulton is a generalisation of the implicit backwards Euler method which is include previous time points in the time integration up to a require order.

Question 2 Does the algorithm work like this?

1. Solve the nonlinear system with $\theta$-method to give $u^{n+1}$, $$ w^{\prime}(u^{n+1}, u^{n}) = b_1 F(u^{n+1}) + b_0 F(u^{n}) $$

2. Solve the system for the solution variable at the next time step $u^{n+2}$ but include the pervious value and appropriate coefficients to improve the time integration, $$ w^{\prime}(u^{n+2}, u^{n+1}) = b_2 F(u^{n+2}) + \underbrace{b_1 F(u^{n+1}) + b_0 F(u^{n})}_{\text{known}} $$

3. Continue this processes up until the desired order ($N$) at which point we can start dropping the older terms, $$ w^{\prime}(u^{n+k}, u^{n+k-1}) = b_k F(u^{n+k}) + \underbrace{b_{k-1} F(u^{n+k-1}) + \,\,...\,\, +\, b_{k-N} F(u^{n+k-N})}_{\text{known}} $$

Question 3 This seems almost identical to the BDF approach, how does these approaches differ?

Question 4 For stiff nonlinear system of ODEs an implicit scheme (such as Newton iteration time-stepping) seems to be what people recommend. However, for a stiff ODE system why are Backwards Differentiation Formula (BDF) recommended and not Adams-Moulton?

---

Perhaps some of these equations don't make sense because I am confused regarding the basic technique, but I will be happy to be put straight.

Answer 1

To answer your questions in order:

1. Any implicit method for solving an ordinary differential equation involves solving a system of nonlinear equations. You can do this through variants of Newton's method, successive substitution, full approximation scheme, or any other approach that solves systems of nonlinear equations. (The caveat is, of course, depending on the problem, some methods work better than others, and some may not work at all. The case of successive substitution is a good example.)

2. You are describing, more or less, how some implicit linear multistep methods work. Adams-Moulton and BDF methods are both linear multi step methods. For more background on linear multi step methods, check out the book by Ascher and Petzold, the two-volume work of Hairer and Wanner, Butcher's book, or the book by Lambert (all on numerical methods for ODEs).

3. BDF methods have different coefficients than Adams-Moulton methods, and thus, they also have different stability and accuracy properties. The form of BDF methods is different than the equation you mentioned because, in standard form, many of its coefficients are zero. The Wikipedia articles on BDF methods and linear multistep methods illustrate this distinction nicely.

4. If I remember correctly, BDF methods are recommended because they have large stability regions, but they're by no means the only choice for stiff systems. Rosenbrock methods, implicit Runge-Kutta methods, exponential integrators, and general linear methods can be effective as well, depending on the properties of your ODE right-hand side (and the spectrum of its Jacobian matrix), and whether or not you can effectively precondition any of the linear systems you solve during integration. If your stiff system can be decomposed into stiff and nonstiff components (like a reaction-diffusion equation), then implicit-explicit methods can also be worthwhile. The impression I get is that, due to the high-quality implementations of BDF methods out there, they've become the method of choice for people who just want something to work and don't really care about investigating alternatives or understanding their problem more deeply. They are reliable and accurate, but other algorithmic choices may be faster for a given problem.

Some final thoughts: VODE is really an old version of the CVODE solver in the SUNDIALS suite, and it might be worth using that instead of VODE to benefit from the algorithmic improvements made over the years (like incorporating inexact Newton methods into the nonlinear solves with good error control). Assimulo is a decent Python interface to SUNDIALS. PETSc also implements many of the methods I mentioned above and has a Python interface (called petsc4py), and Trilinos also implements some of those methods and has a Python interface (called PyTrilinos). If you don't think you need the new features, using scipy and VODE is probably good enough; lots of people still use it.