Parallel iteration of the extended backward differentiation formulas

The extended backward differentiation Formulas (EBDFs) and their modified f orm (MEBDF) were proposed by Cash in the 1980s for solving initial value pr oblems (IVPs) for stiff systems of ordinary differential equations (ODEs). In a recent performance evaluation of various IVP solvers, including a vari able-step-variable-order implementation of the MEBDF method by Cash, it tur ned out that the MEBDF code often performs more efficiently than codes like RADAU5, DASSL and VODE. This motivated us to look at possible parallel imp lementations of the MEBDF method. Each MEBDF step essentially consists of s uccessively solving three non-linear systems by means of modified Newton it eration using the same Jacobian matrix. In a direct implementation of the M EBDF 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 tight-hand-side evaluations have to be done in sequence. In this paper, our starting point is the original (un modified) EBDF method. As a consequence, two different Jacobian matrices ar e 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 i teration the forward-backward substitutions and the right-hand-side evaluat ions can be done concurrently. A mutual comparison of the performance of th e parallel EBDF approach and the MEBDF approach shows that we can expect a speed-up factor of about 2 on three processors.