next up previous
Next: About this document ...

Jed Brown
Fast solvers for implicit Runge-Kutta

Argonne National Laboratory
CU Boulder
jedbrown@mcs.anl.gov
Debojyoti Ghosh

Implicit Runge-Kutta methods solve coupled systems involving all stages in a step, and in turn benefit from excellent accuracy and stability properties as well as optional symplecticity. While quite successful in the dense and research ODE communities, IRK has only recently received significant attention from the PDE community, largely due to interest in the spectral deferred correction (SDC) method for solving IRK systems. While such methods can expose parallelism, total work grows superlinearly in the number of stages, and each stage experiences the low arithmetic intensity of scalar problems. These factors result in typically-low efficiencies. We propose a different solution technique, inspired by the classical methods of Butcher and Bickart as well as waveform relaxation for space-time multigrid. Specifically, we apply multigrid methods directly to the tensor-product system obtained by linearizing the coupled Runge-Kutta system. This results in easy vectorization and high arithmetic intensity similar to multiple right hand sides. Only one communication is required per iteration, which may assist applications with strict turn-around time requirements. We present these methods, a performance analysis, and techniques for improving convergence due to the increasing imaginary parts in the eigenvalues of the Runge-Kutta matrix.




next up previous
Next: About this document ...
Copper Mountain 2014-02-23