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 (onedimensional) 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.