Premium
Algebraic analysis of aggregation‐based multigrid
Author(s) -
Napov Artem,
Notay Yvan
Publication year - 2011
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.741
Subject(s) - mathematics , multigrid method , classification of discontinuities , diagonally dominant matrix , convergence (economics) , rate of convergence , bounded function , algebraic number , boundary (topology) , a priori and a posteriori , algebraic analysis , grid , mathematical analysis , pure mathematics , partial differential equation , geometry , computer science , ordinary differential equation , key (lock) , computer security , differential algebraic equation , philosophy , epistemology , economics , invertible matrix , differential equation , economic growth
A convergence analysis of two‐grid methods based on coarsening by (unsmoothed) aggregation is presented. For diagonally dominant symmetric (M‐)matrices, it is shown that the analysis can be conducted locally; that is, the convergence factor can be bounded above by computing separately for each aggregate a parameter, which in some sense measures its quality. The procedure is purely algebraic and can be used to control a posteriori the quality of automatic coarsening algorithms. Assuming the aggregation pattern is sufficiently regular, it is further shown that the resulting bound is asymptotically sharp for a large class of elliptic boundary value problems, including problems with variable and discontinuous coefficients. In particular, the analysis of typical examples shows that the convergence rate is insensitive to discontinuities under some reasonable assumptions on the aggregation scheme. Copyright © 2010 John Wiley & Sons, Ltd.