Premium
MGM Optimal convergence for certain (multilevel) structured linear systems
Author(s) -
Aricó Antonio,
Donatelli Marco,
SerraCapizzano Stefano
Publication year - 2003
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/pamm.200310540
Subject(s) - mathematics , circulant matrix , toeplitz matrix , coefficient matrix , eigenvalues and eigenvectors , dimension (graph theory) , matrix (chemical analysis) , rate of convergence , polynomial , multigrid method , condition number , convergence (economics) , singular value , linear system , combinatorics , discrete mathematics , pure mathematics , mathematical analysis , computer science , key (lock) , physics , materials science , computer security , quantum mechanics , partial differential equation , economics , composite material , economic growth
We present a multigrid algorithm to solve linear systems whose coefficient metrices belongs to circulant, Hartley or τ multilevel algebras and are generated by a nonnegative multivariate polynomial f. It is known that these matrices are banded (with respect to their multilevel structure) and their eigenvalues are obtained by sampling f on uniform meshes, so they are ill‐conditioned (or singular, and need some corrections) whenever f takes the zero value. We prove the proposed metod to be optimal even in presence of ill‐conditioning: if the multilevel coefficient matrix has dimension ni at level i, i = 1, … , d, then only $ N(n) = \prod ^{d} _{i=1} n_{i} $ ni operations are required on each iteration, but the convergence rate keeps constant with respect to N(n) as it depends only on f. The algorithm can be extended to multilevel Toeplitz matrices too.