Extended local fourier analysis for multigrid: optimal smoothing, coarse grid correction, and preconditioning

Mehrgitterverfahren sind schnelle, iterative Löser für partielle Differentialgleichungen. Insbesondere für elliptische Gleichungen ist ihre hohe Effizienz allgemein an erkannt und nachgewiesen. Sobald nichtelliptische und unsymmetrische Merkmale auftreten wie es bei realen Anwendungen üblich ist steht eine rigorose mathematische Theorie im Allgemeinen nicht zur Verfügung. Die vorherrschenden Analysewerkzeuge in solchen Situationen sind die Fourier Glättungs- und Zweigitteranalyse. Sie ermöglichen quantitative Konvergenzabschätzungen und eine geschickte Wahl der Mehrgitterkomponenten wie z.B. Glätter und Gittertransferoperatoren. Die korrekte Auswahl der Mehrgitterkomponenten für große Problemklassen ist ein schwieriger Prozess Eine populäre Alternative für die Konstruktion eines robusten Lösers ist die Verwendung von Mehrgittermethoden als Vorkonditionierer für ein Krylovverfahren wie z.B. GMRES Die Beiträge dieser Arbeit zur Fourieranalyse von Mehrgitterverfahren können in zwei Kategorien eingeteilt werden. Erstens wird die Auswahl an Situationen vergrößert in denen die Fourieranalyse angewendet werden kann. Das bedeutet insbesondere, daß die Fourieranalyse auf k-Gitterzyklen und auf Mehrgitter als Vorkonditionierer verallgemeinert wird Mit einer k-Gitteranalyse ist es möglich, echte Mehrgittereffekte zu untersuchen, die von der klassischen Zweigitteranalyse nicht aufgelöst werden können. Des weiteren kann eine detailliertere Untersuchung von eventuellen Grobgitterproblemen durchgeführt werden. Durch die Auswertung von Mehrgitterverfahren als Vorkonditionierer für GMRES werden zusätzliche wertvolle Einsichten erzielt. Zweitens wird die Bandbreite an Diskretisierungen und Mehrgitterkomponenten erweitert, für die eine detaillierte Fourieranalyse existiert. Hierbei betrachten wir vier wohlbekannte singulär gestörte Modellprobleme, um den Nutzen der beschriebenen Verallgemeinerungen unter Beweis zu stellen; die anisotrope Poissongleichung, die rotierte, anisotrope Diffusionsgleichung, die Konvektions-Diffusionsgleichung mit dominantem Konvektionsteil und das "Driven Cavity" Problem für die inkompressiblen Navier-Stokesgleichungen. Jede dieser Gleichungen repräsentiert eine größere Klasse von Problemen mit ähnlichen Merkmalen und Komplikationen wie sie in praxisnahen Rechnungen auftreten. Mithilfe der neu entwickelten Analysemethoden kann eine umfassende Untersuchung der charakteristischen Schwierigkeiten von singulär gestörten Problemen unternommen werden. Aufbauend auf die so gewonnenen Einsichten ist es möglich, Verfahrenskomponenten zu identifizieren, die eine verbesserte Mehrgitterkonvergenz erzielen. Die theoretischen Überlegungen werden anhand numerischer Testrechnungen bestätigt.

Multigrid methods are fast iterative solvers for partial di erential equations. Especially for elliptic equations they have been proven to be highly e cient. For problems with nonelliptic and nonsymmetric features--as they often occur in typical real life applications--a rigorous mathematical theory is generally not available. For such situations Fourier smoothing and two-grid analysis can be considered as the main analysis tools to obtain quantitative convergence estimates and to optimize different multigrid components like smoothers or inter-grid transfer operators. In general, it is difficult to choose the correct multigrid components for large classes of problems. A popular alternative to construct a robust solver is the use of multigrid as a preconditioner for a Krylov subspace acceleration method like GMRES. Our contributions to the Fourier analysis for multigrid are two-fold. Firstly we extend the range of situations for which the Fourier analysis can be applied. More precisely, the Fourier analysis is generalized to k-grid cycles and to multigrid as a preconditioner. With a k-grid analysis it is possible to investigate real multigrid effects which cannot be captured by the classical two-grid analysis. Moreover, the k-grid analysis allows for a more detailed investigation of possible coarse grid correction difficulties. Additional valuable insight is obtained by evaluating multigrid as a preconditioner for GMRES. Secondly we extend the range of discretizations and multigrid components for which detailed Fourier analysis results exist. We consider four well-known singularly perturbed model problems to demonstrate the usefulness of the above generalizations: The anisotropic Poisson equation, the rotated anisotropic diffusion equation, the convection diffusion equation with dominant convection, and the driven cavity problem governed by the incompressible Navier Stokes equations. Each of these equations represents a larger class of problems with similar features and complications which are of practical relevance. With the help of the newly developed Fourier analysis methods, a comprehensive study of characteristic difficulties for singular perturbation problems can be performed. Based on the insights from this analysis it is possible to identify remedies resulting in an improved multigrid convergence. The theoretical considerations are validated by numerical test calculations.