Parallel iteration of the extended backward differentiation formulas

The extended backward differentiation formulas (EBDFs) and their modified form (MEBDF) were proposed by Cash in the 1980s for solving initial value problems (IVPs) for stiff systems of ordinary differential equations (ODEs). In a recent performance evaluation of various IVP solvers, including a variable-step-variable-order implementation of the MEBDF method by Cash, it turned out that the MEBDF code often performs more efficiently than codes like RADAUS, DASSL and VODE. This motivated us to look at possible parallel implementations of the MEBDF method. Each MEBDF step essentially consists of successively solving three non-linear systems by means of modified Newton iteration using the same Jacobian matrix. In a direct implementation of the MEBDF method on a parallel computer system, the only scope for (coarse grain) parallelism consists of a number of parallel vector updates. However, all forward-backward substitutions and all right-hand-side evaluations have to be done in sequence. In this paper, our starting point is the original (unmodified) EBDF method. As a consequence, two different Jacobian matrices are involved in the modified Newton method, but on a parallel computer system, the effective Jacobian-evaluation and the LU decomposition costs are not increased. Furthermore, we consider the simultaneous solution, rather than the successive solution, of the three non-linear systems, so that in each iteration the forward-backward substitutions and the right-hand-side evaluations can be done concurrently. A mutual comparison of the performance of the parallel EBDF approach and the MEBDF approach shows that we can expect a speed-up factor of about 2 on three processors.