Generalized Optimal AMG Convergence Theory for Nonsymmetric and Indefinite Problems
SIAM Journal on Scientific Computing · 31.10.2026 · 48 (5) · S89-S111
DOI: 10.1137/24m1679288 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Scientific Computing, online erschienen am 06.05.2025. Verfasst von Ahsan Ali und 5 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 44 Literaturangaben. Gefördert von: Los Alamos National Laboratory, National Science Foundation.
Abstract (Originalsprache)
Algebraic multigrid (AMG) is known to be an effective solver for many sparse symmetric positive definite (SPD) linear systems. For SPD systems, the convergence theory of AMG is well-understood in terms of the [Formula: see text]-norm, but in a nonsymmetric setting such an energy norm is nonexistent. For this reason, convergence of AMG for nonsymmetric systems of equations remains an open area of research. A particular aspect missing from theory of nonsymmetric and indefinite AMG is the incorporation of general relaxation schemes. In the SPD setting, the classical form of optimal AMG interpolation provides a useful insight in determining the best possible two-grid convergence rate of a method based on an arbitrary symmetrized relaxation scheme. In this work, we discuss a generalization of the optimal AMG convergence theory targeting nonsymmetric problems, using a certain matrix-induced orthogonality of the left and right eigenvectors of a generalized eigenvalue problem relating the system matrix and relaxation operator. We show that using this generalization of the optimal convergence theory, one can obtain a measure of the spectral radius of the two-grid error transfer operator that is mathematically equivalent to the derivation in the SPD setting for optimal interpolation, which instead uses norms. In addition, this generalization of the optimal AMG convergence theory can be further extended for symmetric indefinite problems, such as those arising from saddle-point systems so that one can obtain a precise convergence rate of the resulting two-grid method based on optimal interpolation. We provide supporting numerical examples of the convergence theory for nonsymmetric advection-diffusion problems, the two-dimensional Dirac equation motivated by [Formula: see text]-symmetry, and the mixed Darcy flow problem corresponding to a saddle-point system.
Förderung
- Los Alamos National Laboratory
- National Science Foundation
Zitieren
APA
Ali, A., Brannick, J. J., Kahl, K., Krzysik, O. A., Schroder, J. B., & Southworth, B. S. (2026). Generalized Optimal AMG Convergence Theory for Nonsymmetric and Indefinite Problems. SIAM Journal on Scientific Computing, 48(5), S89-S111. https://doi.org/10.1137/24m1679288
Vancouver
Ali A, Brannick JJ, Kahl K, Krzysik OA, Schroder JB, Southworth BS. Generalized Optimal AMG Convergence Theory for Nonsymmetric and Indefinite Problems. SIAM Journal on Scientific Computing. 2026;48(5):S89-S111. doi:10.1137/24m1679288
BibTeX
@article{Ali2026,
author = {Ali, Ahsan and Brannick, James J. and Kahl, Karsten and Krzysik, Oliver A. and Schroder, Jacob B. and Southworth, Ben S.},
title = {Generalized Optimal AMG Convergence Theory for Nonsymmetric and Indefinite Problems},
journal = {SIAM Journal on Scientific Computing},
year = {2026},
volume = {48},
number = {5},
pages = {S89--S111},
doi = {10.1137/24m1679288}
}
EUVIMED