Toward robust algebraic multigrid methods for nonsymmetric problems

Thesis

When analyzing symmetric problems and the methods for solving them, multigrid and algebraic multigrid in particular, one of the primary tools at the analyst's disposal is the energy norm associated with the problem. The lack of this tool is one of the many reasons analysis of nonsymmetric problems and methods for solving them is substantially more difficult than in the symmetric case. We show that there is an analog to the energy norm for a nonsymmetric matrix A, associated with a new absolute value we term the "form" absolute value. This new absolute value can be described as a symmetric positive definite solution to the matrix equation A*|A|^-1A = |A|; it exists and is unique in particular whenever A has positive symmetric part. We then develop a novel convergence theory for a general two-level multigrid iteration for any such A, making use of the form absolute value. In particular, we derive a convergence bound in terms of a smoothing property and separate approximation properties for the interpolation and restriction (a novel feature). Finally, we present new algebraic multigrid heuristics designed specifically targeting this new theory, which we evaluate with numerical tests.

Authors: Lottes, J

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: nonsymmetric; absolute value; algebraic multigrid
• Subjects: Multigrid methods (Numerical analysis)