id: 02135313
dt: j
an: 02135313
au: Aricò, Antonio; Donatelli, M.; Serra Capizzano, Stefano
ti: V-cycle optimal convergence for certain (multilevel) structured linear
    systems.
so: SIAM J. Matrix Anal. Appl. 26, No. 1, 186-214 (2004).
py: 2004
pu: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
la: EN
cc: 
ut: $τ$ algebra; two-grid and multigrid iterations; multi-iterative methods;
    multilevel matrices; circulant matrix; Hartley matrix; Toeplitz matrix;
    V-cycle; convergence; ill-conditioning; numerical experiments; image
    restoration
ci: 
li: doi:10.1137/S0895479803421987
ab: Summary: We are interested in the solution by multigrid strategies of
    multilevel linear systems whose coefficient matrices belong to the
    circulant, Hartley, or $τ$ algebras or to the Toeplitz class and are
    generated by (the Fourier expansion of) a nonnegative multivariate
    polynomial $f$. It is well known that these matrices are banded and
    have eigenvalues equally distributed as $f$, so they are
    ill-conditioned whenever $f$ takes the zero value; they can even be
    singular and need a low-rank correction.  We prove the V-cycle
    multigrid iteration to have a convergence rate independent of the
    dimension even in presence of ill-conditioning. If the (multilevel)
    coefficient matrix has partial dimension $n_{r}$ at level $r$,
    $r=1,\dots,d$, then the size of the algebraic system is
    $N(n)=\prod_{r=1}^d n_r$, $O(N(n))$ operations are required by our
    technique, and therefore the corresponding method is optimal.  Some
    numerical experiments concerning linear systems arising in
    applications, such as elliptic PDEs with mixed boundary conditions and
    image restoration problems, are considered and discussed.
rv: