Paper Info
Title
Convergence in Norm of Nonsymmetric Algebraic Multigrid
Abstract
Algebraic multigrid (AMG) is one of the fastest numerical methods for solving large sparse linear systems. For SPD matrices, convergence of AMG is well motivated in the A-norm, and AMG has proven to be an effective solver for many applications. Recently, several AMG algorithms have been developed that are effective on nonsymmetric linear systems. Although motivation was provided in each case, the convergence of AMG for nonsymmetric linear systems is still not well understood, and algorithms are based largely on heuristics or incomplete theory. For multigrid restriction and interpolation operators, R and P, respectively, let I - Pi := I - P(RAP)(-1) RA denote the projection corresponding to coarse-grid correction in AMG. It is invariably the case in the nonsymmetric setting that vertical bar vertical bar Pi vertical bar vertical bar = vertical bar vertical bar I - Pi vertical bar vertical bar > 1 in any known norm. This causes an interesting dichotomy: coarse-grid correction is fundamental to AMG achieving fast convergence, but, in this case, can actually increase the error. Here, we present a detailed analysis of nonsymmetric AMG, discussing why SPD theory breaks down in the nonsymmetric setting, and developing a general framework for convergence of NS-AMG. Classical multigrid weak and strong approximation properties are generalized to a fractional approximation property. Conditions are then developed on R and P to ensure that vertical bar vertical bar Pi vertical bar vertical bar (root A*A) is nicely bounded, independent of problem size. This is followed by the development of conditions for two-grid and multilevel W-cycle convergence in the root A*A-norm.
Year
DOI
Venue
2019
10.1137/18M1193773
SIAM JOURNAL ON SCIENTIFIC COMPUTING
Keywords
Field
DocType
nonsymmetric,multigrid,convergence,two-grid,AMG
Convergence (routing),Applied mathematics,Linear system,Matrix (mathematics),Mathematical analysis,Numerical analysis,Multigrid method,Mathematics
Journal
Volume
Issue
ISSN
41
5
1064-8275
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Tom Manteuffel111.37
Ben S. Southworth200.34