11th August 2013, 2 min read

Design Notes on System for the Analysis of Order- and Stepsize Changes for Cyclic Composite Multistep Methods

Original post is here eklausmeier.goip.de/blog/2013/08-11-design-notes-on-system-for-the-analysis-of-order-and-stepsize-changes-for-cyclic-composite-multistep-methods.

For the numerical solution of the ordinary differential equation, initial value problem

y^{'} = f (t, y), y (t_{0}) = y_{0},

one can use a cyclic composite multistep method of the form

\sum_{i = 0}^{m} A_{i} Y_{k + i} = h \sum_{i = 0}^{m} B_{i} Y_{k + i}^{'}, A_{i}, B_{i} \in R^{ℓ \times ℓ},

and

Y_{k} = (\begin{matrix} y_{k ℓ + 1} \\ ⋮ \\ y_{k ℓ + ℓ} \end{matrix}), Y_{k}^{'} = (\begin{matrix} y_{k ℓ + 1}^{'} \\ ⋮ \\ y_{k ℓ + ℓ}^{'} \end{matrix}), y_{i} = y (t_{i}), y_{i}^{'} = f (t_{i}, y_{i}) .

$y^{'}$ denotes the derivative of $y$ , $h$ is the stepsize, $ℓ$ is the cycle length. The stepsize does not need to be kept constant. If the stepsize changes one can still use above formula but adds a sub-cycle of the form

\tilde{y_{i}} = linear combination / interpolation polynomial with previous grid elements

Some notes:

Individual stages of the cyclic composite multistep method do not have to be of same order.
Some stages can be explicit, some implicit.

The method can still be stiffly stable even if some stages are explicit, assuming that the explicit stages are not used for advancing the solution.

For the test equation

y^{'} = λ y, λ \in C,

one has to analyze the roots of the determinant of the matrix polynomial

det Q (μ, H) = det [\sum_{i = 0}^{m} (A_{i} - H B_{i}) μ^{i}], H = λ h .

The analysis system or workbench we are after will now

use the companion matrix to solve $det Q (μ, H) = 0$
use $\tilde{y_{i}}$ for the interpolation step, i.e., stepsize change
order change is trivial
calculate Widlund wedge
picture of 3D images of $det Q (μ, H)$ and conic section of $det Q (e^{i φ}, H) = 0, > φ \in [0, 2 π]$
propose a list of stepsize and order changes, which can be edited easily, possibly with mouse pointer or direct edit
1. linear increase / descrease
2. sawtooth / zig-zag
3. Sierpinski shape
ideally be able to change some of the $A_{i}, B_{i}$ or automatically tune them with a minimization procedure according some criteria, like
1. Widlund wedge
2. maximal stepsize possible not exceeding minimum Widlund wedge
3. sum of absolute values of stage coefficients

There are still a number of open issues and several decisions have to be taken:

use Octave, Maxima, or C
use OpenGL, or Gnuplot
incorporate CUDA in C or Octave (see: Drop-in Acceleration of GNU Octave), if dimension of companion matrix becomes large and calculations therefore slow

Added 02-Jun-2020: At the time of posting mid 2013 the Julia programming language was just almost freshly born. Now it fits in nicely here: It offers speed, graphics, and support for CUDA.