  We perform a time-frequency analysis of Fourier multipliers and, more
generally, pseudodifferential operators with symbols of Gevrey, analytic and
ultra-analytic regularity. As an application we show that Gabor frames, which
provide optimally sparse decompositions for Schroedinger-type propagators,
reveal to be an even more efficient tool for representing solutions to a wide
class of evolution operators with constant coefficients, including weakly
hyperbolic and parabolic-type operators. Besides the class of operators, the
main novelty of the paper is the proof of super-exponential (as opposite to
super-polynomial) off-diagonal decay for the Gabor matrix representation.
