°µÍø½ûÇø

Parallel in Time Algorithms for Nonlinear Partial Differential Equations

Ben O'Neill

Applied Mathematics,Ìý

Date and time:Ìý

Tuesday, September 15, 2015 - 11:00am

³¢´Ç³¦²¹³Ù¾±´Ç²Ô:Ìý

GRVW 105

´¡²ú²õ³Ù°ù²¹³¦³Ù:Ìý

Standard sequential time marching schemes limit parallelism to the spatial domain. With computer architectures growing in size and clock speeds remaining constant, speed-up must come from greater parallelism. Multigrid Reduction in Time (MGRIT) is an iterative procedure that allows for temporal parallelism by utilizing multigrid reduction techniques and a multilevel hierarchy of coarse time-grids. MGRIT has been shown to be very effective for linear problems, with speedups of up to 10 times coming with the addition of only 256 temporal processors.

The goal of this work is the efficient solution of nonlinear problems with MGRIT, where efficient is defined as achieving similar performance when compared to a corresponding linear problem.Ìý As our benchmark, we use the p-Laplacian, where p=4 corresponds to a well-known nonlinear diffusion equation and p=2 corresponds to our benchmark linear diffusion problem.Ìý When considering linear problems and implicit time stepping schemes, the cost of the key computational kernel, a time stepping routine capable of marching forward in time given only the time step size and the solution at a previous time(s), is generally fixed across temporal grids. This is not the case for nonlinear problems, where the work required increases dramatically on coarser time-grids, where large time steps lead to worse conditioned nonlinear solves and increased nonlinear iteration counts per time step evaluation. We show that by using a variety of strategies, most importantly, spatial coarsening and an alternate initial guess to the nonlinear solver, we can reduce the work per time step evaluation to less than that of an equivalent sequential time integration. This allows for overall speedups comparable with those for linear problems.