An Asymptotic Parallel-in-Time Method for Highly Oscillatory PDEs

We present a new time-stepping algorithm for nonlinear PDEs that exhibit scale separation in time of a highly oscillatory nature. The algorithm combines the parareal method---a parallel-in-time scheme introduced in [J.-L. Lions, Y. Maday, and G. Turinici, C. R. Acad. Sci. Paris Ser. I Math., 332 (2001), pp. 661--668]---with techniques from the heterogeneous multiscale method (cf. [W. E and B. Engquist, Notices Amer. Math. Soc., 50 (2003), pp. 1062--1070]), which make use of the slow asymptotic structure of the equations [A. J. Majda and P. Embid, Theoret. Comput. Fluid Dyn., 11 (1998), pp. 155--169]. We present error bounds, based on the analysis in [M. J. Gander and E. Hairer, in Domain Decomposition Methods in Science and Engineering XVII, Springer, Berlin, 2008, pp. 45--56] and [G. Bal, in Domain Decomposition Methods in Science and Engineering, Springer, Berlin, 2005, pp. 425--432], that demonstrate convergence of the method. A complexity analysis also demonstrates that the parallel speedup increases arbitrarily with greater scale separation. Finally, we demonstrate the accuracy and efficiency of the method on the (one-dimensional) rotating shallow water equations, which is a standard test problem for new algorithms in geophysical fluid problems. Compared to exponential integrators such as ETDRK4 and Strang splitting---which solve the stiff oscillatory part exactly---we find that we can use coarse time steps that are orders of magnitude larger (for a comparable accuracy), yielding an estimated parallel speedup of approximately 100 for physically realistic parameter values. For the (one-dimensional) shallow water equations, we also show that the estimated parallel speedup of this “asymptotic parareal method” is more than a factor of 10 greater than the speedup obtained from the standard parareal method.