Preconditioning and Parallel Implementation of Implicit Runge-Kutta Methods

A major problem in obtaining an e#cient implementation of fully implicit RungeKutta (IRK) methods applied to systems of di#erential equations is to solve the underlying systems of nonlinear equations. Their solution is usually obtained by application of modified Newton iterations with an approximate Jacobian matrix. The systems of linear equations of the modified Newton method can actually be solved approximately with a preconditioned linear iterative method. In this article we present a truly parallelizable preconditioner to the approximate Jacobian matrix. Its decomposition cost for a sequential or parallel implementation can be made equivalent to the cost corresponding to the implicit Euler method. The application of the preconditioner to a vector consists of three steps: two steps involve the solution of a linear system with the same block-diagonal matrix and one step involves a matrix-vector product. The preconditioner is asymptotically correct for the Dahlquist test equation. Some free parameters of the preconditioner can be determined in order to optimize certain properties of the preconditioned approximate Jacobian matrix