  Fully implicit Runge-Kutta (IRK) methods have many desirable accuracy and
stability properties as time integration schemes, but are rarely used in
practice with large-scale numerical PDEs because of the difficulty of solving
the stage equations. This paper introduces a theoretical and algorithmic
framework for the fast, parallel solution of the nonlinear equations that arise
from IRK methods applied to nonlinear numerical PDEs, including PDEs with
algebraic constraints. This framework also naturally applies to discontinuous
Galerkin discretizations in time. Moreover, the new method is built using the
same preconditioners needed for backward Euler-type time stepping schemes.
Several new linearizations of the nonlinear IRK equations are developed,
offering faster and more robust convergence than the often-considered
simplified Newton, as well as an effective preconditioner for the true Jacobian
if exact Newton iterations are desired. Inverting these linearizations requires
solving a set of block 2x2 systems. Under quite general assumptions on the
spatial discretization, it is proven that the preconditioned operator has a
condition number of ~O(1), with only weak dependence on the number of stages or
integration accuracy. The new methods are applied to several challenging fluid
flow problems, including the compressible Euler and Navier Stokes equations,
and the vorticity-streamfunction formulation of the incompressible Euler and
Navier Stokes equations. Up to 10th-order accuracy is demonstrated using Gauss
integration, while in all cases 4th-order Gauss integration requires roughly
half the number of preconditioner applications as required by standard SDIRK
methods.
