We develop the block-circulant structure of Gabor matrices, and establish that Gabor matrices are unitarily block-diagonalizable simultaneously. It opens a new way of implementing the discrete Gabor
transforms. For the most interesting cases, if the product ab of the lattice constants divides the signal length N (in particular, in the critical-sampling cases), we prove that the Gabor operators are simultaneously unitarily equivalent to non-negative pointwise multiplication operators. This leads to fast computations of the inverse of the Gabor operator and the square root of the inverse of the Gabor operator, as well as the dual Gabor wavelet and the tight Gabor wavelet. Gabor syntheses turn out to be simple, and we can also easily predetermine the stability of Gabor reconstructions.