Parallel algorithms for initial-value problems for difference and differential equations

摘要

Let {yn} be a trajectory defined sequentially by a nonlinear vector difference equation yn+1 = Fn+1(yn) with y0 known. A Steffensen-like iterative method is proposed which starts from a guessed sequence {un(0)} for the approximation of {yn} and allows certain computations to be performed in parallel. The sequence {u(k+1)n} is obtained from {u(k)n} by means of a formula of the form u(k+1)n+1 = v(k+1)n+1 + Λ(k+1)n+1(u(k+1)n - u(k)n). Here the vectors v(k+1)n+1 and the matrices Λ(k+1)n+1 each require a function evaluation but can be computed in parallel with respect to n in a suitable interval [Nk, Mk], the length of which depends on the number of processors available. Therefore, for the algorithm to serve effectively, the Steffensen iteration must converge quickly and the machine used must possess a large number of processors. Finally, note that the theory includes the case that the sequence {yn} is given by a one-step ODE solver.