We discretize first order equations $u_t + c(x,t) u_x + b(x,t) u = f(x,t)$ subject to periodic boundary conditions (in $x$ and $t$) with a Fourier collocation method. The matrix of the resulting linear system is moderately sparse and highly structured. Iterative methods are an excellent choice for solving such systems. We compare the performance of various iterative solvers, and propose an effective preconditioning strategy for this class of matrices. The method extends easily to nonlinear PDEs, where each Newton step requires the solution of a linear first order equation. One such problem, namely the computation of an invariant torus, will be presented as an example.