  Starting from the spectral analysis of g-circulant matrices, we consider a
new multigrid method for circulant and Toeplitz matrices with given generating
function. We assume that the size n of the coefficient matrix is divisible by g
\geq 2 such that at the lower level the system is reduced to one of size n/g by
employing g-circulant based projectors. We perform a rigorous two-grid
convergence analysis in the circulant case and we extend experimentally the
results to the Toeplitz setting, by employing structure preserving projectors.
The optimality of the proposed two-grid method and of the multigrid method is
proved, when the number theta \in N of recursive calls is such that 1 < theta <
g. The previous analysis is used also to overcome some pathological cases, in
which the generating function has zeros located at "mirror points" and the
standard two-grid method with g = 2 is not optimal. The numerical experiments
show the correctness and applicability of the proposed ideas both for circulant
and Toeplitz matrices.
