Under CopyrightStüben, K.K.Stüben2022-03-0707.08.20021999https://publica.fraunhofer.de/handle/publica/29027010.24406/publica-fhg-290270Seit den frühen neunziger Jahren besteht ein stark wachsender Bedarf an effizienteren Methoden zur Lösung großer, dünnbesetzter und unstrukturierter linearer Gleichungssysteme. Klassische Lösungsverfahren sind für praktisch relevante Problemgrößen an ihre Grenzen gestoßen und neue hierarchische Verfahren mußten entwickelt werden, um die numerische Effizienz zu steigern. Dieses Paper gibt eine elementare Einführung in die erste, rein matrix-orientierte Methode dieser Art, die algebraische Mehrgittermethode (AMG). In dieser Methode wird die klassische Mehrgitteridee der Kombination von Glättungs- mit Grobgitterkorrekturprozessen auf gewisse Klassen von Matrixproblemen übertragen. Neben ihrer Robustheit und Effizienz besteht ein großer Vorteil dieser Methode etwa in ihrer direkten Anwendbarkeit zur Lösung verschiedener Typen elliptischer partieller Differentialgleichungen auf unstrukturierten, zwei- oder dreidimensionalen Gittern. Weil AMG keine geometrische Information ausnutzt, kann es unmittelbar auch zur Lösung von Problemen eingesetzt werden, die keinen direkten geometrischen Hintergrund besitzen, vorausgesetzt, die zugrundeliegenden Matrizen erfüllen gewisse Voraussetzungen. Obwohl der AMG-Ansatz bereits zu Beginn der achtziger Jahre entwickelt wurde, stellt er immer noch einen der effizientesten Ansätze zur algebraischen Lösung entsprechender Probleme dar. Allerdings sind zwischenzeitlich einige Modifikationen und Erweiterungen hinzugekommen. Neben einer Einführung in die theoretischen Grundlagen von AMG beschreiben wir einen konkreten Algorithmus und demonstrieren seine Robustheit und Effizienz am Beispiel verschiedener Anwendungen.Since the early nineties, there has been a strongly increasing demand for more efficient methods to solve large sparse and unstructured linear systems of equations. For practically relevant problem sizes, classical one-level methods had already reached their limits and new hierarchical algorithms had to be developed in order to allow an efficient solution of even larger problems. The purpose of this paper is to give an elementary introduction to the first hierarchical and purely matrix-based approach, algebraic multigrid (AMG). The main idea behind AMG is to extend the classical ideas of geometric multigrid (smoothing and coarse-grid correction) to certain classes of algebraic systems of equations. Besides its robustness and efficiency, the main practical advantage of AMG is that it can directly be applied, for instance, to solve various types of elliptic partial differential equations discretized on unstructured meshes, both in 2D and 3D. Since AMG does not make use of any geometric information, it is a \plug-in" solver which can even be applied to problems without any geometric background, provided that the underlying matrix satisfies certain properties. Although the development of AMG goes back to the early eighties, it still provides one of the most efficient algebraic methods to solve corresponding problems. Compared to the original approach, however, several modifications and extensions have been introduced. In addition to the theoretical basics of AMG, we present a concrete algorithm in some detail and demonstrate its robustness and efficiency by means of a variety of typical applications.Contents S.4-7 1 Introduction S.8-15 - 1.1 Geometric multigrid S.9-10 - 1.2 Algebraic multigrid S.10-12 - 1.3 An example S.12-14 - 1.4 Overview of the paper S.14-15 2 Theoretical basis and notation S.16-25 - 2.1 Formal AMG components S.16-18 - 2.2 Further notation S.18-20 - 2.3 Limit case of direct solvers S.20-23 - 2.4 The variational principle for positive de nite problems S.23-25 3 Algebraic smoothing S.26-36 - 3.1 Basic norms and smooth eigenvectors S.26-27 - 3.2 Smoothing property of relaxation S.28-31 - 3.3 Interpretation of algebraically smooth error S.31-36 - 3.3.1 M-matrices S.32-33 - 3.3.2 Essentially positive-type matrices S.33-34 - 3.3.3 Large positive connections S.34-36 4 Post-smoothing and two-level convergence S.37-51 - 4.1 Convergence estimate S.37-39 - 4.2 Direct interpolation S.39-50 - 4.2.1 M-matrices S.39-45 - 4.2.2 Essentially positive-type matrices S.45-46 - 4.2.3 General case S.46-50 - 4.3 Indirect interpolation S.50-51 5 Pre-smoothing and two-level convergence S.52-59 - 5.1 Convergence using mere F-smoothing S.52-58 - 5.1.1 An auxiliary result S.53 - 5.1.2 F-smoothing S.54 - 5.1.3 Jacobi-interpolation S.55 - 5.1.4 Convergence estimate S.55-58 - 5.2 Convergence using full smoothing S.58-59 6 Limits of the theory S.60-62 7 The AMG algorithm S.63-75 - 7.1 Coarsening S.63-69 - 7.1.1 Standard coarsening S.64-66 - 7.1.2 Aggressive coarsening S.67-68 - 7.1.3 Strong positive connections S.69 - 7.2 Interpolation S.69-74 - 7.2.1 Direct and standard interpolation S.70-72 - 7.2.2 Multi-pass interpolation S.72-73 - 7.2.3 Jacobi-interpolation S.73-74 - 7.2.4 Truncation of interpolation S.74 - 7.3 AMG as pre-conditioner S.74-75 8 Applications S.76-111 - 8.1 Default settings and notation S.77-78 - 8.2 Poisson-like problems S.78-84 - 8.2.1 Coarsening and complexity S.79-80 - 8.2.2 Performance and comparisons S.80-83 - 8.2.3 F-smoothing and Jacobi-interpolation S.83-84 - 8.3 Computational uid dynamics S.85-92 - 8.3.1 Segregated solution methods S.86-88 - 8.3.2 Industrial test cases S.88-91 - 8.3.3 Low-accuracy approximations S.91-92 - 8.4 Problems with discontinuous coe cients S.92-102 - 8.4.1 A model problem S.93-97 - 8.4.2 Oil reservoir simulation S.97-100 - 8.4.3 Electromagnetic systems S.100-102 - 8.5 Further model problems S.102-111 - 8.5.1 Special anisotropic problems S.102-106 - 8.5.2 Convection-di usion problems S.106-109 - 8.5.3 Inde nite problems S.109-111 9 Aggregation-based AMG S.112-117 - 9.1 Re-scaling of the Galerkin operator S.113-115 - 9.2 Smoothed aggregation S.115-117 10 Further developments and conclusions S.118-127enalgebraisches Mehrgitteralgebraic multigrid003005006518book