PARALLELISM IN TIME:

Can parts of the solution later in time be computer before

the solution earlier in time is known ?

Martin J. Gander
McGill University and University of Geneva

Thursday, July 29, 2004

Chapman Room, Mesa Lab 11am

Large scale time dependent problems can only be solved using parallel computers. To do such simulations, time marching schemes are commonly used, and at each time step the computation is done in parallel using all the processors available. Once the time step is solved, the simulation advances to the next time step. This approach is effective as long as each time step is costly enough to lead to an effective computation to communication ratio of the process. If however hundreds of thousands of time steps need to be simulated, or very many processors are available, the scalability of this approach is often lost. It would be of great advantage to be able to compute the solution parallel in time as well, which would add a fourth dimension to the parallelization of the process. Is it possible to do useful computations at future time steps before the current time step results are

known ?

I will first survey in this talk several classical approaches in the literature which have tried to do so, and show the positive and negative results known for these classical approaches. I will then discuss a new approach introduced in 2001 by Lions, Maday and Turinici called the parareal algorithm. In this algorithm, the time domain is decomposed into subdomains in time, and then an iteration parallel in time using fine grid approximations on the time subdomains and a coarse grid correction in time is used to construct a better and better approximation in time of the evolution problem. I will show that the parareal algorithm can be put into the context of the classical methods surveyed at the beginning of the talk and also present new convergence results for the parareal algorithm, which show that indeed the solution later in time can be successfully approximated before an accurate approximation earlier in time is available.