  Many iterative parallel-in-time algorithms have been shown to be highly
efficient for diffusion-dominated partial differential equations (PDEs), but
are inefficient or even divergent when applied to advection-dominated PDEs. We
consider the application of the multigrid reduction-in-time (MGRIT) algorithm
to linear advection PDEs. The key to efficient time integration with this
method is using a coarse-grid operator that provides a sufficiently accurate
approximation to the the so-called ideal coarse-grid operator. For certain
classes of semi-Lagrangian discretizations, we present a novel
semi-Lagrangian-based coarse-grid operator that leads to fast and scalable
multilevel time integration of linear advection PDEs. The coarse-grid operator
is composed of a semi-Lagrangian discretization followed by a correction term,
with the correction designed so that the leading-order truncation error of the
composite operator is approximately equal to that of the ideal coarse-grid
operator. Parallel results show substantial speed-ups over sequential time
integration for variable-wave-speed advection problems in one and two spatial
dimensions, and using high-order discretizations up to order five. The proposed
approach establishes the first practical method that provides small and
scalable MGRIT iteration counts for advection problems.
