A parallelizable preconditioner for the iterative solution of implicit Runge-Kutta-type methods

The main difficulty in the implementation of most standard implicit Runge-Kutta (IRK) methods applied to (stiff) ordinary differential equations (ODEs) is to efficiently solve the nonlinear system of equations. In this article we propose the use of a preconditioner whose decomposition cost for a parallel implementation is equivalent to the cost for the implicit Euler method. The preconditioner is based on the W-transformation of the RK coefficient matrices discovered by Hairer and Wanner. For stiff ODEs the preconditioner is by construction asymptotically exact for methods with an invertible RK coefficient matrix. The methodology is particularly useful when applied to super partitioned additive Runge-Kutta (SPARK) methods. The nonlinear system can be solved by inexact simplified Newton iterations: at each simplified Newton step the linear system can be approximately solved by an iterative method applied to the preconditioned linear system. (C) 1999 Published by Elsevier Science B.V. All rights reserved.