A V-cycle Multigrid for multilevel matrix algebras: proof of optimality

We analyze the convergence rate of a multigrid method for multilevel
linear systems whose coefficient matrices are generated by a real
and nonnegative multivariate polynomial $f$ and belong to multilevel
matrix algebras like circulant, tau, Hartley, or are of Toeplitz type.

In the case of matrix algebra linear systems, we prove that the
convergence rate is independent of the system dimension even in
presence of asymptotical ill-conditioning (this happens iff $f$
takes the zero value). More precisely, if the $d$-level coefficient
matrix has partial dimension $n_r$ at level $r$, with $r=1,\dots,d$,
then the size of the system is $N(\mi{n})=\prod_{r=1}^d n_r$,
$\mi{n}=(n_1, \dots, n_d)$, and $O(N(\mi{n}))$ operations are
required by the considered $V$-cycle Multigrid in order to compute the solution
within a fixed accuracy. Since the total arithmetic cost is
asymptotically equivalent to the one of a matrix-vector product, the
proposed method is optimal. Some numerical experiments concerning
linear systems arising in 2D and 3D applications are considered
and discussed.