Multigrid methods for Toeplitz linear systems with different size reduction

Starting from the spectral analysis of $g$-circulant matrices, we
study the convergence of a multigrid method for circulant and Toeplitz matrices
with various size reductions. We assume that the size $n$ of the coefficient matrix is
divisible by $g\ge 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 two-grid method and of the multigrid method is proved, when the number $\theta \in \mathbb{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.