  We begin by showing that any $n \times n$ matrix can be decomposed into a sum
of $n$ circulant matrices with periodic relaxations on the unit circle. This
decomposition is orthogonal with respect to a Frobenius inner product, allowing
recursive iterations for these circulant components. It is also shown that the
dominance of a few circulant components in the matrix allows sparse similarity
transformations using Fast-Fourier-transform (FFT) operations. This enables the
evaluation of all eigenvalues of dense Toeplitz, block-Toeplitz, and other
periodic or quasi-periodic matrices, to a reasonable approximation in
$\mathcal{O}(n^2)$ arithmetic operations. The utility of the approximate
similarity transformation in preconditioning linear solvers is also
demonstrated.
