Skip Navigation

IMA Journal of Numerical Analysis 2001 21(1):367-385; doi:10.1093/imanum/21.1.367
© 2001 by Institute of Mathematics and its Applications
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Frank, J. E.
Right arrow Articles by Van Der Houwen, P. J.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Parallel iteration of the extended backward differentiation formulas

J. E. Frank1 and P. J. Van Der Houwen2

1 Delft University of Technology, The Netherlands 2 CWI, Amsterdam, The Netherlands

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 RADAU5, 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.

Key Words: numerical analysis, iteration methods, initial value problems, extended BDFs, parallelism

Received 26 March 1999. Accepted 29 February 2000.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.