  This work is concerned with linear matrix equations that arise from the
space-time discretization of time-dependent linear partial differential
equations (PDEs). Such matrix equations have been considered, for example, in
the context of parallel-in-time integration leading to a class of algorithms
called ParaDiag. We develop and analyze two novel approaches for the numerical
solution of such equations. Our first approach is based on the observation that
the modification of these equations performed by ParaDiag in order to solve
them in parallel has low rank. Building upon previous work on low-rank updates
of matrix equations, this allows us to make use of tensorized Krylov subspace
methods to account for the modification. Our second approach is based on
interpolating the solution of the matrix equation from the solutions of several
modifications. Both approaches avoid the use of iterative refinement needed by
ParaDiag and related space-time approaches in order to attain good accuracy. In
turn, our new algorithms have the potential to outperform, sometimes
significantly, existing methods. This potential is demonstrated for several
different types of PDEs.
