  Runge-Kutta (RK) schemes, especially Gauss-Legendre and some other fully
implicit RK (FIRK) schemes, are desirable for the time integration of parabolic
partial differential equations due to their A-stability and high-order
accuracy. However, it is significantly more challenging to construct optimal
preconditioners for them compared to semi-implicit RK (aka diagonally implicit
RK or DIRK) schemes. To address this challenge, we first introduce
mathematically optimal preconditioners called block complex Schur decomposition
(BCSD), block real Schur decomposition (BRSD), and block Jordan form (BJF),
motivated by block-circulant preconditioners and Jordan form solution
techniques for IRK. We then derive an efficient, near-optimal singly-diagonal
approximate BRSD (SABRSD) by approximating the quasi-triangular matrix in real
Schur decomposition using an optimized upper-triangular matrix with a single
diagonal value. A desirable feature of SABRSD is that it has comparable memory
requirements and factorization cost as singly DIRK (SDIRK). We approximately
factorize the diagonal blocks in these preconditioners using a
near-linear-complexity multilevel ILU factorization called HILUCSI, which is
significantly more robust and more efficient than ILU(0). We apply the
preconditioners in right-preconditioned GMRES to solve the advection-diffusion
equation in 3D using finite element and finite difference methods. We show that
BCSD, BRSD, and BJF significantly outperform other preconditioners in terms of
GMRES iterations, and SABRSD is competitive with them and the prior state of
the art in terms of computational cost while requiring the least amount of
memory.
