Triangularly implicit iteration methods for ODE-IVP solvers

It often happens that iteration processes used for solving the implicit relations arising in ODE-IVP methods only start to converge rapidly after a certain number of iterations. Fast convergence right from the beginning is particularly important if we want to use so-called step-parallel iterations in which the iteration method is concurrently applied at a number of step points. In this paper, we construct highly parallel iteration methods that do converge fast from the first iteration on. Our starting point is the PDIRK method (parallel, diagonal-implicit, iterated Runge-Kutta method), designed for solving implicit Runge-Kutta equations on parallel computers. The PDIRK method may be considered as Newton type iteration in which the Newton Jacobian is `simplified' to block-diagonal form. However, when applied in a step-parallel mode, it turns out that its relatively slow convergence, or even divergent behaviour, reduces the effectiveness of the step-parallel scheme. By replacing the block-diagonal Newton Jacobian approximation in PDIRK by a block-triangular approximation, we do achieve convergence right from the beginning at a modest increase of the computational costs. Our convergence analysis of the block-triangular approach will be given for the wide class of general linear methods, but the derivation of iteration schemes is limited to Runge-Kutta based methods. A number of experiments show that the new parallel, triangular-implicit, iterated Runge-Kutta method (PTIRK method) is a considerable improvement over the PDIRK method.