, 21 min read
Stability Regions for Donelson and Hansen Formulas
In the seminal paper Cyclic Composite Multistep Predictor-Corrector Methods the two authors Donelson and Hansen derive cyclic multistep methods of high order and break the first Dahlquist barrier.
Their formulas have the following properties.
| Method | stages ℓ | steps k | order p |
|---|---|---|---|
| 1 | 3 | 3 | 5 |
| 2 | 3 | 3 | 6 |
| 3 | 3 | 3 | 6 |
| 4 | 2 | 3 | 5 |
| 5 | 4 | 4 | 7 |
| 6 | 4 | 4 | 8 |
typedef struct {
const char *name;
const int p; // order (for information only)
const int k; // number of start steps, 2*(k+l) = number of rows of a[]
const int l; // cycle length, i.e., column count of a[]
double *a; // transpose of A_i and B_i matrices in a single matrix
} formula_t;
formula_t F[] = {
. . .
{
"DonelsonHansen1", 5, 3, 3, // name, p, k, l
(double[]){
0, 0, 0,
-57, 1083, 0,
24, -456, 0,
33, -1347, -57,
0, 720, 24,
0, 0, 33,
// --------
-1, 0, 0,
24, -350, 0,
57, -1347, -1,
10, 456, 24,
0, 251, 57,
0, 0, 10 }
},
{
"DonelsonHansen2", 6, 3, 3, // name, p, k, l
(double[]){
-11, 0, 0,
-27, 188, 0,
27, -36, 25,
11, -252, -63,
0, 100, -9,
0, 0, 47,
// --------
3, 0, 0,
27, -60, 0,
27, -252, -9,
3, 36, -9,
0, 36, 63,
0, 0, 15 }
},
{
"DonelsonHansen3", 6, 3, 3, // name, p, k, l
(double[]){
0, 0, 0,
-57, 136, 0,
24, -117, -283,
33, -144, -306,
0, 125, 531,
0, 0, 58,
// --------
-1, 0, 0,
24, -45, 0,
57, -144, 84,
10, 117, 531,
0, 42, 306,
0, 0, 9 }
},
{
"DonelsonHansen4", 5, 3, 2, // name, p, k, l
(double[]){
0, 0,
-57, 31,
24, -12,
33, -39,
0, 20,
// --------
-1, 0,
24, -10,
57, -39,
10, 12,
0, 7 }
},
{
"DonelsonHansen5", 7, 4, 4, // name, p, k, l
(double[]){
0, 0, 0, 0,
-1360, 13409, 0, 0,
-1350, 30384, 3653, 0,
2160, -55026, -22752, 4550,
550, 2224, -45792, 14160,
0, 9009, 49888, -14850,
0, 0, 15003, -5360,
0, 0, 0, 1500,
// ---------------------------
-9, 0, 0, 0,
456, -3585, 0, 0,
2376, -32904, -1182, 0,
1656, -19008, 1440, -1191,
141, 16008, 49032, -12456,
0, 2529, 42144, -13176,
0, 0, 3906, 744,
0, 0, 0, 459 }
},
{
"DonelsonHansen6", 8, 4, 4, // name, p, k, l
(double[]){
0, 0, 0, 0,
-1360, 4603, 0, 0,
-1350, 1008, -3455657, 0,
2160, -28242, -28102272, 59160,
550, 15728, -5942052, 175440,
0, 6903, 31623488, -201690,
0, 0, 5876493, -55920,
0, 0, 0, 23010,
// ---------------------------------
-9, 0, 0, 0,
456, -1293, 0, 0,
2376, -8136, 789744, 0,
1656, 9936, 15276816, -15543,
141, 16968, 40314888, -159048,
0, 1845, 20558640, -156168,
0, 0, 1449972, 20232,
0, 0, 0, 6867 }
}
}
1. Stability regions. None of the formulas is A(α)-stable or A-stable. In particular, the graph for p=2 looks weird.
2. Error constants per stage.
The C program stabregion performs a check on the order of each stage.
Below are the results of these checks for the Donelson & Hansen methods.
DonelsonHansen1, p=5, k=3, l=3
0.0000 0.0000 0.0000
-57.0000 1083.0000 0.0000
24.0000 -456.0000 0.0000
33.0000 -1347.0000 -57.0000
0.0000 720.0000 24.0000
0.0000 0.0000 33.0000
-1.0000 0.0000 0.0000
24.0000 -350.0000 0.0000
57.0000 -1347.0000 -1.0000
10.0000 456.0000 24.0000
0.0000 251.0000 57.0000
0.0000 0.0000 10.0000
rho_0 0.000000000 0.000000000 0.000000000
rho_1 0.000000000 0.000000000 0.000000000
rho_2 0.000000000 0.000000000 0.000000000
rho_3 0.000000000 0.000000000 0.000000000
rho_4 0.000000000 0.000000000 0.000000000
rho_5 0.000000000 0.000000000 0.000000000
rho_6 -132.000000000 -7212.000000000 -132.000000000 <-----
DonelsonHansen2, p=6, k=3, l=3
-11.0000 0.0000 0.0000
-27.0000 188.0000 0.0000
27.0000 -36.0000 25.0000
11.0000 -252.0000 -63.0000
0.0000 100.0000 -9.0000
0.0000 0.0000 47.0000
3.0000 0.0000 0.0000
27.0000 -60.0000 0.0000
27.0000 -252.0000 -9.0000
3.0000 36.0000 -9.0000
0.0000 36.0000 63.0000
0.0000 0.0000 15.0000
rho_0 0.000000000 0.000000000 0.000000000
rho_1 0.000000000 0.000000000 0.000000000
rho_2 0.000000000 0.000000000 0.000000000
rho_3 0.000000000 0.000000000 0.000000000
rho_4 0.000000000 0.000000000 0.000000000
rho_5 0.000000000 0.000000000 0.000000000
rho_6 0.000000000 -1152.000000000 -288.000000000 <-----
rho_7 -108.000000000 -19728.000000000 -7164.000000000 <-----
DonelsonHansen3, p=6, k=3, l=3
0.0000 0.0000 0.0000
-57.0000 136.0000 0.0000
24.0000 -117.0000 -283.0000
33.0000 -144.0000 -306.0000
0.0000 125.0000 531.0000
0.0000 0.0000 58.0000
-1.0000 0.0000 0.0000
24.0000 -45.0000 0.0000
57.0000 -144.0000 84.0000
10.0000 117.0000 531.0000
0.0000 42.0000 306.0000
0.0000 0.0000 9.0000
rho_0 0.000000000 0.000000000 0.000000000
rho_1 0.000000000 0.000000000 0.000000000
rho_2 0.000000000 0.000000000 0.000000000
rho_3 0.000000000 0.000000000 0.000000000
rho_4 0.000000000 0.000000000 0.000000000
rho_5 0.000000000 0.000000000 0.000000000
rho_6 -132.000000000 -1044.000000000 900.000000000 <-----
rho_7 -1548.000000000 -18216.000000000 20376.000000000 <-----
DonelsonHansen4, p=5, k=3, l=2
0.0000 0.0000
-57.0000 31.0000
24.0000 -12.0000
33.0000 -39.0000
0.0000 20.0000
-1.0000 0.0000
24.0000 -10.0000
57.0000 -39.0000
10.0000 12.0000
0.0000 7.0000
rho_0 0.000000000 0.000000000
rho_1 0.000000000 0.000000000
rho_2 0.000000000 0.000000000
rho_3 0.000000000 0.000000000
rho_4 0.000000000 0.000000000
rho_5 0.000000000 0.000000000
rho_6 -132.000000000 -204.000000000 <-----
DonelsonHansen5, p=7, k=4, l=4
0.0000 0.0000 0.0000 0.0000
-1360.0000 13409.0000 0.0000 0.0000
-1350.0000 30384.0000 3653.0000 0.0000
2160.0000 -55026.0000 -22752.0000 4550.0000
550.0000 2224.0000 -45792.0000 14160.0000
0.0000 9009.0000 49888.0000 -14850.0000
0.0000 0.0000 15003.0000 -5360.0000
0.0000 0.0000 0.0000 1500.0000
-9.0000 0.0000 0.0000 0.0000
456.0000 -3585.0000 0.0000 0.0000
2376.0000 -32904.0000 -1182.0000 0.0000
1656.0000 -19008.0000 1440.0000 -1191.0000
141.0000 16008.0000 49032.0000 -12456.0000
0.0000 2529.0000 42144.0000 -13176.0000
0.0000 0.0000 3906.0000 744.0000
0.0000 0.0000 0.0000 459.0000
rho_0 0.000000000 0.000000000 0.000000000 0.000000000
rho_1 0.000000000 0.000000000 0.000000000 0.000000000
rho_2 0.000000000 0.000000000 0.000000000 0.000000000
rho_3 0.000000000 0.000000000 0.000000000 0.000000000
rho_4 0.000000000 0.000000000 0.000000000 0.000000000
rho_5 0.000000000 0.000000000 0.000000000 0.000000000
rho_6 0.000000000 0.000000000 0.000000000 0.000000000
rho_7 0.000000000 0.000000000 0.000000000 0.000000000
rho_8 -21600.000000000 -880416.000000000 -732672.000000000 -237600.000000000 <-----
DonelsonHansen6, p=8, k=4, l=4
0.0000 0.0000 0.0000 0.0000
-1360.0000 4603.0000 0.0000 0.0000
-1350.0000 1008.0000-3455657.0000 0.0000
2160.0000 -28242.0000-28102272.0000 59160.0000
550.0000 15728.0000-5942052.0000 175440.0000
0.0000 6903.000031623488.0000 -201690.0000
0.0000 0.0000 5876493.0000 -55920.0000
0.0000 0.0000 0.0000 23010.0000
-9.0000 0.0000 0.0000 0.0000
456.0000 -1293.0000 0.0000 0.0000
2376.0000 -8136.0000 789744.0000 0.0000
1656.0000 9936.000015276816.0000 -15543.0000
141.0000 16968.000040314888.0000 -159048.0000
0.0000 1845.000020558640.0000 -156168.0000
0.0000 0.0000 1449972.0000 20232.0000
0.0000 0.0000 0.0000 6867.0000
rho_0 0.000000000 0.000000000 0.000000000 0.000000000
rho_1 0.000000000 0.000000000 0.000000000 0.000000000
rho_2 0.000000000 0.000000000 0.000000000 0.000000000
rho_3 0.000000000 0.000000000 0.000000000 0.000000000
rho_4 0.000000000 0.000000000 0.000000000 0.000000000
rho_5 0.000000000 0.000000000 0.000000000 0.000000000
rho_6 0.000000000 0.000000000 0.000000000 0.000000000
rho_7 0.000000000 0.000000000 0.000000000 0.000000000
rho_8 -21600.000000000 -451872.000000000 -95072832.000000000 -3227040.000000000 <-----
rho_9 -426816.000000000 -12359520.000000000 -4067660160.000000000 -142718112.000000000 <-----