  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 $\Pi:= P(RAP)^{-1}RA$ denote the projection corresponding to
coarse-grid correction in AMG. It is invariably the case in the nonsymmetric
setting that $\|\Pi\| > 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 \textit{fractional approximation property}.
Conditions are then developed on $R$ and $P$ to ensure that
$\|\Pi\|_{\sqrt{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 $\sqrt{A^*A}$-norm.
