, 25 min read

Stability Regions for Tischer's Formulas

Ten years after Tendler's PhD in 1973, Peter Tischer finished his PhD thesis in 1983. He developed an array of cyclic multistep formulas, which are all stiffly stable. While Tendler found his formulas by guessing and experimenting, Tischer computed his formulas according the following objectives:

  1. The extraneous roots at the origin should be equal to zero (as with the Adams formulas).
  2. The roots at infinity should be equal to zero (as with the BDF).
  3. The formulas should exhibit better stiff-stability properties, order by order, than the BDF.
  4. The leading coefficients of the multistep formulae should not vary within a cycle.
  5. The leading truncation error coefficients of the multistep formulae used in the cycle should not be "large".

Tischer used the nonlinear equation solver ZSYSTM from IMSL to solve his optimization problem. ZSYSTM is:

Determination of a root of a system of N simultaneous nonlinear equations in N unknowns, f(x)=0, in vector form

Tischer restricted himself to only two stages. The formulas were later implemented in a program called ODIOUS. Program ODIOUS was compared against LSODE in Tischer/Gupta (1985).

Tischer, Peter E.: “The Cyclic Use of Linear Multistep Formulas for the Solution of Stiff Differential Equations”, Ph.D. Thesis, Department of Computer Science, Monash University, Clayton, Victoria, Australia, August 1983, x+180 S.

Tischer, Peter E. und Sacks-Davis, Ron: “A New Class of Cyclic Multistep Formulae for Stiff Systems”, SIAM Journal on Scientific and Statistical Computing, Vol 4, No 4, December 1983, pp.733—747.

Peter Tischer and G.K. Gupta: “An evaluation of some new cyclic linear multistep formulas for stiff ODEs”, ACM Transactions on Mathematical Software, Vol. 11, No. 3, pages 263–27, 01-Sep-1985

Below table summarizes the Widlund-α-wedge. BP73 denotes the block-implicit methods from Bickart/Picel (1973).

p TENDLER BDF ODIOUS BP73
1 90.00 90.00 90.00 90.0
2 90.00 90.00 90.00 90.0
3 89.43 86.03 90.00 88.9
4 80.88 73.35 90.00 87.7
5 77.48 51.84 86.64 85.5
6 63.25 17.84 76.32 82.7
7 33.53 * 57.66 79.5
8 * * 22.15 76.0
9 * * * 72.5
10 * * * 69.6

Here we compute these values by using the QZ algorithm. The program stabregion has a command line flag -s for the Tischer/Sacks-Davis formulas. See Stability Regions for BDF and Tendler's Formulas.

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

1. The stability regions. You can hover over the diagrams and see the values.

2. stabregion program The formulas were entered like so.

formula_t F[] = {
    . . .
    {
        "Tischer2", 2, 2, 2,	// name, p, k, l
        (double[]){
        0.2713503499466539, S * 0.2713503499466539,
        -1.271350349946654, S * -1.271350349946654,
        1, -1 + S,
        0, 1,
        // --------
        -0.06067517497332695, -0.04894502624599904 + S * (-0.06067517497332695),
        0.2143248250266731, 0.1728900524919981 + S * 0.2143248250266731,
        0.575, 0.3010549737540010 + S * 0.575,
        0, 0.575 }
    },
    {
        "Tischer3", 3, 3, 2,	// name, p, k, l
        (double[]){
        -0.7156809323463300, S * (-0.7156809323463300),
        2.421409496232843, S * 2.421409496232843,
        -2.705728563886513, 0.4195749238763092 + S *(-2.705728563886513),
        1, -1.419574923876309 + S,
        0, 1,
        // --------
        -0.8629888978651531, 1.894838801355351+ S * (-0.8629888978651531),
        3.166634912306544, -6.952885160409694+ S * 3.166634912306544,
        -4.013693645981575, 9.231466454815180 + S * (-4.013693645981575),
        1.72, -5.312995019637147 + S * 1.72,
        0, 1.72 }
    },
    . . .
};

stabregion performs a check on the order. Checking the correct order for the order eight method.

Tischer8, p=8, k=8, l=2
               0.4453       0.0000
              -3.8592      -0.0000
              14.7164      -0.1163
             -32.2732       1.0075
              44.5395      -3.8279
             -39.6177       8.3029
              22.1685     -11.1659
              -7.1197       9.3699
               1.0000      -4.5702
               0.0000       1.0000
               0.4822      -1.3844
              -4.1369      11.8761
              15.6598     -45.0792
             -34.2186      99.2938
              47.3011    -139.7913
             -42.4514     130.5230
              24.2093     -81.1853
              -8.0285      33.0004
               1.1800      -8.4084
               0.0000       1.1800
rho_0(1)           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              0.000000000           0.000000002    <
rho_7              0.000000002           0.000000004    <
rho_8             -0.000000002           0.000000045    <--
rho_9        -268194.357417837      200351.482900381    <-----

One can notice that starting with consistency order of six the truncation error is no longer neglible.