A parallel algebraic multigrid method for elliptic problems with highly discontinuous coefficients [Elektronische Ressource] / vorgelegt von Markus Blatt

Sujets

• Mathematics

Informations

• Publié par: ruprecht-karls-universitat_heidelberg
• Publié le: 01 janvier 2010
• Nombre de lectures: 12
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

InauguralDissertation
zur Erlangung der Doktorw?rde
der
NaturwissenschaftlichMathematischen Gesamtfakult?t
der
RuprechtKarlsUniversit?t
Heidelberg
vorgelegt von
DiplomMathematiker Markus Blatt
aus Erlangen
Tag der m?ndlichen Pr?fung: 2. Juli 2010A Parallel Algebraic Multigrid Method for
Elliptic Problems with Highly Discontinuous
Coecients
February 4, 2010
Gutachter: Prof. Dr. Peter Bastian
Dr. Robert ScheichlIVAbstract
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.
Thepresentedapproachusesanewstrengthofconnectionmeasurefor
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
informationaboutthedatadecompositioniskeptapartfromthelinearal
gebrasolversanddatastructures. Itisusedtokeepthedatastoredinthe
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.
VVIZusammenfassung
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
bereitsbekannt.Deswegenkannersieausnützen,umbesonderseffizien
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
mitdenBasisfunktioneneinesElementsassoziiertenUnbekanntenbilden
zusammen einen Block.
Schließlich präsentieren wir unseren Parallelisierungansatz für iterati
ve Löser und benutzen ihn, um unser algebraisches Mehrgitterverfahren
VIIzu parallelisieren. Bei unserem Ansatz wird die Information über die Da
tenverteilung und Kommunikationsmuster nicht in die Löser und Daten
strukturenintegriert.BasierendaufdiesenexterngespeichertenInforma
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.
VIIIAcknowledgement
First of all, I would like to express my deep gratitude to the adviser of
this thesis, Prof. Dr. Peter Bastian. When I told him that I would like
to write a dissertation, he, immediately, provided me with a post. He
always trusted in me and provided me with great freedom of research.
ThesupportthatIexperiencedduringthepreparationofthisthesisinhis
group was outstanding.
The diversity of his group in terms of my colleagues’ scientific back
ground was very fruitful in forming me as a scientist. This group is truly
interdisciplinary in itself and lets one get insights into many different
fields and applications. Explaining current problems and insights to peo
ple with a different background turned out to be very useful. Sometimes
rephrasing problems in another scientific language made contradictions
and errors apparent, even before anybody commented on the problem.
While being grateful to all members of the group, my special thanks go
to my dear colleagues Christian Engwer and Olaf Ippisch, who constantly
discussed scientific issues and real world stuff with me from the start of
this thesis.
I would like to thank Dr. Rob Scheichl for many discussions about ap
plying algebraic multigrid methods to problems with jumping coefficients
aswellastoDGdiscretizations,andDr. KlausJohannsenforsharinghis
experiences with applying multigrid to NIPG discretizations.
I would like to thank my fellow DUNE developers for putting so much
effortintotheDUNElibrary. Withoutthemitwouldnothavebeenpossible
to test my solver with such challenging problems. Providing my solvers
withthelibraryresultedintomanycommentsfromthem. Thismadesome
flaws apparent that I would not have found on my own.
I would like to thank the users of DUNE and ISTL for trying it out and
using it in productive code. While this poses a real challenge onto the
developers, it forces us to always provide high quality code. Without the
users, DUNE would not be as usable and of such high quality.
Especially, I would like to thank the Statoil research centre in Trond
heim, Norway, for evaluating my solvers for their oil reservoir simulator
and providing me with an upscaling example and code for usage in this
thesis.
Furthermore,IwouldliketothankmyfatherHansPeterandmybrother
Simon for proofreading the final version of my thesis in nearly no time. I
am grateful to the rest of family, namely my mother Elvira and my sisters
Sarah and Sophie for their implicit support by just being there. Special
IXthanks go to my cousin Bärbel Gundlach, who was there when I needed
someone to take over some of my everyday duties. Her immediate help
gave me more time to work on the subject of this thesis.
Last but not least, I would like to thank Michaela for her patience and
constant emotional support during the preparation of this thesis. She
always believed in my abilities and assured me of them.
X