German Title: Eine parallele algebraische Mehrgittermethode für elliptische Probleme mit stark diskontinuierlichen Koeffizienten

Preview

PDF, English Download (1MB) | Terms of use

Abstract

The aim of this thesis is the development of a parallel algebraic multigrid method suitable for solving linear systems arising from the discretization of scalar and systems of partial differential equations. Among others it is suitable from conforming finite element methods, finite volume methods, and discontinuous Galerkin methods. The method is especially tailored for the solution of diffusion problems with highly oscillating and discon- tinuous diffusion coefficients. The presented approach uses a new strength of connection measure for guiding the construction of the coarse level matrices. It uses a heuristic greedy aggregation algorithm that allows for aggressive coarsening. It is able to detect weak connections in the matrix graph even for anisotropic diffusion with bi- and trilinear finite elements and thus leads to semi- coarsening even for these cases. At the same time it keeps the stencil size from the finer levels and thus the total operator complexity low even for three dimensional problems. This leads to a very low memory consump- tion of our solver compared with other methods. We develop extensions of the solver to systems of partial differential equation by using special blocking approaches of the unknowns. These blockings are emulated by the underlying matrix and vector data struc- tures. As the blocking is already available to the compiler, it can be exploited to produce automatically more efficient code. For the solution of the linear systems stemming from Discontinuous Galerkin discretizations, we employ the subspace of continuous linear basis function as the space associated with the first coarse level. The further coarsening is done by using the above algorithm. For the method of Baumann and Oden we need to use overlapping Schwarz methods as smoothers to get a convergent method. Their local subspaces are con- structed using our aggregation algorithm on the blocks consisting of all unknowns associated with each element. Finally we present a parallelisation approach for iterative solvers and use it to parallelise our algebraic multigrid method. In our approach the information about the data decomposition is kept apart from the linear al- gebra solvers and data structures. It is used to keep the data stored in the local memory of the process consistent. Using our proposed consistency model, the efficient sequential linear algebra solvers and data structures can be reused without the need to rewrite the actual solver algorithms.

Translation of abstract (German)

Gegenstand dieser Arbeit ist die Entwicklung eines parallelen algebrai- schen Mehrgitterverfahrens zur Lösung linearer Systeme, die durch die Diskretisierung von skalaren und Systemen von partiellen Differential- gleichungen entstehen. Unter anderem ist es geeignet für lineare System aus der Diskretisierung mit konformen finite Elemente Verfahren, finiten Volumen Verfahren und unstetigen Galerkin Verfahren. Die Methode ist besonders geeignet zur Lösung der Diffusionsgleichung mit stark oszillie- renden und unstetigen Diffusionskoeffizienten. Das entwickelte Verfahren benützt ein neues Maß zur Erkennung von „starken“ Verbindungen im Matrixgraphen. Dieses leitet die Aggregati- on der Unbekannten der Matrix und damit die Konstruktion gröberer Matrizen. Die Vergröberung basiert auf einem neu entwickelten heuri- stischen Algorithmus, der auch aggressives Vergröbern erlaubt. Dieser kann schwache Verbindungen auch für anisotrope Diffusion mit bi- und trilinearen finiten Elementen erkennen und vergröbert nur in Richtung starker Verbindungen. Zur gleichen Zeit lässt der Algorithmus die Größe des Besetzheitssterns der Matrizen auf den groben Ebenen vergleichbar klein wie bei der Matrix auf der feinsten Ebene. Somit ist auch die Kom- plexität des Operators und damit der Speicherverbrauch des Lösers im Vergleich mit anderen algebraischen Mehrgitterlösern gering. Wir entwickeln Erweiterungen des Lösers für Systeme partieller Diffe- rentialgleichungen, indem wir die Unbekannten auf eine spezielle Weise blocken. Diese Blöcke werden in den benutzten Matrix- und Vektorda- tenstrukturen nachgebildet. Die Struktur dieser Blöcke ist dem Compiler bereits bekannt. Deswegen kann er sie ausnützen, um besonders effizien- ten Code zu generieren. Für die Lösung linearer Systeme, die aus unstetigen Galerkin Diskre- tisierungen entstanden sind, benutzen wir den Unterraum der stetigen linearen Ansatzfunktionen als Raum der ersten gröberen Ebene. Ab hier benutzen wir zur weiteren Vergröberung den obigen Algorithmus. Für die Methode von Baumann und Oden benötigen wir überlappende Schwarz Verfahren als Glätter, um Konvergenz zu erreichen. Die lokalen Probleme dieser Glätter konstruieren wir mit Hilfe unseres Aggregationsalgorith- mus. Wir benützen die geblockte Variante ähnlich wie für Systeme. Alle mit den Basisfunktionen eines Elements assoziierten Unbekannten bilden zusammen einen Block. Schließlich präsentieren wir unseren Parallelisierungansatz für iterati- ve Löser und benutzen ihn, um unser algebraisches Mehrgitterverfahren u parallelisieren. Bei unserem Ansatz wird die Information über die Da- tenverteilung und Kommunikationsmuster nicht in die Löser und Daten- strukturen integriert. Basierend auf diesen extern gespeicherten Informa- tionen wird dafür gesorgt, dass die Daten vorgegebene Konsistenzmodelle erfüllen. So können wir die sequentiellen Löseralgorithmen und die Da- tenstrukturen der linearen Algebra wiederverwenden, ohne die Löser neu schreiben zu müssen. Gleichzeitig wird die Kommunikation der Daten auf ein Minimum beschränkt und die Effizienz der sequentiellen linearen Algebra kann auch im parallelen Fall genutzt werden.