  Fully implicit Runge-Kutta (IRK) methods have many desirable accuracy and
stability properties as time integration schemes, but high-order IRK methods
are not commonly 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 solving the nonlinear equations that
arise from IRK methods (and discontinuous Galerkin discretizations in time)
applied to nonlinear numerical PDEs, including PDEs with algebraic constraints.
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, it is
proven that the preconditioned 2x2 operator's condition number is bounded by a
small constant close to one, independent of the spatial discretization, spatial
mesh, and time step, and with only weak dependence on the number of stages or
integration accuracy. Moreover, the new method is built using the same
preconditioners needed for backward Euler-type time stepping schemes, so can be
readily added to existing codes. 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 IRK, while in all cases 4th-order Gauss IRK requires
roughly half the number of preconditioner applications as required by standard
SDIRK methods.
