Error Bound Analysis of the Stochastic Parareal Algorithm

Stochastic parareal (SParareal) is a probabilistic variant of the popular parallel-intime algorithm known as parareal.Similarly to parareal, it combines fine-and coarse-grained solutions to an ordinary differential equation (ODE) using a predictor-corrector (PC) scheme.The key difference is that carefully chosen random perturbations are added to the PC to try to accelerate the location of a stochastic solution to the ODE.In this paper, we derive superlinear and linear mean-square error bounds for SParareal applied to nonlinear systems of ODEs using different types of perturbations.We illustrate these bounds numerically on a linear system of ODEs and a scalar nonlinear ODE, showing a good match between theory and numerics.