Effiziente Verfahren zur Lösung partieller ... · nauigkeit der Finite-Elemente-Methode auf voll besetzten Gittern nahezu erreicht wur- de. Die Konvergenzrate des Gauß-Seidel-Verfahrens

Effiziente Verfahren zur Lösung

partieller Differentialgleichungen mit

variablen Koeffizienten auf dünnen

Gittern

Der technischen Fakultät der

Friedrich-Alexander-Universität Erlangen-Nürnberg

zur Erlangung des akademischen Grades eines

Dr. Ing.

eingereichte Dissertation

von

Rainer Hartmann

aus

Nürnberg

Als Dissertation genehmigt

von der Technischen Fakultät

der Friedrich-Alexander-Universität Erlangen-Nürnberg

Tag der mündlichen Prüfung: 08.06.2018

Vorsitzender des Promotionsorgans:

Prof. Dr.-Ing. Reinhard Lerch

Gutachter:

Prof. Dr. Christoph Pflaum

Prof. Dr. Reinhold Schneider

Danksagungen

Ein erster Dank gilt Prof. Dr. Günther Greiner und dem Zufall. Ersterer übernahm im

Wintersemester 2014 in Vertretung die Vorlesung „Functional analysis for engineers“

und vertiefte das Thema Orthogonalität und hierarchische Basen. So wurde mein In-

teresse an diesem Thema geweckt.

Zusammen mit Prof. Dr. Christoph Pflaum konnte ich die Grundlage für diese Ar-

beit legen. Ich blicke auf eine diskussionsreiche und kreative Zeit zurück. Prof. Pflaum

hatte immer ein offenes Ohr und oft eine andere Meinung. Wer ihn vom Gegenteil

überzeugen konnte, hatte wirklich verstanden worum es geht. In unzähligen frucht-

baren Gesprächen wurde so mancher Ansatz verworfen und schließlich eine Lösung

gefunden.

Prof. Dr. Reinhold Schneider danke ich für die Übernahme des Zweitgutachtens,

dem Team vom Lehrstuhl für Systemsimulation für die angenehme Zeit und die Über-

lassung eines Schreibtisches, auch nach meinem Wechsel in die Industrie.

i

AbstractThis thesis offers an efficient solution for highly dimensional, elliptic partial differen-

tial equations on sparse grids. The discretization applies the Galerkin method and

the finite element method. In order to ensure an efficient implementation, an effec-

tive matrix-vector-multiplication, whose complexity scales linearly with the number of

grid points of the sparse grid, is required. For this end an algorithm will be presented,

which collects and distributes the hierarchical surplus through traversing over all grids

using a combination of restriction and prolongation operators. Sparse grips, however,

skip some paths compared to full grids. Thanks to the semi-orthogonality this does

not influence the convergence, with prewavelets being L2-orthogonal for overlapping

basis functions. A convergence proof shows that this orthogonality holds also for vari-

able coefficients since the induced errors by the semi-orthogonality property are small.

In contrast to full grids the number of unknowns decreases dramatically, whereas the

order of convergence is only slightly reduced for the discretization of sparse grids.

Numerical results with variable coefficients show an optimal convergence behavior

for three- and six-dimensional problems. Transformations for curvilinear bounded do-

mains have variable coefficients and are not based on tensor products. The calculation

of the coefficients of the system matrix utilizes numerical integration in high dimen-

sions. The matrix-vector multiplication is reduced to one-dimensional operators via

recursion. In the scope of this work a comprehensive software framework has been

created. By using templates, the implementation can be applied to arbitrary dimen-

sions. A parallelization for distributed memory, as well as shared memory, guarantees

a high accuracy for higher dimensions. An approach of semi-adaptive refinement en-

ables a partial refinement, while maintaining the structure of a tensor product grid.

This dissertation concludes with an outlook on the implementation of fully adaptive

sparse grids.

iii

ZusammenfassungZiel dieser Arbeit ist die effiziente Lösung hochdimensionaler elliptischer partieller

Differentialgleichungen auf dünnen Gittern. Bei Diskretisierung wird der Galerkin-

Ansatz und die Finite-Elemente-Methode verwendet. Eine effiziente Implementierung

der Matrix-Vektor-Multiplikation skaliert linear mit der Anzahl der Gitterpunkte. Da-

zu wird ein Algorithmus vorgestellt, der durch eine Kombination von Restriktionen

und Prolongationen die hierarchischen Überschüsse aller Gitter einsammelt und ver-

teilt. Für dünne Gitter muss allerdings auf den Austausch zwischen einigen Gittern

verzichtet werden. Dies hat aufgrund der Semi-Orthogonalität keinen Einfluss auf die

Konvergenz, da Prewavelets für überlappende Gebiete L2-orthogonal sind. Bei varia-

blen Koeffizienten zeigt ein Konvergenzbeweis, dass diese Werte sehr klein sind und

keinen Einfluss auf die Konvergenz haben. Die Konvergenzordnung der Dünngitter-

diskretisierung reduziert sich im Vergleich zu vollen Gittern nur leicht, während die

Anzahl der Unbekannten dramatisch abnimmt.

Numerische Ergebnisse mit variablen Koeffizienten zeigen optimale Konvergenz

für dreidimensionale und sechsdimensionale Probleme. Transformationen für krumm-

linig umrandete Gebiete besitzen variable Koeffizienten und beruhen nicht auf einem

Tensorprodukt. Die Berechnung der Steifigkeitsmatrix verwendet eine hochdimensio-

nale numerische Integration. Multiplikationen werden durch Rekursion auf eindimen-

sionale Operatoren zurückgeführt. Dazu ist im Rahmen dieser Arbeit eine umfangrei-

che Softwarebibliothek entstanden. Durch die Verwendung von Templates kann die

Implementierung auf beliebige hochdimensionale Probleme angewendet werden. Par-

allelisierung sowohl für geteilten Speicher als auch verteilte Systeme gewährleistet ei-

ne hohe Genauigkeit für große Dimensionen. Ein Ansatz mit semi-adaptiver Verfeine-

rung ermöglicht partielle Verfeinerung bei gleichzeitigem Erhalt der Tensorprodukt-

Struktur. Die Umsetzung adaptiver dünner Gitter wird als Ausblick behandelt.

v

Inhaltsverzeichnis

1 Einleitung 1

2 Diskretisierung der Finite-Elemente-Methode auf dünnen Gittern 3

2.1 Historische Entwicklung dünner Gitter . . . . . . . . . . . . . . . . . . . 4

2.2 Galerkin-Diskretisierung für dünne Gitter . . . . . . . . . . . . . . . . . . 6

2.3 Semi-Orthogonalität für variable Koeffizienten . . . . . . . . . . . . . . . 18

3 Matrix-Vektor-Multiplikation für dünne Gitter 21

3.1 Rekursive hochdimensionale Operatoren . . . . . . . . . . . . . . . . . . 22

3.2 Bilinearoperator für dünne Gitter . . . . . . . . . . . . . . . . . . . . . . . 25

3.3 Umrechnung zwischen Prewavelets und nodaler Basis . . . . . . . . . . 26

3.4 Algorithmus zur Matrix-Vektor-Multiplikation auf dünnen Gittern . . . 33

3.4.1 Eindimensionale Matrix-Vektor-Multiplikation . . . . . . . . . . . 34

3.4.2 Hochdimensionale Rekursion . . . . . . . . . . . . . . . . . . . . . 36

3.4.3 Multiplikation für inhomogene Randbedingungen mit Korrektu 43

3.5 Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.6 Komplexitätsanalyse und Kostendiskussion . . . . . . . . . . . . . . . . . 52

4 Hochdimensionale partielle Differentialgleichungen auf dünnen Gittern 55

4.1 Prewavelet-vorkonditionierte Methode der konjugierenden Gradienten 56

4.2 Variable Koeffizienten für krummlinig umrandete Gebiete . . . . . . . . 61

4.3 Variable Koeffizienten in hohen Dimensionen . . . . . . . . . . . . . . . . 65

4.4 Inhomogene Randprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5 Parallelisierung und Laufzeitanalyse 69

5.1 Parallelisierung der Vektoroperationen für geteilten Speicher . . . . . . . 70

5.2 Parallelisierung für verteilte Systeme . . . . . . . . . . . . . . . . . . . . . 75

vii

6 Erweiterung für adaptive Verfeinerung 79

6.1 Semi-adaptive Verfeinerung . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6.2 Adaptiv verfeinerte dünne Gitter . . . . . . . . . . . . . . . . . . . . . . . 85

7 Abschließende Bemerkungen 89

viii

Kapitel 1

Einleitung

Der Fluch der Dimensionen beschäftigt die numerische Mathematik seit Jahrzehnten.

Immer leistungsfähigere Großrechner haben für niedrigdimensionale Probleme we-

sentliche Fortschritte gebracht. Für hochdimensionale Probleme, und diese beginnen

bereits bei mehr als einer Handvoll Dimensionen, ist der exponentielle Anstieg der

Unbekannten der limitierende Faktor. Riesige Datenmengen müssen dazu gespeichert

und verarbeitet werden.

Ein mächtiges Werkzeug zur Reduzierung der Unbekannten sind die in [41] vor-

gestellten dünnen Gitter. Bei hinreichend glatten Funktionen liefern sie eine ähnliche

Fehlerordnung wie reguläre Gitterstrukturen.

Zwei wesentliche Ansätze haben sich für die Diskretisierung mit dünnen Gittern

durchgesetzt. Die Kombinationstechnik verlangt zur Behandlung variabler Koeffizi-

enten spezielle problemabhängige Annahmen. Der Galerkin-Ansatz ist universeller,

benötigt aber komplizierte Algorithmen zur Lösung partieller Differentialgleichungen

und ist daher weder für beliebige Dimensionen noch für adaptive Verfeinerung direkt

anwendbar.

Dieses Problem soll im Rahmen dieser Arbeit gelöst werden. Dazu wird ein Algo-

rithmus vorgestellt, der auf Basis der Galerkin-Diskretisierung eine rekursive Imple-

mentierung für hochdimensionale Räume ermöglicht. Knackpunkt ist die Multiplika-

tion mit der Diskretisierungsmatrix. Um diese effektiv durchführen zu können, wird

der zweidimensionale Ansatz aus [27] aufgegriffen.

Die Verwendung der Semi-Orthogonalität wird für höhere Dimensionen durch den

Einsatz von Prewavelets ermöglicht. Die Matrix-Vektor-Multiplikation ist die Basis für

die Methode der konjugierenden Gradienten. Durch den hierarchischen Aufbau dün-

ner Gitter und die durch Prewavelets gewonnene L2-Orthogonalität wird eine optima-

1

KAPITEL 1. EINLEITUNG

le Konditionierung O (1) erreicht.

Elliptische Differentialgleichungen werden in Kapitel 2 mit der Finite-Elemente-Me-

thode auf dünnen Gittern diskretisiert. Dazu werden geeignete Prewavelets eingeführt

und für inhomogene Randbedingungen erweitert.

Die daraus resultierende Semi-Orthogonalität wird in Kapitel 3 für einen effizienten

Algorithmus zur Matrix-Vektor-Multiplikation eingesetzt. Die Analyse der Laufzeit

zeigt dabei eine lineare Skalierung mit der Anzahl der Unbekannten.

In Kapitel 4 werden numerische Beispiele in verschiedenen Dimensionen bis d = 6

betrachtet. Für die Berechnung der Steifigkeitsmatrizen wird teilweise auf numerische

Integration zurückgegriffen. Für variable Koeffizienten ist dazu eine Integration auf

dünnen Gittern notwendig. Außerdem werden allgemeine variable Koeffizienten oh-

ne Tensorproduktstruktur sowie Koordinatentransformationen für gebogene Kanten

untersucht.

Zur Berechnung großer Tiefen in hohen Dimensionen ist zwingend eine Paralleli-

sierung notwendig. Kapitel 5 betrachtet sowohl die „shared memory“-Parallelisierung

mit OpenMP als auch die „distributed memory“=Parallelisierung mit MPI. Hauptpro-

blem ist jedoch der hohe Speicherbedarf. Dieses Problem kann auch mit verteilten Sys-

temen für reguläre dünne Gitter nicht gelöst werden.

Kapitel 6 behandelt daher abschließend eine Erweiterung für adaptive dünne Gitter.

Neben einer geeigneten Datenstruktur sind zahlreiche Anpassungen der Operatoren

für die Traversierung der Gitter notwendig.

2

Kapitel 2

Diskretisierung der Finite-Elemente-

Methode auf dünnen Gittern

Partielle Differentialgleichungen können näherungsweise auf einem Gitter mithilfe der

Finite-Elemente-Methode gelöst werden. Die Wahl des passenden Gitters wird durch

die gewünschte Genauigkeit der Berechnung beeinflusst. Bei der Wahl eines voll be-

setzten Tensorprodukt-Gitters wächst die Anzahl der Gitterpunkte für d-dimensionale

Probleme jedoch mit der Ordnung O(

Nd), wobei N der Anzahl der Gitterpunkte in

einer Dimension entspricht. Für niedrigdimensionale Probleme lässt sich oftmals ei-

ne Lösung mit akzeptablem Aufwand finden. Dagegen spricht man für Probleme mit

d ≥ 4 vom Fluch der Dimensionen, da der Speicheraufwand exponentiell anwächst

und sich auch mit modernster Computerarchitektur nicht mehr unter Kontrolle brin-

gen lässt. Diese Probleme können nicht mehr mit voll besetzten Gittern gelöst werden.

In diesem Kapitel wird eine speichersparsamere Diskretisierung mithilfe dünner

Gitter vorgestellt. Zunächst wird die Diskretisierung mithilfe der Galerkin-Methode

betrachtet. Dazu wird ein Mehrgitteransatz mit hierarchischen Überschüssen gewählt.

Bei der Wahl der Hutfunktion als Ansatzraum ergeben sich interessante Orthogona-

litätseigenschaften für zweidimensionale Poisson-Probleme. Die Orthogonalität wird

zur Entwicklung effizienter Algorithmen benötigt. Anschließend wird eine verallge-

meinerte Semi-Orthogonalität für variable Koeffizienten abgeleitet. Damit diese auch

für hochdimensionale Räume angewendet werden kann, werden L2-orthogonale Pre-

wavelets eingeführt. Diese werden abschließend durch geeignete Randelemente für

inhomogene Probleme erweitert.

3

KAPITEL 2. DISKRETISIERUNG DER FINITE-ELEMENTE-METHODE AUFDÜNNEN GITTERN

2.1 Historische Entwicklung dünner Gitter

Rechenaufwand und Speicherbedarf können durch den Einsatz dünner Gitter

zur Diskretisierung partieller Differentialgleichungen substantiell reduziert wer-

den [41, 5]. Dünne Gitter benötigen lediglich einen Speicheraufwand der Ordnung

O(

N (log (N))d−1)

. Trotzdem ist der Interpolationsfehler bei hinreichend glatten

Funktionen vergleichbar dem Einsatz eines regulären voll besetzten Gitters. Dies

macht die Verwendung dünner Gitter zur Diskretisierung partieller Differentialglei-

chungen interessant, und es haben sich in den vergangenen Jahren zahlreiche Ansätze

herausgebildet.

Der erste Ansatz von Zenger in [41] nutzte rechteckige Elemente zur Diskretisie-

rung zweidimensionaler homogener Einheitsquadrate. Da der bilineare Finite-Elemen-

te-Raum durch das kartesische Produkt aufgespannt wird, konnte die Anzahl der Un-

bekannten dadurch reduziert werden, dass besonders hochauflösende Elemente weg-

gelassen wurden (vgl. Abbildung 2.1).

Durch eine Analyse des Interpolationsfehler wurde gezeigt, dass Elemente mit re-

lativ kleinem Beitrag zum Fehler und einer großen Anzahl an Freiheitsgraden mithilfe

der Dreiecksstruktur aus Abbildung 2.4 ausgelassen werden können. Die Anzahl der

Gitterpunkte konnte dadurch für zweidimensionale von O(

N2) auf O (N log N) si-

gnifikant reduziert werden. Die Ordnung des Interpolationsfehlers wurde nur leicht

von O(h2) auf O (h log h) reduziert.

Andere Dünngitterstrukturen basieren auf einer Optimierung der Energienorm. Die

Anzahl der Gitterpunkte konnte mit O (N) noch weiter reduziert werden und weist

keine Abhängigkeit zur Dimension mehr auf. In diesem Fall fällt leider auch die Ord-

nung des Interpolationsfehlers auf O (h) [12].

In Analogie zu schwach besetzten Matrizen („sparse matrix“) wurde der Name

„sparse grid“ verwendet. Ein experimentelles Programm zur Lösung der Laplace-Glei-

chung im Einheitsquadrat mit Dirichlet-Randbedingungen in [42] zeigte, dass die Ge-

nauigkeit der Finite-Elemente-Methode auf voll besetzten Gittern nahezu erreicht wur-

de. Die Konvergenzrate des Gauß-Seidel-Verfahrens zeigte die übliche Konvergenz für

hierarchische Basen.

Zengers Ansatz wurde schon bald auf die verbreitetsten Diskretisierungen partieller

Differentialgleichungen angewendet. Der Forschungsschwerpunkt lag dabei größten-

teils auf der Kombinationstechnik, dem Ritz-Galerkin-Ansatz, der Finite-Differenzen-

Methode und der Finite-Volumen-Methode. Die Konvergenzanalyse der Kombinati-

4


onstechnik wurde in [28] und [32] gezeigt. In [23] konnte diese auch auf adaptive Ver-

feinerung übertragen werden. Das genaue Konvergenzverhalten wurde bisher noch

nicht vollständig bewiesen. Daher lag der Schwerpunkt der Forschung zur Lösung

partieller Differentialgleichungen auf dem Ritz-Galerkin-Ansatz und der Finite-Diffe-

renzen-Methode.

Die ersten Ansätze der Ritz-Galerkin-Methode mit dünnen Gittern verwendeten

ausschließlich konstante Koeffizienten und waren auf Einheitswürfel beschränkt [3, 2].

Neben stückweise linearen finiten Elementen gab es Studien sowohl zu Elementen hö-

herer Ordnung [4] als auch zu Wavelets [37]. Der „unidirectional approach“ führt hoch-

dimensionale Diskretisierungen auf eindimensionale Algorithmen zurück und iteriert

darüber mit verschachtelten Schleifen [6]. Diese Ansätze ließen sich jedoch nicht effizi-

ent auf Probleme mit variablen Koeffizienten übertragen [7, 40]. Für die Anwendung

auf reale Probleme der Physik und der Ingenieurwissenschaften ist dies jedoch essen-

tiell.

Ein erster Ansatz zur Diskretisierung allgemeiner variabler Koeffizienten mit der

Ritz-Galerkin-Methode wurde in [29] präsentiert. Durch die Verwendung hierarchi-

scher Basisfunktionen ergeben sich im zweidimensionalen Fall Semi-Orthogonalitäts-

Eigenschaften. Hierfür konnte Konvergenz gezeigt werden und eine symmetrische

Diskretisierung für symmetrische Bilinearformen abgeleitet werden [29]. Leider lässt

sich dieser Ansatz nicht direkt auf hochdimensionale Räume übertragen, da hier die

Orthogonalitäts-Eigenschaft der nodalen Basisfunktionen für d ≥ 3 nicht mehr gege-

ben ist.

Weitere Diskretisierungen partieller Differentialgleichungen mit variablen Koef-

fizienten benötigen eine wesentliche Umformulierung der ursprünglichen Bilinear-

form [1] oder verwenden die Finite-Differenzen-Methode [13]. Beide Diskretisierun-

gen führen zu einem nicht-symmetrischen linearen Gleichungssystem und erschwe-

ren deren Lösung [1, 35]. Die Konvergenz beider Verfahren konnte bisher noch nicht

vollständig gezeigt werden. Simulationen zeigen jedoch optimale Konvergenzeigen-

schaften für zwei- und dreidimensionale Probleme.

5


2.2 Galerkin-Diskretisierung für dünne Gitter

Für die Diskretisierung partieller Differentialgleichungen existieren verschiedene Ver-

fahren. Alle gitterbasierten Methoden eignen sich grundsätzlich auch für die Verwen-

dung von dünnen Gittern [43]. Als besonders beliebt haben sich die Finite-Differenzen-

Methode, die Finite-Volumen-Methode und die Finite-Elemente-Methode (FEM) er-

wiesen. Für den FEM-Ansatz wird hauptsächlich die Kombinationstechnik sowie der

Galerkin-Ansatz verwendet.

Der Vorteil der Kombinationstechnik liegt in ihrer hohen Genauigkeit und der

leichten Implementierung, während Rechenzeit und Speicheraufwand relativ hoch

sind [32]. Dagegen lässt sich die Konvergenz nur eingeschränkt beweisen. Bewei-

se für zweidimensionale Poisson-Probleme zeigen eine Konvergenz der Ordnung

O(h2 log

(h−1)). Bei zweidimensionalen elliptischen Differentialgleichungen konnte

die Konvergenz jedoch nur für ausgewählte Koeffizienten gezeigt werden [28]. Va-

riable Koeffizienten erfordern geeignete Regularitätseigenschaften und Super-Konver-

genz des Gradienten [32]. Die Erweiterung für höhere Dimensionen erfordert den Ein-

satz sehr technischer Beweise für jede Dimension und lässt sich daher nicht verallge-

meinern. Außerdem ist die Verwendung adaptiver Gitter damit nicht möglich.

Der Galerkin-Ansatz für dünne Gitter beruht dagegen auf einer hierarchischen Zer-

legung des Ansatz-Raumes [41]. Hochdimensionale Räume werden mithilfe des Ten-

sorproduktes aus eindimensionalen Basisfunktionen aufgespannt. Im Folgenden wer-

den zunächst homogene Randwertprobleme behandelt. Die Diskretisierung erfolgt mit

stückweise linearen Elementen, wobei grundsätzlich auch die Verwendung von Ele-

menten höherer Ordnung möglich wäre. Die vorgestellte nodale Basis lässt sich sehr

einfach auf inhomogene Randwertprobleme erweitern. Für die Verwendung von Pre-

wavelets müssen dagegen einige Anpassungen erfolgen. Diese werden im Anschluss

vorgestellt.

Aus dem Indexset It

It =

i|i = 1, . . . , 2t+1 − 1

(2.1)

der Tiefe t lässt sich das Gitter Ωt für ht := 2−1−t ableiten.

Das eindimensionale Gitter

Ωt = i · ht|i ∈ It (2.2)

6


der Tiefe t besitzt 2t+1 innere Gitterpunkte.

Mit Hilfe der nodalen Basis lässt sich für das Gitter Ωt der Raum

Vt = vt,i (x) |i ∈ It (2.3)

aufspannen.

Die eindimensionalen Basisfunktionen vt,i (x) (vgl. Abbildung 2.3 links) sind defi-

niert durch

vt,i (x) =

1−∣∣∣ x

ht− i∣∣∣ x ∈ [(i− 1) ht, (i + 1) ht]

0 sonst. (2.4)

Aus Ωt ⊂ Ωt+1 folgt Vt ⊂ Vt+1. Abbildung 2.3 zeigt links die schrittweise Verfeine-

rung der nodalen Basisfunktionen für die Tiefen t = 0; 1; 2.

Die hierarchische Basis wird durch den hierarchischen Überschuss

Wt := Vt \Vt−1 (2.5)

gebildet.

Dies lässt sich rekursiv für dünne Gitter der Tiefe n mit W1 = V1 erweitern:

Vn = W1 ⊕ · · · ⊕Wn (2.6)

Daraus ergibt sich die Menge der Indizes der Feingitterpunkte

Ξt := It \ 2It−1. (2.7)

Für Dimensionen d ≥ 2 werden folgende Multi-Indizes eingeführt. Die Tiefe t :=

(t1, . . . , td) ∈Nd0 eines Gitters Ωt besitzt die Indexmenge

It := (i1, . . . , id) |ik ∈ Itk . (2.8)

Entsprechend wird ebenfalls die Menge der ausschließlich auf dem Gitter der Tiefe

t vorkommenden Punkte

Ξt := (ξ1, . . . , ξd) |ξk ∈ Ξtk (2.9)

7


definiert.

Das Indexset Ξt wird als dünnes Untergitter bezeichnet, da der hierarchische Über-

schuss auf

mt =d

∏i=1

(2ti)

(2.10)

Gitterpunkten dargestellt werden kann. Das volle Untergitter mit It besitzt dagegen

ebenso die Gitterpunkte der Grobgitterpunkte. Hierfür ergeben sich insgesamt

nt =d

∏i=1

(2ti+1 − 1

)(2.11)

Gitterpunkte.

Die entsprechende Basisfunktion

vt,i (x) :=d

∏k=1

vtk,ik (xk) (2.12)

wird durch das d-dimensionale Tensorprodukt erweitert.

Daraus ergibt sich der nodale Raum

Vt :=vt,i (x) |i ∈ It (2.13)

mit Tiefenvektor t sowie der zugehörige Raum

Wt :=vt,ξ (x) |ξ ∈ Ξt (2.14)

der hierarchischen Überschüsse.

Zur Definition des hierarchischen Aufbaus des Raumes des vollen Gitters Vn sowie

des Dünngitterraumes VDn werden folgende Metriken benötigt:

‖t‖∞ := max t1, . . . , td (2.15)

|t| :=d

∑k=1

ik (2.16)

8


Die daraus abgeleiteten Räume

Vn =⊕‖t‖∞<n

Wt (2.17)

VDn =⊕|t|<n

Wt (2.18)

besitzen die maximale Tiefe n.

n=1 n=2 n=3

Abbildung 2.1: Reguläres volles Gitter Ω3 und dünnes Gitter ΩDn für n = 1; 2; 3

Abbildung 2.2: ΩDn für n = 3

Nun wird ein dünnes Gitter ΩDn mit maximaler Tiefe n betrachtet (vgl. Abbil-

dung 2.2 für n = 3). Gesucht wird eine Funktion un (x) ∈ VDn die wie folgt auf dem

9


dünnen Gitter Dn dargestellt werden kann:

uDn (x) = ∑|t|<n

∑i∈Ξt

ut,ivt,i (x) (2.19)

Die folgende elliptische Differentialgleichung soll gelöst werden.

Problem 1. Seien f ∈ L2(ΩDn) und κ ≥ 0 gegeben. Suche u ∈ H10(ΩDn) für

a (u, v) :=∫

Ω(∇u)T A∇v + κuv dx, A ∈ Kn

f (v) :=∫

Ωf v dx

so dass

a (u, v) = f (v) für alle v ∈ H10 (ΩDn) . (2.20)

Anhand der hierarchischen Diskretisierungen (2.19) von VDn ergibt sich folgendes

lineares Gleichungssystem:

a(t,i),(t,j) :=a(vt,i, vt,j

)f(t,j) := f

(vt,j)

∑|t|<n

∑i∈Ξt

u(t,i) a(t,i),(t,j) = ft,j ∀ |t| < n, j ∈ Ξt (2.21)

Besonderes Augenmerk wird der Berechnung der Koeffizienten a(t,i),(t,j) gewidmet.

Dies wird beispielhaft anhand der Berechnung für Tiefe t = (0, 2) und Tiefe t = (2, 0)

gezeigt. Abbildung 2.4 zeigt die Träger der Basisfunktionen i = (2, 1) für t und j =

(1, 2) für t.

Aufgrund der Überlappung beider Träger muss der Wert des Bilinearoperators

a(vt,i, vt,j

)genauer betrachtet werden. Aus |max (t, t)| ≥ n folgt, dass die Gitter-

punkte der beiden Basisfunktionen außerhalb der Überlappung der jeweiligen Träger

liegen. Entscheidend dafür ist, dass sich die Tiefen beider Basisfunktionen t = (t1, t2)

und t = (t1, t2) in beiden Dimensionen wie folgt unterscheiden:

t1 < t1

t2 > t2

10


Für die Berechnung wird Ωtmax benötigt, wobei tmax := (tmax,i)i=1,...,d mit tmax,i =

max ti, ti. Im Beispiel für n = 3 wird für die Berechnung das Gitter tmax = (2, 2) be-

nötigt. Dessen Verwendung würde aber aufgrund des zusätzlichen Speicheraufwands

die Effektivität der dünnen Gitter eliminieren [27]. Für zweidimensionale dünne Gitter

kann auf die Berechnung überlappender Träger verzichtet werden, da die jeweiligen

Basisfunktionen orthogonal sind.

Lemma 1. Sei A = diag (a1, a2) eine konstante Diagonalmatrix. So gilt für die Indizes t und

t mit |max (t, t)| ≥ n und

max (t, t) = (max t1 t1 , max t2 t2) (2.22)

dass ∫Ω(∇vt,i)

T A∇vt,j = 0. (2.23)

Beweis. ∫Ω(∇vt,i)

T A∇vt,j dx =

∫Ω

(∇

2

∏k=1

vtk,ik (xk)

)T

A

(∇

2

∏k=1

vtk,jk (xk)

)dx =

2

∑l=1

al

∫Ω

∂

∂xl

(2

∏k=1

vtk,ik (xk)

)∂

∂xl

(2

∏k=1

vtk,jk (xk)

)dx = 0

Es gilt∫

∂∂xl

vtl ,il (xl)∂

∂xlvtl ,jl (xl) dxl = 0 falls tl 6= tl. Dies folgt für d = 2 aus

|max (t, t)| ≥ n.

11


In [29] wird ein Mehrgitterverfahren zur Lösung zweidimensionaler elliptischer Dif-

ferentialgleichungen auf dünnen Gittern vorgestellt. Dazu muss das Gitter in einem

bestimmten Muster, dem sogenannten Q-Zyklus, durchlaufen werden. Dieser besteht

aus zwei Durchläufen. Auf dem Hinweg werden alle bekannten Anteile der Lösung

mit der Diskretisierungsmatrix multipliziert und von der rechten Seite aller Nachfol-

ger subtrahiert. Der Rückweg dient der Verteilung an alle Vorgänger. Dadurch wird

gewährleistet, dass die lokale Lösung keine Anteile anderer Gitter beinhaltet. Das Glei-

chungssystem wurde zuvor entsprechend korrigiert.

Für die aktualisierte lokale Lösung muss anschließend die Differenz zur vorheri-

gen Lösung wieder durch einen Q-Zyklus verteilt werden. Entscheidend für den Q-

Zyklus ist, dass alle Untergitter pro Durchlauf nur einmal angelaufen werden. Daher

wird ein Pfad benötigt, der das dünne Gitter durch Prolongationen und Restriktionen

vollständig ohne Verzweigungen durchläuft.

Eine Erweiterung auf dreidimensionale Räume ist grundsätzlich möglich [24, 25].

Allerdings lässt sich kein allgemeingültiges Schema für ein hochdimensionales Muster

dieses Pfades ausmachen. Daher wurde dieser Ansatz im Rahmen dieser Arbeit nicht

weiter verfolgt.

0

1

x0,1

v0,1

V1t = 0

0

1

x1,1 x1,3

v1,1 v1,3

W2t = 1

0

1

x2,1 x2,3 x2,5 x2,7

v2,1 v2,3 v2,5 v2,7

W3t = 2

V3

0

1

x0,1

v0,1

V1

0

1

x1,1 x1,2 x1,3

v1,1 v1,2 v1,3

V2

0

1

x2,1 x2,2 x2,3 x2,4 x2,5 x2,6x2,7

v2,1 v2,2 v2,3 v2,4 v2,5 v2,6 v2,7

V3

Abbildung 2.3: Nodale Basis (links) sowie hierarchische nodale Basisfunktionen(rechts)

Die Algorithmen des Q-Zyklus basieren auf a-Orthogonalität für überlappende Ge-

biete. Dies bedeutet für zweidimensionale Probleme gemäß |max (t, t)| ≥ n, dass in

12


ϕt,i

ϕt′,j

Abbildung 2.4: Überlappende Träger zweier Basisfunktionen vt,i und vt,j mit|max (t, t)| ≥ n

allen Dimensionen unterschiedliche Tiefen für t und t vorliegen. Für hochdimensiona-

le Gebiete ist diese Einschränkung jedoch zu strikt. Auch hier wäre es wünschenswert,

dass Orthogonalität bereits bei überlappenden Gebieten vorliegt. Folglich unterschei-

den sich die Tiefen nur in zwei Dimensionen. Dies ist jedoch nur durch die Verwen-

dung von L2-orthogonalen hierarchischen Basisfunktionen ϕt,i möglich.

Lemma 2. Sei A = diag (a1, . . . , ad) eine konstante Diagonalmatrix. So gilt für die Tiefen t

und t mit |max (t, t)| ≥ n für

max (t, t) = (max t1 t1 , . . . , max td td) (2.24)

und alle i ∈ Ξt, j ∈ Ξt, dass ∫Ω(∇ϕt,i)

T A∇ϕt,j = 0 (2.25)

für L2-orthogonale Basisfunktionen.

Beweis. ∫Ω(∇ϕt,i)

T A∇ϕt,j dx =

∫Ω

(∇

d

∏k=1

ϕtk,ik (xk)

)T

A

(∇

d

∏k=1

ϕtk,jk (xk)

)dx =

d

∑l=1

al

d

∏k=1

∫Ω

∂

∂xlϕtk,ik

∂

∂xlϕtk,jk dxk = 0

Es gilt∫

∂∂xl

vtk,ik (xk)∂

∂xlvtk,jk (xk) dxk = 0 falls k 6= l und tk 6= tk. Dies folgt aus tk < tk

und tl > tl für überlappende Gebiete.

Besonders geeignet sind dazu L2-orthogonale Prewavelet-Basisfunktionen. Hierzu

13


werden stückweise lineare Funktionen mit nodaler Repräsentation auf Ξt verwendet.

Zur Lösung partieller Differentialgleichungen mit Prewavelets gibt es zahlreiche An-

wendungen. Bei Mehrgitterverfahren führen sie aufgrund ihrer hervorragenden Kon-

ditionszahl zu schnellen und robusten Lösern [10, 39]. Geeignete Prewavelet-Basen be-

sitzen kleine kompakte Träger. Als Tensorproduktbasis können sie zur Diskretisierung

dünner Gitter verwendet werden. Die Umrechnung zwischen hierarchischer Basis und

Prewavelets reduziert sich folglich zu einem eindimensionalen Problem [8, 14, 16, 22].

Für den eindimensionalen Fall wird Wt ⊆ Vt betrachtet, sodass Wt⊕

L2 Vt−1. An-

hand der Basisfunktionen vt,i ∈ Vt aus Abbildung 2.4 werden die Prewavelets aus

Abbildung 2.5 in [30] definiert:

ϕt,i =

910 vt,i − 3

5 vt,i+1 +1

10 vt,i+2 falls i = 1

vt,i − 35(vt,i+1 + vt,i−1) +

110(vt,i+2 + vt,i−2) falls 3 ≤ i ≤ 2t − 3, i ∈ Ξt

110 vt,i−2 − 3

5 vt,i−1 +9

10 vt,i falls i = 2t − 1

(2.26)

Wobei ϕt,1 die Prewavelet-Funktion am linken Rand und ϕt,2t−1 die Prewavelet-

Funktion am rechten Rand für t > 0 ist.

Sei ϕ0,1 = v0,1 ∈ V0 die gröbste Basisfunktion, die um den Punkt 2−1 zentriert ist.

Daraus ergibt sich die hierarchische Prewavelet-Basis in Abbildung 2.6. Die hierarchi-

sche Basis weist nun L2-Orthogonalität für Funktionen aus unterschiedlichen Tiefen t

und t auf.

Daher gilt für t 6= t

∫ 1

0ϕt,i ϕt,jdx = 0. (2.27)

Die Orthogonalitätseigenschaft der Prewavelet-Basis kann auch auf Helmholtz-

Operatoren mit variablen Koeffizienten in hochdimensionalen Räumen erweitert wer-

den [31]. Die dazu benötigte Semi-Orthogonalität wird in Abschnitt 2.3 erläutert.

Die vorgestellten Prewavelets besitzen homogene Randbedingungen und eignen

sich daher auch als Dualraum. Mit Dualraum wird dabei der Raum der Testfunktionen

bezeichnet.

Für inhomogene Probleme liegt der Ansatz nahe, auf dem gröbsten Level zusätz-

liche Hut-Elemente an den Randpunkten einzuführen. Abbildung 2.7 zeigt diese als

14


-0.6

0.1

1

xt,i−3 xt,i−2 xt,i−1 xt,i xt,i+1 xt,i+2 xt,i+3

ϕt,i

Abbildung 2.5: Prewavelet-Basisfunktion zentriert um Punkt xt,i

gestrichelte und gepunktete halbseitige Hutfunktionen an den Randpunkten x0,0 und

x0,2 in V0. Dirichlet-Prewavelets können aufgrund ihrer fehlenden L2-Orthogonalität

mit der halbseitigen Hutfunktion am Rand nicht zur Diskretisierung dünner Gitter

verwendet werden. Das Problem der Orthogonalität für inhomogene Randwertproble-

me wird durch die in [30] vorgestellten Prewavelets für Neumann Randbedingungen

gelöst (Abbildung 2.7).

Sie unterscheiden sich von (2.26) durch die Randelemente ϕt,1 am linken bzw. ϕt,2t−1

am rechten Rand für t > 0:

ϕt,i =

−6

5 vt,i−1 +1110 vt,i − 3

5 vt,i+1 +1

10 vt,i+2 falls i = 1

vt,i − 35(vt,i+1 + vt,i−1) +

110(vt,i+2 + vt,i−2) falls 3 ≤ i ≤ 2t − 3, i ∈ Ξt

110 vt,i−2 − 3

5 vt,i−1 +1110 vt,i − 6

5 vt,i+1 falls i = 2t − 1

(2.28)

Der Einsatz von Neumann-Prewavelets beschränkt sich lediglich auf den Primär-

raum. Die fehlende Homogenität verhindert eine direkte Verwendung als Dualraum.

Homogenität kann durch ein geeignetes Korrekturverfahren erreicht werden. In Ab-

schnitt 3.4.3 wird ein Korrekturverfahren vorgestellt, das den Dualraum zunächst in

die nodale Basis umgerechnet und anschließend in Prewavelet-Basisfunktionen mit

Dirichlet-Randbedingungen umwandelt. Über diesen Umweg kann zuerst Semi-Or-

thogonalität und anschließend Homogenität gewährleistet werden.

Sei u = g am Rande von Ω. So kann u in eine Randfunktion uR und die Funktion

im Inneren uI zerlegt werden. Daraus ergibt sich das inhomogene Randwertproblem.

15


0

1

0 x0,1 1

ϕ0,1

V1t = 0

0

1

0 x1,1 x1,3 1

ϕ1,1 ϕ1,3

W2t = 1

0

1

0 x2,1 x2,3 x2,5 x2,7 1

ϕ2,1ϕ2,3 ϕ2,5 ϕ2,7

W3t = 2

V3

Abbildung 2.6: Prewavelet-Basisfunktionen mit Dirichlet-Randbedingungen

Problem 2. Seien f ∈ L2(ΩDn) und κ ≥ 0 gegeben. Suche uI ∈ H10(ΩDn) für

a (uI , v) :=∫


a (uR, v) :=∫


f (v) :=∫

Ωf v dx

so dass

a (uI , v) = f (v)− a (uR, v) für alle v ∈ H10 (ΩDn) . (2.29)

Zunächst erfolgt eine Zerlegung der Randfunktion uR anhand der Neumann Prewa-

velets. Nach Anwendung des Bilinearoperator wird der Dualraum mithilfe des Kor-

rekturverfahrens in Dirichlet-Prewavelets überführt. Durch Subtraktion dieses Terms

von der rechten Seite wird das Problem in ein homogenes Randwertproblem über-

führt. Für die Berechnung der rechten Seite f (v) muss ebenfalls eine Zerlegung von f

für Neumann-Prewavelets durchgeführt werden. Auch hier ist eine Überführung des

Dualraumes in Dirichlet-Prewavelets notwendig.

16


0

1

x0,0 = 0 x0,1 x0,2 = 1

ϕ0,0 ϕ0,1 ϕ0,2

V1t = 0

-1.2

00.1

11.1

0 x1,1 x1,3 1

ϕ1,1 ϕ1,1

W2t = 1

-1.2

00.1

11.1

0 x2,1 x2,3 x2,5 x2,7 1

ϕ3,1 ϕ3,3 ϕ3,5ϕ3,7

W3t = 2

V3

Abbildung 2.7: Prewavelet-Basisfunktionen mit Neumann-Randbedingungen

17


2.3 Semi-Orthogonalität für variable Koeffizienten

Bereits in [29] wurde gezeigt, dass die Orthogonalität der nodalen Basis für zweidi-

mensionale Räume auch auf variable Koeffizienten des Helmholtzoperators erweitert

werden kann.

Problem 3. Seien f ∈ L2(Ω) sowie κ (x) ∈ L∞(Ω), κ (x) ≥ 0 gegeben. Suche u ∈ H10(Ω)

für

a (u, v) :=∫

Ω(∇uA (x))T∇v + κ (x) uv dx

f (v) :=∫

Ωf v dx

so dass

a (u, v) = f (v) für alle v ∈ H10 (Ω) . (2.30)

Dazu wurde die Bilinearform a durch eine vereinfachte Bilinearform mit Semi-Or-

thogonalität

ason(vt,i, vt,j

):=

0 falls |max (t, t)| ≥ n

an(vt,i, vt,j

)sonst

(2.31)

ersetzt. Die Einträge a(t,i),(t,j) der Diskretisierungsmatrix werden zu Null für überlap-

pende Funktionen mit |max (t, t)| ≥ n. Dadurch entfällt die aufwendige Berechnung

für überlappende Träger, und die Berechnung der Matrix-Vektor-Multiplikation kann

vollständig auf dem dünnen Gitter ausgeführt werden.

Die Bilinearform mit Semi-Orthogonalität weist für sämtliche elliptische partielle

Differentialgleichungen ähnliche Ortogonalitätseigenschaften wie die Helmholtzglei-

chung mit konstanten Koeffizienten auf. Durch die Verwendung der nodalen Basis

ist der Einsatz der Semi-Orthogonalität jedoch auf den zweidimensionalen Raum be-

schränkt. Im vorherigen Abschnitt wurde daher eine Erweiterung mit Prewavelets für

konstante Koeffizienten betrachtet. Diese Basis kann mit der Bilinearform mit Semi-

Orthogonalität kombiniert werden und ermöglicht die Diskretisierung variabler Koef-

fizienten auf hochdimensionalen dünnen Gittern.

18


In [31] wird gezeigt, dass der entstandene Diskretisierungsfehler für dünne Gitter

Dn mit n > n0 durch die Konstanten Kl und Ku für alle v, w ∈ VDn mit

‖v‖H1(Ω)Kl ≤√

a(v, v) ≤ Ku‖v‖H1(Ω) und (2.32)

an(v, w) ≤ Ku‖v‖H1(Ω)‖w‖H1(Ω) (2.33)

abgeschätzt werden kann.

Anhand der Norm für gemischte Ableitungen der Ordnung 2

‖u‖2M2(Ω) := ∑

(k1,...,kd)∈Nd0 |kj≤2

‖d

∏j=1

∂kj

∂xkjj

u‖L2(Ω) (2.34)

lässt sich ein Konvergenzbeweis für Problem 3 mit Dimension d ableiten:

‖u− uDn‖H1 ≤ C ‖u‖M2(Ω) h(

log(

h−1)d−1

)(2.35)

Für die Galerkin-Diskretisierung mit multilinearen finiten Elementen konnte damit

eine Konvergenz der Ordnung O(

h(log(h−1))d−1

)in der H1-Norm für Semi-Ortho-

gonalität bewiesen werden. Sie besitzt damit dieselbe Ordnung wie die Dünngitterin-

terpolation des variablen Koeffizienten. Dadurch konnte die optimale Konvergenzord-

nung in der H1-Norm gezeigt werden.

Numerische Ergebnisse in [19] zeigen eine Konvergenzgeschwindigkeit

O(

h2 (log(h−1))d−1

)in der L2-Norm wie auch in der Maximumsnorm. Dies

deckt sich im Falle d = 2 mit den Ergebnissen aus [29]. Das Konvergenzverhalten

der Dünngitterinterpolation führt zur Erkenntnis, dass uDn auf dem dünnen Gitter

zur exakten Lösung u mit O(h2 log

(h−1)) für h = 2−n sowohl in der L2-Norm

als auch in der Maximumsnorm konvergiert. Der variable Koeffizient wurde durch

eine stückweise konstante Interpolation auf dem dünnen Gitter ersetzt. Dadurch

ergibt sich eine vereinfachte Integration der rechten Seite sowie des Bilinearopera-

tors [26, 27]. Ein Konvergenzbeweis der Dünngitterdiskretisierung für die L2-Norm

und Maximumsnorm mit optimaler Fehlerordnung ist bis jetzt noch nicht gelungen.

Anhand von numerischen Beispielen kann gezeigt werden, dass durch Verwendung

der Semi-Orthogonalität robuste und effiziente Mehrgitterverfahren möglich sind. Der

Q-Zyklus in [29] ähnelt sehr dem bekannten V-Zyklus und verwendet Standardrouti-

nen der Mehrgitter-Algorithmik auf zweidimensionalen dünnen Gittern. Mehrgitter-

19


löser haben folglich einen Rechenaufwand der OrdnungO (N log N) für eine Iteration

sowieO (1) für die Konvergenzgeschwindigkeit.O (N log N) entspricht dabei der An-

zahl der Gitterpunkte des zweidimensionalen dünnen Gitters. Außerdem lässt sich der

Ansatz ebenfalls auf adaptive dünne Gitter und komplexe Geometrien anwenden.

In [31] wurde dieser Ansatz auf hochdimensionale Helmholtzgleichung erweitert.

Eine Erweiterung auf beliebige elliptische, partielle Differentialgleichungen bedarf

noch einer erweiterten Konvergenzanalyse. Erste numerische Ergebnisse hierzu wur-

den in [19, 20] vorgestellt.

20

Kapitel 3

Matrix-Vektor-Multiplikation für

dünne Gitter

Die Galerkin-Diskretisierung mit Semi-Orthogonalität aus Kapitel 2 liefert schwach

besetzte Diskretisierungsmatrizen. Dies konnte dadurch erreicht werden, dass der Bi-

linearoperator für überlappende Elemente auf Null gesetzt wurde, ohne dass sich da-

durch die Konvergenzordnung ändert. Mithilfe der Prewavelet-Diskretisierung wurde

eine hierarchische Basis gefunden, die Semi-Orthogonalität auch in hochdimensiona-

len Räumen gewährleistet. Für die Zerlegung einer Funktion mithilfe der hierarchi-

schen Basis verteilen sich die Koeffizienten auf die einzelnen Level des dünnen Git-

ters. Geeignete iterative Verfahren zur Lösung des linearen Gleichungssystems benöti-

gen zur effizienten Realisierung eine schnelle Anwendung der Steifigkeitsmatrix und

der Massenmatrix auf einen Vektor. Dazu müssen die Koeffizienten von allen Gittern

eingesammelt werden. Effiziente Verfahren lösen dies mit einer konstanten Anzahl an

Rechenoperationen pro Gitterpunkt [2].

Zunächst wird eine Transformation zwischen nodaler Basis und hierarchischer Pre-

wavelet-Basis vorgestellt. Eine effiziente Berechnung ist in hochdimensionalen Räu-

men nur dann möglich, wenn sie sich auf eindimensionale Operatoren zurückführen

lässt.

Die Berechnung der Matrix-Vektor-Multiplikation erfolgt mithilfe eines rekursiven

Algorithmus. Die Grundidee ist dabei die Aufteilung in eindimensionale Operatoren

zur Prolongation und Restriktion. Dieser Ansatz ist bewährt und wurde zum Beispiel

von [33] verwendet.

Weitere Ansätze [2, 3, 16, 25] verlangen ebenso eine Zerlegung der Bilinearform.

Da die Tensorproduktstruktur des zugrunde liegenden Operators genutzt wird, kann

21

KAPITEL 3. MATRIX-VEKTOR-MULTIPLIKATION FÜR DÜNNE GITTER

dieses Verfahren nicht für allgemeine variable Koeffizienten angewendet werden. Das

Verfahren von Schwab und Todor [36] für beliebige variable Koeffizienten hat dagegen

nur einen suboptimalen Rechenaufwand [40].

Der folgende Ansatz vereint optimalen Rechenaufwand und allgemeine variable

Koeffizienten. Durch die getrennte Abfolge von Prolongationen und Restriktionen

können die hierarchischen Überschüsse eines jeden Untergitters auf alle anderen Gitter

verteilt werden. Entscheidend ist dabei der Zeitpunkt der Multiplikation mit der Dis-

kretisierungsmatrix. Da dies zwischen dem Wechsel von Prolongation auf Restriktion

erfolgt, müssen diese streng getrennt werden. Die Überlappung von Basisfunktionen,

deren Verbindungspfad nur über Restriktion vor Prolongation auf dem dünnen Git-

ter erreicht werden kann, wird dadurch ignoriert. Da sich diese Anteile aber mit der

im vorigen Kapitel vorgestellten Semi-Orthogonalität decken, kann ohne zusätzlichen

Fehler auf deren Berechnung verzichtetet werden.

3.1 Rekursive hochdimensionale Operatoren

Für die weitere Berechnung werden einige Operatoren benötigt, die entweder lokal

auf einem vollen Untergitter agieren oder den Transfer zwischen zwei Gittern realisie-

ren. Sie lassen sich stets auf eindimensionale Operationen zurückführen und sind sehr

einfach in hochdimensionalen Räumen zu implementieren.

Der Prolongationsoperator P tt ermöglicht die dimensionsweise Interpolation von

Vt nach Vt, wobei t ≥ t sowie t − t ≤ 1 gilt. Daraus folgt ti − ti ∈ 0, 1 für alle

i ∈ 1, . . . , d. In der Regel wird jedoch nur in einer Dimension k prolongiert, sodass

tk − tk = 1 und ti − ti = 0 für i 6= k.

Der Operator P tt wird definiert durch

P tt :Rnt 7→ Rnt (3.1)

u 7→(

d⊗i=1

Ptiti

)u.

Dabei entspricht die eindimensionale Prolongationsmatrix Ptt entweder der Identi-

tätsmatrix Iti im Falle ti = ti oder Pt im Falle ti = ti − 1. Der eindimensionale Operator

22


Pt hat folgende Matrixform:

Pt =12

2

1 1

2

1 1. . .

1 1

2

Zur Vergröberung werden der Restriktionsoperator

Rtt :Rnt 7→ Rnt (3.2)

u 7→(

d⊗i=1

Rtiti

)

und der Vergröberungsoperator

C tt :Rnt 7→ Rnt (3.3)

u 7→(

d⊗i=1

Ctiti

)u

benötigt.

Auch hier lassen sich wiederum Rt und Ct für ti = ti + 1 als eindimensionale Matri-

zen

Rt =12

2 1

1 2 1

1 2 1. . .

1 2 1

1 2

23


und

Ct =

1 0

0 1 0

0 1 0. . .

0 1

darstellen.

Zuletzt werden Operatoren zur Umrechnung der Koeffizienten in der Prewavelet-

Basis in die nodale Basis benötigt. Hierbei wird zwischen Primärraum und Dualraum

unterschieden. Der Primärraum dient der Repräsentation der Lösung u. Im Gegensatz

zu Kapitel 2 ist der Dualraum nun nicht mehr der Testraum. Er bezeichnet das Ergebnis

der Anwendung des Bilinearoperators ason (u, ϕt,k) auf Testfunktionen ϕt,k.

Es gibt je einen Operator zur Umrechnung der Prewavelet-Koeffizienten in die no-

dale Basis im Primärraum

St :Rnt 7→ Rnt (3.4)

u 7→(

d⊗i=1

Sti

)u

sowie für den Dualraum

Dt :Rnt 7→ Rnt (3.5)

u 7→(

d⊗i=1

Dti

)u.

Da das Level nicht verändert wird, handelt es sich bei

St =

910 0 1

10

−35 0 −3

5 01

10 0 1 0 110

−35 0 −3

5110 0 1 0 1

10. . . . . . . . . . . . . . .

110 0 1 0 1

10

0 −35 0 −3

51

10 0 910

24


und

Dt =

910 −

35

110

0 0 0 0110 −

35 1 −3

5110

0 0 0 0 01

10 −35 1 −3

5110

. . . . . . . . . . . . . . .110 −3

5 1 −35

110

0 0 0 0110 −3

59

10

jeweils um quadratische Matrizen. Die Nullzeilen bzw. Nullspalten entstehen dadurch,

dass Prewavelet-Koeffizienten nicht auf groben Gitterpunkten gespeichert werden.

3.2 Bilinearoperator für dünne Gitter

Im Gegensatz zu den Operatoren aus Abschnitt 3.1 kann die Multiplikation der Dis-

kretisierungsmatrix nicht als Tensorprodukt ausgeführt werden. Für jeden Gitterpunkt

auf den vollen Untergittern ergeben sich daher 3d Einträge in der Diskretisierungsma-

trix At des Gitters der Tiefe t. Die Diskretisierung erfolgt für die nodale Basis. Der zu

multiplizierende Vektor wird mit Operator (3.4) in die nodale Basis überführt und das

Ergebnis der Multiplikation abschließend in die Prewavelet-Basis zurückgeführt.

Die Anwendung der Diskretisierungsmatrix reduziert sich daher auf die Multipli-

kation At · u sowie den zugehörigen Operator

At :Rnt 7→ Rnt (3.6)

u 7→ Atu.

Matrix At wurde dazu mithilfe der nodalen Basis aus Abbildung 2.3 diskretisiert.

Die Abspeicherung erfolgt für jeden Punkt des vollen Untergitters auf einem Diskre-

tisierungsstern mit 3d Einträgen. Abbildung 3.1 zeigt die jeweiligen vollen Untergitter

eines dünnen Gitters der Tiefe n = 3.

25


Abbildung 3.1: Dünnes Gitter für die Berechnung der Bilinearoperatorenmit Tiefe n = 3

3.3 Umrechnung zwischen Prewavelets

und nodaler Basis

Zur Berechnung der Prewavelet-Koeffizienten liegt die Funktion in nodaler Basis vor.

Dies bedeutet, dass auf allen vollen Untergittern mit |t| < n der Funktionswert für

jeden Gitterpunkt i ∈ It vorgehalten wird. Diese Zuweisung kann sehr einfach durch

die Auswertung eines Funktionszeigers an den entsprechenden Koordinaten realisiert

werden.

Ausgehend von der nodalen Basis ist auch eine Umwandlung in die hierarchische

Basis möglich. Hierzu wird ein ähnlicher Algorithmus wie zur Umrechnung in Prewa-

velets verwendet. Ein Algorithmus hierzu findet sich beispielsweise in [2].

Für die Umrechnung in Prewavelets ist das Lösen eines Gleichungssystems notwen-

dig. Dazu wird die Berechnung auf eindimensionale Operationen zurückgeführt. Die

nodale Basis wird dabei in einen Prewavelet-Anteil sowie den Grobgitteranteil zerlegt.

Hierzu wird das Gleichungssystem WDirichlet x = b gelöst, wobei b die Darstellung mit

nodaler Basis ist und x sowohl die Koeffizienten der Prewavelets aus Wti als auch der

nodalen Grobgitterbasis Vti−1 enthält. Die Bandmatrix WDirichlet kann mit einer LU-

Zerlegung effektiv gelöst werden. Der Rechenaufwand ist dabei linear bezüglich der

Anzahl der Einträge des Vektors.

26


Für jede Tiefe ti muss die Matrix

WDirichlet =

910

12

110

−35 1 −3

5110

12 1 1

21

10

−35 1 −3

5110

12 1 1

21

10. . . . . . . . . . . . . . .

110

12 1 1

2110

−35 1 −3

51

1012

910

(3.7)

zerlegt werden. WDirichlet setzt sich zusammen aus zwei Dirichlet-Randelementen,(2ti − 2

)Prewavelets sowie den

(2ti − 1

)nodalen Basiselementen des Grobgitters. Im

Falle regulärer dünner Gitter sind die Matrizen unabhängig von der Dimension. Das

Gleichungssystem muss für Neumann-Randbedingungen (siehe 2.28) entsprechend

angepasst werden. An den Rändern werden zwei zusätzliche halbseitige nodale Ba-

sisfunktionen hinzugefügt.

Die Größe des Gleichungssystems WNeumann x = b mit

WNeumann =

1 −65

12

1110

12

110

−35 1 −3

51

1012 1 1

2110

−35 1 −3

5. . . . . . . . . . . . . . .

110

12 1 1

21

10

−35 1 −3

51

1012

1110

12

−65 1

(3.8)

erhöht sich dadurch auf(2t+1 + 1

)Freiheitsgrade.

Abbildung 3.2a zeigt die Umrechnung in Prewavelets für ein zweidimensiona-

les Vollgitter der Tiefe n = 4. Rote Pfeile sind dabei ausschließlich auf vollen Git-

tern vorhanden, während schwarze Pfeile auch auf dünnen Gittern abgelaufen wer-

den können. Der Algorithmus beginnt für volle Gitter am Level mit maximaler Tiefe

27


t1 = t2 = n− 1. Dazu werden zuerst in y-Richtung die Prewavelet-Koeffizienten sowie

der Grobgitteranteil für t2 = n− 2 anhand der LU-Zerlegung ermittelt. Der Grobgit-

teranteil wird auf das entsprechende Gitter übertragen und dort das Gleichungssys-

tem erneut gelöst. Daher wird t2 von n − 1 bis 0 iteriert. Zusätzlich wird nach jeder

Zerlegung je ein rekursiver Funktionsaufruf in x-Richtung gestartet. Dadurch erfolgt

schrittweise eine Zerlegung in allen Dimensionen.

Im Falle dünner Gitter müssen die roten Pfade in Abbildung 3.2a durch die alter-

nativen blauen Pfade ersetzt werden. Für blaue Pfeile wird eine Prolongation benö-

tigt, da keine direkten Vorgänger vorhanden sind. Zur leichteren Berechnung werden

die Berechnungen für alle Dimensionen jeweils in separate Durchläufe unterteilt. Für

jede Dimension erfolgt weiterhin ein rekursiver Funktionsaufruf über alle Gitter. Al-

gorithmus 1 iteriert daher zunächst über alle Dimensionen und startet jeweils einen

rekursiven Aufruf.

Abbildung 3.2b zeigt die separate Berechnung in y sowie Abbildung 3.2c in x-Rich-

tung. Für den ersten Durchlauf muss zusätzlich noch prolongiert werden. Die gepunk-

teten Pfeile stehen dabei für die Prolongation in allen tieferen Dimensionen.

Im ersten Durchlauf erfolgt ausschließlich eine LU-Zerlegung in y-Richtung, an-

schließend im zweiten Durchlauf in x-Richtung. Alle Dimensionen ohne Zerlegung

werden jeweils rekursiv durchlaufen, um eine vollständige Abdeckung des gesamten

dünnen Gitters zu gewährleisten. Im Folgenden wird dieses Verfahren als ebenenweise

Abarbeitung bezeichnet, da die aktuelle Ebene der Tiefe t = (t1, . . . , td) ∈ Dn zu Tiefe

t mit ti = ti − 1 für Dimension i vergröbert wird. Die aktuelle Dimension bezieht sich

dabei auf die Berechnung der LU-Zerlegung, für alle niedrigeren Dimensionen wird

prolongiert.

Algorithmus 1 startet mit maximaler Tiefe ti = n− 1. Damit t ∈ Dn erfüllt ist, muss

für alle k 6= i erfüllt sein, dass tk = 0. In Abbildung 3.2c entspricht dies t = (0, 3) bzw.

t = (3, 0) in Abbildung 3.2b.

Abbildung 3.3 zeigt die Umrechnung für dreidimensionale dünne Gitter und deren

Aufteilung in je eine Berechnung für alle Dimensionen. Abbildung 3.3a startet dabei

mit Tiefe t = (0, 0, 3). Nach Berechnung der Prewavelet-Koeffizienten wird daraus mit

Operator S der nodale Überschuss ermittelt. Für t = (0, 0, 2) wird der Überschuss von

(0, 0, 3) anschließend nach (1, 0, 2) und (0, 1, 2) prolongiert und dort subtrahiert. Für

die nächsttiefere Ebene t3 = 1 muss die Prolongation des Überschusses für (1, 1, 1)

28


mithilfe der Kombinationsformel

∑tk=tk ∀k≥δ

(tk−tk)∈0,1 ∀k<δ

(−1)|t−t| P tt (Ct) (3.9)

berechnet werden.

Die Berechnungen der x- und y-Richtung entspricht ebenenweise der zweidimen-

sionalen Berechnung. Für alle Elemente einer Zeile (y-Richtung) bzw. Spalte (x-Rich-

tung) wird die Zerlegung in Prewavelet-Überschuss und Grobgitteranteil mithilfe der

LU-Zerlegung berechnet. Der Grobgitteranteil liegt in nodaler Basis vor, während der

Überschuss als Prewavelet-Koeffizienten gegeben ist. Zur weiteren Berechnung wird

der Überschuss der Zerlegung wieder in die nodale Basis umgerechnet und muss an-

schließend von allen gröberen Gittern subtrahiert werden. Hierzu verwendet Algo-

rithmus 1 einen Korrekturvektor ~C. Dieser speichert den aktuellen Prewavelet-Anteil

sowie alle vorherigen mit Tiefe größer ti.

(a) Vollgitter (b) Dimension y (c) Dimension x

Abbildung 3.2: Aufteilung der Umrechnung von nodaler Basis und Prewavelet-Dar-stellung mithilfe eindimensionaler Operatoren für dünne Gitter sowie volle Gitter (feh-lende Pfade rot, alternativer Pfad blau)

29


x

z

y

+ +– + +– + +

+ +– + +

+ +

(a) Dimension z

x

z

y

++

+

++

+

(b) Dimension y

x

z

y

(c) Dimension x

Abbildung 3.3: Ebenenweise Berechnung in allen Dimensionen für dreidimensionaleProbleme. Die Berechnungen der Kombinationsformel sind grau hinterlegt.

Die umgekehrte Umrechnung von Prewavelet-Darstellung in nodale Basis erfolgt

analog. Algorithmus 2 unterscheidet sich dadurch, dass im Fall i = δ einmal von

(n− depth) bis 1 („down“) und ein zweites Mal in umgekehrter Reihenfolge von 0

nach (n− depth− 1) („up“) durchlaufen wird, allerdings kein Gleichungssystem ge-

löst werden muss. Der doppelte Durchlauf ist notwendig, da für jedes Gitter sowohl

die Überschüsse der gröberen als auch der feineren Gitter aufsummiert werden müs-

sen. Prewavelet-Koeffizienten können mit Operator St aus (3.4) in Koeffizienten der

nodalen Basis umgewandelt werden.

30


Algorithmus 1 Umrechnung von nodaler Basis in Prewavelet-Darstellung

1: procedure UMRECHNUNGPREWAVELETS(~Y)2: ~C =~03: t = (t1, . . . , td)4: for δ = d, . . . , 1 do5: REKURSIVPREWAVELETS(~Y, ~C, δ, d, t)6: end for7: end procedure8: procedure REKURSIVPREWAVELETS(~Y, ~C, δ, i, t)9: depth = ∑d−1

i=δ+1 ti10: if i > δ then11: for tδ = 0, . . . , (n− depth) do12: REKURSIVPREWAVELETS(~Y, ~C, δ, i− 1,t)13: end for14: else if i = δ then15: for t1 = (n− depth− 1) , . . . , 1 do16: REKURSIVPREWAVELETS(~Y, ~C, δ, i− 1,t)17: end for18: else if i < δ then19: for t1 = 0, . . . , (n− depth− 1) do20: REKURSIVPREWAVELETS(~Y, ~C, δ, i− 1,t)21: end for22: ti = n− depth23: Ct = ∑

t: k≥δ: tk=tkk<δ: (tk−tk)∈0,1

(−1)|t−t| P tt(Ct)

24: else if i < 0 then25: t = (t1, . . . , tδ + 1, . . . , td)26: Zerlege Yt in Ft und Gt durch Invertierung von (3.7) bzw. (3.8)27: Yt = Ft28: Ct = C t

t (Ct + St (Ft))29: end if30: end procedure

31


Algorithmus 2 Umrechnung von Prewavelet-Darstellung in nodale Basis

1: procedure UMRECHNUNGNODAL(~Y)2: ~C =~03: t = (t1, . . . , td)

4: for δ = 1, . . . , d do5: REKURSIVNODAL(~Y, ~C, δ, d, t, ~)6: end for7: end procedure8: procedure REKURSIVNODAL(~Y, ~C, δ, i, t, dir)9: depth = ∑d−1

i=δ+1 ti

10: if i < 0 then11: t = (t1, . . . , tδ + 1, . . . , td)

12: if dir = up then13: Yt = Yt + P t

t (Yt)14: Yt = Yt + Ct15: else16: Yt = St (Yt)17: Ct = C t

t (St (Yt) + Ct)18: end if19: else if i < δ then20: for t1 = 0, . . . , (n− depth− 1) do21: REKURSIVNODAL(~Y, ~C, δ, i− 1,t, dir)22: end for23: ti = n− depth24: Ct = ∑

t:k≥δ: tk=tkk<δ: (tk−tk)∈0,1

(−1)|t−t| P tt(Ct)

25: else if i = δ then26: . TopDown27: for t1 = (n− depth) , . . . , 1 do28: REKURSIVNODAL(~Y, ~C, δ, i− 1,t,down)29: end for30: . BottumUp31: for t1 = 0, . . . , (n− depth− 1) do32: REKURSIVNODAL(~Y, ~C, δ, i− 1,t,up)33: end for34: else if i > δ then35: for tδ = 0, . . . , (n− depth) do36: REKURSIVNODAL(~Y, ~C, δ, i− 1,t, dir)37: end for38: end if39: end procedure 32


3.4 Algorithmus zur Matrix-Vektor-Multiplikation auf

dünnen Gittern

Der Algorithmus zur Matrix-Vektor-Multiplikation verwendet zur Berechnung volle

Untergitter. Daher werden, zusätzlich zu den Gitterpunkten des feinen Gitters Ξt, alle

Punkte der groben Gitter lokal vorgehalten. Diese werden benötigt, um die Prewave-

let-Koeffizienten in die nodale Basis umzurechnen. Für die Diskretisierung der Steifig-

keits- und Massenmatrix werden nodale Basiselemente verwendet.

Die Aufgabe einer effizienten Implementierung ist es, die lokalen Überschüsse al-

ler Gitter zusammen zu sammeln und an alle anderen Gitter zu verteilen. Für zwei-

dimensionale Probleme kann dies durch den Q-Zyklus in einem einzigen Durchlauf

durch alle Gitter realisiert werden [29]. Dazu werden alle Gitter über einen Pfad durch

geschickte Kombination von Prolongationen und Restriktionen jeweils vorwärts und

rückwärts durchlaufen.

Für hochdimensionale Probleme ist ein einziger Durchlauf nicht möglich. Prolonga-

tionen und Restriktionen werden getrennt voneinander behandelt. Dadurch ergeben

sich für d-dimensionale Probleme 2d Fälle, da für jede Dimension jeweils eine Prolon-

gation und Restriktion durchgeführt werden muss.

Es wird die Multiplikation

~Xn = An~Un (3.10)

der Diskretisierungsmatrix An mit einem Vektor ~Un betrachtet.

Wobei der Vektor ~Un in Dünngitter-Zerlegung vorliegt, sodass für Ut := (ut,i)i∈Ξt∈

Rmt mit mt = |Vt| gilt

~Un := (Ut)|t|<n . (3.11)

Die Elemente at,i,k := ason (ϕt,i, ϕt,k) für i,k ∈ Ξt der Matrix An := (At)|t|<n und

At := (at,i,k)i,k∈Ξtsind durch die Bilinearform aso

n (·, ·) gegeben.

Die Elemente von Ut sind dabei in einem Vektor der Größe mt für das Gitter des

Raumes Vt mit Tiefe t gespeichert.

Für die Zerlegung von u (x) ∈ VDn gilt:

u (x) = ∑|t|<n

∑i∈Ξt

ut,iϕt,i (x) (3.12)

33


3.4.1 Eindimensionale Matrix-Vektor-Multiplikation

Für den eindimensionalen Fall ist

u (x) =n−1

∑t=0

∑i∈Ξt

ut,i ϕt,i (x) (3.13)

auf n Gitter verteilt, wobei jeweils nur die Feingitterkoeffizienten Ξt berücksichtigt

werden.

Die Matrix-Vektor-Multiplikation ~Xn := An~Un für ~Xn := (Xt)t<n sowie Xt =

(xt,i)i∈Ξtverwendet den Bilinearoperator mit Semi-Orthogonalität (2.31):

xt,i = ason

(n−1

∑t=0

∑i∈Ξt

ut,i ϕt,i , ϕt,i

)=

n−1

∑t=0

ason

(∑

i∈Ξt

ut,i ϕt,i , ϕt,i

)(3.14)

Im eindimensionalen Fall gibt es keine überlappenden Gebiete, da sich dazu die

Tiefe in mindestens zwei Dimensionen unterscheiden muss. Der Bilinearoperator mit

Semi-Orthogonalität entspricht daher dem gewöhnlichen Bilinearoperator.

Die Berechnung kann dabei in „TopDown“ und „BottomUp“ aufgeteilt werden:

xt,i =t

∑t=0

ason

(∑

i∈Ξt

ut,i ϕt,i , ϕt,i

)+

n−1

∑t=t+1

ason

(∑

i∈Ξt

ut,i ϕt,i , ϕt,i

)(3.15)

Prewavelets weisen einen erheblich größeren Träger als nodale Basiselemente auf.

Die Diskretisierung der Systemmatrix

At :=(aso

n(vt,i, vt,j

))i,j∈It

(3.16)

erfolgt daher anhand der nodalen Basis für alle Gitterpunkte It des vollen Untergitters.

Die Überführung des Primärraums von Prewavelets in nodale Basis übernimmt

Operator St aus Gleichung (3.4). Der Dualraum wird mit Operator Dt aus Gleichung

(3.5) in Prewavelets überführt.

Über die „TopDown“-Iteration werden die Überschüsse beginnend beim feinsten

Level eingesammelt und auf die gröberen Gitter restringiert. Die „BottomUp“-Iteration

prolongiert ausgehend vom gröbsten Gitter.

Algorithmus 3 speichert die Ergebnisse in zwei Variablen. Der Vektor ~G = (Gt)t<n

34


mit

Gt =n−1

∑t=t+1

Rtt (At (St (ut))) (3.17)

wird für die „TopDown“-Iteration verwendet, Vektor ~H = (Ht)t<n mit

Ht = At

(t

∑t=0

P tt (St (ut))

)(3.18)

für „BottumUp“. Der Restriktionsoperator Rtt verringert schrittweise die Tiefe des

Dualraums. Der Prolongationsoperator P tt erhöht schrittweise die Tiefe des Primär-

raums.

Anschließend werden beide Vektoren addiert und der Dualoperator Dt zur Über-

führung des Dualraums in die Prewaveletbasis angewendet:

Xt = Dt(Rt

t+1Gt+1 + Ht)

(3.19)

Der Anteil der „TopDown“-Iteration wird dazu mit Rtt+1 nach Level t restringiert,

um eine Doppelung für t zu verhindern.

35


Algorithmus 3 Eindimensionale Matrix-Vektor-Multiplikation ~X = A~U

1: procedure MULTIPLIKATION1D(~U)2: . TopDown3: ~G = (G)t≤n4: Gn−1 = An−1 (Sn−1 (Un−1))5: for t′ = (n− 1) , . . . , 1 do6: Gt′−1 = Rt′

t′Gt′ +At′−1 (St′−1 (Ut′−1))7: end for8: . BottomUp9: H0 = S0 (U0)

10: for t′ = 1, . . . , (n− 1) do11: Ht′ = P t′

t′−1Ht′−1 + St′ (Ut′)12: end for13: . Addition G und H14: for t′ = 0, . . . , n do15: if t′ 6= (n− 1) then16: Xt′ = Dt′

(Rt′

t′+1Gt′+1 +At′Ht′)

17: else18: Xt′ = Dt′At′Ht′

19: end if20: end for21: end procedure

3.4.2 Hochdimensionale Rekursion

Algorithmus 3 soll im Folgenden für hochdimensionale Probleme erweitert werden.

Hierzu wird ein rekursiver Aufruf über alle Dimensionen verwendet, sodass die ein-

zelne Rekursion der Vorgehensweise des eindimensionalen Falls entspricht. Der we-

sentliche Ansatz ist dabei die getrennte Behandlung von Restriktionen und Prolon-

gationen. Für mehrdimensionale Probleme kann für jede Dimension entweder eine

Prolongation oder Restriktion durchgeführt werden. Dadurch ergeben sich insgesamt

2d Kombinationen. Jede dieser Kombinationen kann vollständig unabhängig von allen

anderen berechnet werden. Daraus ergeben sich interessante Aspekte für die Paralleli-

sierung.

Grundsätzlich lässt sich der vorgestellte Algorithmus aufgrund seiner Unabhän-

gigkeit der einzelnen Kombinationen sehr gut parallelisieren. Der Aufwand des Da-

tenaustausches der Ergebnisse lässt sich im Vergleich zum Berechnungsaufwand ver-

nachlässigen. Dies ist auf die Verwendung besonders speichersparsamer dünner Gitter

zurückzuführen. Die Parallelisierung wird ausführlich in Kapitel 5 behandelt.

36


In der eindimensionalen Multiplikation wurden die hierarchischen Überschüsse al-

ler Gitter mit geringerer Tiefe prolongiert und anschließend das Ergebnis auf dem fina-

len Gitter mit der Systemmatrix multipliziert (vgl. Gleichung 3.17 und Gleichung 3.18)

Für Restriktionen erfolgte die Multiplikation der Überschüsse mit der Systemmatrix

direkt auf dem Gitter der Herkunft. Die Restriktion erfolgt im Dualraum. Dieses Kon-

zept wird nun auch für höhere Dimensionen übernommen. Dazu ist eine Trennung

von Prolongationen und Restriktionen notwendig. Erst wenn alle Prolongationen ab-

gearbeitet sind, erfolgt die Multiplikation mit der Systemmatrix.

Die Abarbeitung kann daher nicht mehr von 1 bis d erfolgen. In einem Vektor wer-

den die Dimensionen vorsortiert. Prolongationen stehen am Ende und werden durch

die Rekursion zuerst abgearbeitet. Am Übergang zwischen Prolongationen und Re-

striktionen erfolgt die Multiplikation mit der Systemmatrix durch die Anwendung

des OperatorsAt. Nach dem Wechsel in den Dualraum kann abschließend restringiert

werden.

Der zweidimensionale Fall eignet sich hervorragend zur Visualisierung des Algo-

rithmus. Er enthält bereits alle notwendigen Funktionen und Probleme der hochdi-

mensionalen Rekursion.

Die Aufteilung in vier Terme lässt sich folgendermaßen darstellen:

a(u, ϕ(t1,t2),(i1,i2)) = ∑t1>t1

∑t2>t2

a(

w(t1,t2), ϕ(t1,t2),(i1,i2)

)+ ∑

t1>t1

a

(∑

t2≤t2

w(t1,t2), ϕ(t1,t2),(i1,i2)

)

+ ∑t2>t2

a

(∑

t1≤t1

w(t1,t2), ϕ(t1,t2),(i1,i2)

)

+a

(∑

t1≤t1

∑t2≤t2

w(t1,t2), ϕ(t1,t2),(i1,i2)

)(3.20)

Der Überschuss auf einem Level w(t1,t2)bezeichnet dabei die nodale Repräsentation

der Prewavelets, sodass w(t1,t2)(x) = ∑

i∈Ξ(t1,t2)

u(t1,t2),iϕ(t1,t2),i gilt.

Abbildung 3.4 zeigt die Aufteilung in vier Fälle für ein zweidimensionales volles

Gitter und ein dünnes Gitter. Für die Berechnung von Prolongation oder Restriktion

in beiden Dimensionen ist die Reihenfolge der Dimension nicht entscheidend. Für den

gemischten Fall in Abbildung 3.4b erfolgt die Prolongation in x-Richtung. Der Dimen-

sionenvektor hätte daher die Einträge (2, 1). Folglich ist der Dimensionenvektor für

37


Prolongation in y-Richtung in Abbildung 3.4c mit (1, 2) genau umgekehrt sortiert.

Um von Level (0, 3) nach (3, 0) durch Prolongation in x-Richtung und Restriktion

in y-Richtung zu gelangen, wird für volle Gitter der Weg über (3, 3) gewählt. Dazu

wird zunächst eine Restriktion in y-Richtung von t2 = 3 nach t2 = 2 durchgeführt.

Zusätzlich wird je ein rekursiver Ausruf für t1 gestartet. Dieser sammelt durch Pro-

longation alle Überschüsse der tieferen Level für t1 ein und multipliziert sie mit der

Systemmatrix.

Für dünne Gitter existiert der Pfad von (0, 3) nach (3, 0) über (3, 3) nicht. Der Pfad

über (0, 0) entfällt ebenfalls aufgrund der Regel „Prolongation vor Restriktion“. Folg-

lich existiert für dünne Gitter kein Austausch zwischen Level (0, 3) und (3, 0). Mithilfe

der Semi-Orthogonalität kann begründet werden, dass dies keine Auswirkungen auf

die Konvergenz hat.

Fehlende Pfade treten nur bei der Kombination aus Restriktionen und Prolongatio-

nen auf. Dabei wird je mindestens eine Dimension i prolongiert, eine weitere Dimensi-

on k restringiert. Dies induziert überlappende Gebiete, da ti > ti und tk < tk gelten. Die

Vernachlässigung dieser Pfade ist folglich ohne Auswirkungen, da sie im Falle semi-

orthogonaler Bilinearoperatoren zu Null gesetzt werden.

Lemma 3. Durch die Regel „Prolongation vor Restriktion“ auf dünnen Gittern werden Pfade

ausgelassen. Dies hat keine Auswirkungen auf die Konvergenz, da es sich um überlappende

Gebiete handelt.

Beweis. Überlappende Gebiete induzieren einen Wechsel von Prolongation auf Restrik-

tion bei Dimension δ. Restriktionen erfolgen für i ≥ δ, Prolongationen für i < δ. Daraus

folgt ∀i ∈ 1, . . . , δ− 1 dass ti ≤ ti und ∀k ∈ δ− 1, . . . , d dass tk ≥ tk. Sofern nicht

mindestens für eine Dimension restringiert bzw. prolongiert wird, wird der Pfad über

Restriktion bzw. Prolongation in allen Dimensionen abgedeckt. Daher gilt

δ−1

∑i=1

ti <δ−1

∑i=1

ti

d

∑k=δ

tk >d

∑k=δ

tk.

Daraus folgt

∃i ∈ 1, . . . , δ− 1 : tk < tk

∃k ∈ δ− 1, . . . , d : tk > tk.

38


Aus ti < ti und tk > tk folgt Überlappung und Semi-Orthogonalität.

Abbildung 3.5 zeigt die Addition der vier Teilsummen des zweidimensionalen dün-

nen Gitters. Um Doppelungen zu verhindern, werden alle Dimensionen mit Restrik-

tion restringiert. Dieses Konzept lässt sich auf hochdimensionale Räume übertragen.

Gleichung 3.21 besteht aus 2d Teilsummen, die geeignet addiert werden müssen:

a(u, ϕt,i) = ∑R⊂1,2,...,d

∑r∈R

∑tr>tr

a

∑p∈R

∑tp≤tp

wt, ϕt,i

(3.21)

Abschließend wird noch der rekursive Aufruf von Algorithmus 4 am Beispiel der

Prolongation in allen Dimensionen betrachtet. Begonnen wird mit Dimension δ = d.

Die Iteration für τ läuft von Tiefe 0 bis (n− 1) und startet jedes Mal einen rekursi-

ven Aufruf für δ− 1 (siehe Abbildung 3.6). Das Ergebnis des rekursiven Aufrufs wird

anschließend für tδ von τ nach τ + 1 prolongiert. Dort wird erneut das Ergebnis des

rekursiven Aufrufs addiert.

Die Berechnung des rekursiven Aufrufs δ − 1 entspricht dem ebenenweisen Ein-

sammeln durch Prolongation. Die Einträge des Tiefenvektors t sind ab δ fixiert. Der

rekursive Aufruf iteriert für alle Dimensionen kleiner δ über alle Gitter des dünnen

Gitters, sodass

δ−1

∑i=1

ti +d

∑i=δ

ti < n. (3.22)

Im Falle der Restriktion erfolgt die Iteration in umgekehrter Richtung. Für jede Di-

mension kann über DIRECTION(δ) ermittelt werden, ob prolongiert oder restringiert

wird. Falls DIRECTION(δ + 1) 6=DIRECTION(δ), muss mit der Systemmatrix multi-

pliziert werden.

39


t2

t10 1 2 3

0

1

2

3

(a) Prolongation-Prolongation

t2

t10 1 2 3

0

1

2

3

(b) Prolongation-Restriktion

t2

t10 1 2 3

0

1

2

3

(c) Restriktion-Prolongation

t2

t10 1 2 3

0

1

2

3

(d) Restriktion-Restriktion

Abbildung 3.4: Alle möglichen Kombinationen aus Restriktionen und Prolongationenfür die zweidimensionale Matrix-Vektor-Multiplikation auf vollen Gittern bzw. dün-nen Gittern. Alle Untergitter des vollen Gitters mit n = 4 sind grau hinterlegt. Im Falleeines dünnen Gitters entfallen daher die Wege über die gestrichelten Pfeile.

40


0 1 2 3

0

1

2

3

t2

t1

Abbildung 3.5: Addition aller möglichen Kombinationen aus Restriktionen und Pro-longationen für die zweidimensionale Matrix-Vektor-Multiplikation. Damit kein Ein-trag mehrfach vorkommt, wird im Falle der Restriktion das nächstgrößere Nachbar-element restringiert. Der rot hinterlegte Bereich zeigt die Unterteilung in die vier mög-lichen Fälle der Addition für das Element (1, 1). Im Falle eines dünnen Gitters entfälltdaher das Diagonalelement (2, 2), welches in x- und y-Richtung restringiert werdenmüsste.

t1 variabler Teil tδ tδ+1tδ+2fixierter Teil td

rekursiverAufruf

τ = 0, . . . , mm := n−∑d

i=δ+2 ti

t1 variabler Teil tδ−1 tδ tδ+1 fixierter Teil td

rekursiverAufruf

τ = 0, . . . , mm := n−∑d

i=δ+1 ti

t1 variabler Teil tδ−2tδ−1 tδ fixierter Teil td

Abbildung 3.6: Rekursiver Aufruf der Methode rekursiveMultiplikation fürden Vektor t. Die Einträge ti für i > δ sind fixiert. tδ wird bis zur maximalen Tiefeiteriert. Der variable Teil i < δ wird durch den rekursiven Aufruf ermittelt [20].

41


Algorithmus 4 Rekursive Matrix-Vektor-Multiplikation Berechnung ~Y ← A~Y

1: procedure REKURSIVEMULTIPLIKATION(~Y, δ, t)2: depth = ∑d−1

i=δ+1 ti3: if DIRECTION(δ) == ’Pro’ then4: tδ = 05: if δ > 0 then6: REKURSIVEMULTIPLIKATION(~Y, δ− 1,t)7: end if8: for all t1, . . . , tδ−1 mit |t|δ−1 < n− depth do9: Yt = St (Yt)

10: end for11: t = t12: for tδ = 1, . . . , (n− depth− 1) do13: tδ = i14: if δ > 0 then15: REKURSIVEMULTIPLIKATION(~Y, δ− 1,t)16: end if17: tδ = i− 118: for all t1, . . . , tδ−1 mit |t|δ−1 < n− depth do19: Yt = St (Yt) + P t

t (Yt)20: end for21: end for22: if δ == d oder DIRECTION(δ + 1) != DIRECTION(δ) then23: for all t1, . . . , tδ−1 mit |t|δ−1 < n− depth do24: Yt = At

(Y~t)

25: end for26: end if27: else if DIRECTION(δ) == ’Res’ then28: tδ = n− depth− 1;29: Yt = At (St (Yt))30: for i = (n− depth− 2) , . . . , 0 do31: t0 = i32: if δ > 0 then33: REKURSIVEMULTIPLIKATION(~Y, δ− 1,t)34: end if35: t0 = i + 136: for all t1, . . . , tδ−1 mit |t|δ−1 < n− depth do37: Yt = At (St (Yt)) +Rt

t (Yt)38: end for39: end for40: end if41: end procedure

42


3.4.3 Multiplikation für inhomogene Randbedingungen

mit Korrektur

In Abschnitt 2.2 wurden bereits geeignete Randelemente vorgestellt. Dafür wurden

in Abbildung 2.7 nodale Basisfunktionen an den Randpunkten mit Neumann-Prewa-

velets addiert. Würden die gewonnenen Randelemente bereits kombiniert auf dem

entsprechenden Gitter verwendet werden, wäre keine Semi-Orthogonalität mehr ge-

geben. Entsprechend entsteht durch Verwendung von Algorithmus 4 ein zusätzlicher

Fehler, und der Konvergenzbeweis in [31] ist nicht mehr gültig.

Befindet sich ein Punkt i mit Tiefe t in Dimension δ am Rand, hat iδ entweder den

Wert 1 oder 2tδ − 1 und wird mit den nodalen Elementen auf Vt mit Index 0 bzw. 2tδ

korrigiert.

Zur Randkorrektur wird die Eigenschaft Vtδ= Wtδ

⊕Vtδ−1 genutzt. Damit lässt sich

Vtδaus Wtδ

und Vtδ−1 bestimmen. Da nur V1 explizit gegeben ist, iteriert t von 0 bis zur

maximalen Tiefe (n− 1).

Selbstverständlich kann ein Punkt auch in mehreren Dimensionen gleichzeitig ein

Randpunkt sein. In diesem Fall kann der Operator ähnlich der Prolongation und

Restriktion wieder auf eine Verkettung eindimensionaler Operationen zurückgeführt

werden. Abbildung 3.7 zeigt die Korrektur zunächst in x-Richtung (Abbildung 3.7a)

sowie in y-Richtung (Abbildung 3.7b).

Für die Korrektur muss a (u, vt,i) aus a (u, ϕt,i) und a (u, vt−1,i) rekonstruiert werden.

Da a (u, ϕt,i) und a (u, vt−1,i) aus der Multiplikation mit WTNeumann berechnet wird, kann

t2

t1

(a) Korrektur Dimension x

t2

t1

(b) Korrektur Dimension y

Abbildung 3.7: Korrekturverfahren für inhomogene Randbedingungen

43


a (u, vt,i) über eine LU-Zerlegung von WTNeumann berechnet werden:

WTNeumann =

1 12

−1210

1110 −

35

110

12 1 1

21

10 −35 1 −3

51

1012 1 1

2. . . . . . . . . . . . . . .

110 −3

5 1 −35

110

12 1 1

2110 −3

51110 −

1210

12 1

(3.23)

Der Dualraum wurde folglich von der Prewavelet-Basis mit Neumann-Randbedin-

gungen in die nodale Basis überführt. Abschließend kann er mit Operator Dt aus Glei-

chung (3.5) in die Prewavelet-Basis mit Dirichlet-Randbedingungen überführt werden.

Dadurch wird Homogenität gewährleistet.

44


3.5 Implementierung

Ziel bei der Implementierung war eine effiziente, flexible und benutzerfreundliche Bi-

bliothek zur Berechnung der Finite-Elemente-Diskretisierungen auf dünnen Gittern

mit Prewavelets. Durch den Einsatz der Programmiersprache C++ und die Verwen-

dung von Templates konnte eine Unabhängigkeit von der Dimension erreicht werden.

Rekursive Algorithmen und Template-basierte Datenstrukturen legen die Dimension

erst zum Zeitpunkt der Übersetzung fest.

Parallelisierung und Rechenleistung standen nicht im Fokus. Das wichtigste Krite-

rium war ein modularer und gekapselter Aufbau.

Expression Templates gewährleisten eine weitestgehend mathematische Schreib-

weise und werden für die vorgestellten Algorithmen verwendet [17, 18]. Listing 3.1

zeigt beispielhaft das CG-Verfahren ohne Vorkonditionierung. multiply ruft den

Algorithmus zur Matrix-Vektor-Multiplikation auf. Leider konnte hier aufgrund der

Komplexität keine Operator-Überladung verwendet werden. Einfachere Ausdrücke

wie Addition oder skalare Multiplikation können dagegen als Kombination verschie-

dener Operatoren verfasst werden.

Listing 3.1: CG-Verfahren

1 multiply(A_matrix,u_vector,r_vector);

2

3 r_vector = rhs_vector - r_vector;

4 d_vector = r_vector;

5

6 for(int i = 0; i < max_iterations; ++i)

7 multiply(A_matrix,d_vector,z_vector);

8 const double res_product = product(r_vector,r_vector);

9 if(sqrt(res_product/sparse_grid.getGridPoints()) < 1e-14)

10 return;

11 const double alpha = res_product/product(d_vector,z_vector);

12

13 u_vector = u_vector + alpha*d_vector;

14 r_vector = r_vector - alpha*z_vector;

15 const double beta = product(r_vector,r_vector)/res_product;

16 d_vector = r_vector + beta*d_vector;

17

45


Alle verwendeten Vektoren sind in diesem Beispiel Variablen auf dünnen Gittern

und bestehen wiederum aus Variablen auf regulären vollen Gittern. Ein dünnes Git-

ter SparseGrid besteht stets aus vollen Untergittern Grid mit Tiefe |t| < n. Dies

spiegelt sich auch in der Klassenstruktur wider (siehe Abbildung 3.8). Für ein dünnes

Gitter können beliebig viele Objekte SparseVariable angelegt werden, die für je-

den Gitterpunkt einen Datenwert speichern. Folglich besteht SparseVariable aus je

einem Objekt Variable für jedes Grid-Objekt des entsprechenden SparseGrid.

Grid SparseGridgrid_vector

1..n

Variable SparseVariablevariable_vector

1..*

1

0..*

1

0..*

Abbildung 3.8: SparseVariable verwaltet Variable

Matrizen werden als 3d-Punkte-Stern abgespeichert (siehe Abbildung 3.9). Die Klas-

se SparseStencil kann dabei sowohl konstante Koeffizienten (ConstantStencil)

als auch variable Koeffizienten (VariableStencil) verwalten. Während bei kon-

stanten Koeffizienten nur ein einziger Stern pro Gitter vorgehalten werden muss, wird

für variable Koeffizienten punktweise ein Array mit 3d Einträgen berechnet und abge-

speichert.

Durch den Einsatz von Schnittstellen wird die Implementierung der dünnen Git-

ter von den Algorithmen entkoppelt. Neben Datenstrukturen für dünne Gitter gibt es

Realisierungen der Schnittstellen für adaptive dünne Gitter und reguläre Mehrgitter-

systeme. Diese lassen sich auf algorithmischer Ebene leicht austauschen. Listing 3.1

konnte daher ohne Änderung für semi-adaptive Gitter verwendet werden. Details zur

Semi-Adaptivität befinden sich in Abschnitt 6.1.

• SparseAddition operator+: Addition zweier Dünngitteroperatoren

• SparseDifference operator-: Differenz zweier Dünngitteroperatoren

• SparseAbs abs: Absolutwert eines Dünngitteroperators

• SparseScalarMultiplication operator*: Multiplikation eines Dünngitteropera-

tors mit einem Skalar

46



1..n

<<interface>>Stencil

ConstStencil VariableStencil

SparseStencilstencil_vector

1..*

1

0..*

1

0..*

Abbildung 3.9: Für die abstrakte Klasse Stencil gibt es entwederConstantStencil für konstante Koeffizienten, oder es wird für jede Koordinate aufGrid ein 3d-Punkte-Stern abgelegt.

• SparseStencilMultiplication operator*: Multiplikation eines Dünngitter-Sten-

cil-Objekts mit einem Dünngitteroperator

Auf algorithmischer Ebene werden hauptsächlich die elementaren Rechenopera-

tionen Addition und skalare Multiplikation auf dünnen Gittern verwendet. Abbil-

dung 3.10 vergleicht die Operatoren für SparseVariable und Variable.

Die Matrix-Vektor-Multiplikation erfordert zusätzlich die Operatoren aus Ab-

schnitt 3.1. Für einige Operatoren gibt es Varianten in einer Dimension sowie in meh-

reren Dimensionen gleichzeitig. Die folgende Liste gibt einen kurzen Überblick über

alle Operatoren.

• Addition operator+(): Addition zweier Operatoren

• Substraction operator-(): Subtraktion zweier Operatoren

• Abs abs(): Absolutwert eines Operators

• ScalarMultiplication operator*(): Multiplikation eines Operators mit einem

Skalar

• Diag diag(): Extrahiert die Diagonaleinträge eines Stencil-Objekts. Das Ergeb-

nis ist wiederum ein Operator und kann anschließend beispielsweise zu einer

Variablen addiert werden.

47


• Multiplication operator*(): Multiplikation eines Stencil-Objekts mit einem

Operator. Somit eine Matrix-Vektor-Multiplikation auf Grid-Ebene.

• Division operator/(): Punktweise Division zweier Operatoren. Die punktwei-

se Division durch die Diagonaleinträge eines Stencil-Objekts ermöglicht Jaco-

bi-Vorkonditionierung.

• Restriction restriction(): Restriktion eines Operators in einer Dimension i

(Rtt mit ti = ti − 1). Operation auf dem Dualraum entsprechend (3.2)

• MultiRestriction (restriction(): Restriktion eines Operators in beliebigen Di-

mensionen anhand eines Booleschen Vektors mit Einträgen für jede Dimension.

• Coarsening coarsening(): Extraktion des Grobgitteranteils in einer Dimension

i. Operator C tt mit ti = ti − 1 auf dem Primärraum entsprechend (3.3)

• MultiCoarsening coarsening(): Extraktion des Grobgitteranteils in beliebigen

Dimensionen anhand eines Booleschen Vektors mit Einträgen für jede Dimensi-

on.

• Prolongation prolongation(): Lineare Interpolation in einer Dimension i. Ope-

rator P tt mit ti = ti + 1 auf dem Primärraum entsprechend (3.1)

• MultiProlongation prolongation(): Lineare Interpolation in beliebigen Di-

mensionen anhand eines Booleschen Vektors prolongation mit Einträgen für

jede Dimension.

• SurplusPrimal surplusPrimal(): Umrechnung des Überschusses im Primär-

raum von nodaler Basis in Prewavelet-Darstellung für eine Dimension. Operator

St auf dem Primärraum entsprechend (3.4)

• SurplusDual surplusDual(): Umrechnung des Überschusses des Dualraums

von Prewavelet-Darstellung in nodale Basis in einer Dimension. Operator Dt auf

dem Dualraum entsprechend (3.5)

• CoarsePrimal coarsePrimal(): Extraktion des Grobgitteranteils einer Prewa-

velet-Zerlegung in einer Dimension.

• CoarseDual coarseDual(): Transfer des Dualraums in Basisfunktionen des

Grobgitters in einer Dimension.

48


Diskretisierungssterne für konstante Koeffizienten bzw. variable Koeffizienten in

Tensorprodukt-Form lassen sich sehr effektiv rekursiv berechnen. Für kompliziertere

Terme muss auf die numerische Integration zurückgegriffen werden. Die numerische

Integration muss dabei die Struktur des dünnen Gitters als Abbruchkriterium berück-

sichtigen. Der variable Koeffizient wird dazu nur auf Gitterpunkten des dünnen Git-

ters ausgewertet. Für Gitter mit maximaler Tiefe |t| = n− 1 bedeutet dies, dass jeweils

nur die 2d Randpunkte des Hyperquaders berücksichtigt werden. Für |t| < n− 1 müs-

sen alle Punkte des dünnen Gitters, die sich innerhalb des Hyperquaders befinden, in

die Interpolation einbezogen werden.

Die numerische Integration des Bilinearoperators wurde im Rahmen einer Bachelor-

arbeit am Lehrstuhl für Systemsimulation untersucht [34]. Dieser Integrator kennt die

Tiefe des zu integrierenden Elements und verwendet es als Abbruchkriterium für die

rekursive Auswertung. Wegen des zuvor beschriebenen Konzepts und der Zerlegung

des dünnen Gitters in volle Untergitter ist ein Zugriff auf andere Gitter des dünnen

Gitters für den Integrator nicht möglich. Daher wird der variable Koeffizient aktuell

noch durch die Auswertung eines Funktionszeigers ermittelt. Eine Pufferung dieses

Wertes ist nur auf dem aktuellen Gitter möglich und stellt einen Nachteil der aktuellen

Implementierung dar.

Die jetzige Implementierung liefert für dreidimensionale Probleme mit großen Tie-

fen zuverlässige Ergebnisse und verlängert die Rechenzeit kaum. Sechsdimensionale

Probleme sind aufgrund der rasant wachsenden Anzahl an Einträgen der Diskretisie-

rungssterne mit 3d Einträgen pro Gitterpunkt jedoch noch nicht möglich. Hierfür muss

auf die analytische Integration zurückgegriffen werden. Dies beschränkt den Einsatz

von variablen Koeffizienten auf Tensorprodukte für n > 3. Numerische Ergebnisse

hierzu folgen in Abschnitt 4.2.

Eine wesentlich effektivere Variante wäre sicherlich eine hierarchische Abspeiche-

rung des variablen Koeffizienten. Für die Integration ist folglich ein ähnliches Ver-

teilungsverfahren wie für die Matrix-Vektor-Multiplikation notwendig. Allerdings

kommt es auch hier wieder zu fehlenden Pfaden bei überlappenden Elementen. Die

Berechnung der Einträge der Diskretisierungsmatrix erfolgt für lineare finite Elemente,

da diese einen kleineren Träger als Prewavelets besitzen. Durch deren fehlende Ortho-

gonalität können die Einträge überlappender Funktionen nicht vernachlässigt werden.

Im Falle der Matrix-Vektor-Multiplikation erfolgte die Prolongation im Primärraum

sowie für Restriktionen im Dualraum. Da Restriktionen für die Auswertung des Bili-

nearoperators im Primär- und Dualraum notwendig sind, sind vorgelagerte Prolonga-

49


tionen nicht möglich. Überschüsse feinerer Gitter müssen daher anderweitig beschafft

werden.

Sinnvoll wäre dazu, den variablen Koeffizienten in einer separaten Datenstruktur

abzuspeichern. Ein effizienter Zugriff über einen eindeutigen Index jedes Punktes ist

über eine Hash-Tabelle möglich. Somit könnten die Diskretisierungssterne für die je-

weils feinsten Gitter berechnet werden und durch Restriktion vergröbert werden. Da

die Berechnung durch Integration aber weiterhin aufwendiger als die Verwendung

von Tensorprodukten ist, ist die Kombination beider Verfahren sinnvoll. Mehrere Dis-

kretisierungssterne können dazu addiert und mit einem Skalar multipliziert werden

(vgl. Abbildung 3.11). Für die Helmholtz-Gleichung könnte der Poisson-Operator ana-

lytisch berechnet werden. Er wird anschließend auf den numerisch integrierten varia-

blen Koeffizienten addiert.

50



1..n

<<interface>>Operator

<<interface>>SparseOperator

Variable

Addition

Substraction

Abs

ScalarMultiplication

Diag

Multiplication

Division

Restriction

MultiRestriction

Coarsening

MultiCoarsening

Prolongation

MultiProlongation

SurplusPrimal

SurplusDual

CoarsePrimal

CoarseDual

SparseVariable

SparseAddition

SparseDifference

SparseAbs

SparseScalarMultiplication

SparseStencilMultiplication

Abbildung 3.10: Für die Klasse Variable steht eine Vielzahl an Operatoren für ma-thematische Ausdrücke zur Verfügung. Mit SparseVariable können ebenfalls Be-rechnungen durchgeführt werden.

51



1..n

<<interface>>StencilOperator

<<interface>>SparseStencilOperator

Stencil

StencilAddition

StencilScalarMultiplication

SparseStencil

SparseStencilAddition

SparseStencilScalarMultiplication

Abbildung 3.11: Verschiedene Stencil- und SparseStencil-Klassen können ad-diert werden.

3.6 Komplexitätsanalyse und Kostendiskussion

In diesem Abschnitt soll die Laufzeit von Algorithmus 4 zur Matrix-Vektor-Multipli-

kation betrachtet werden. Die Kombination von Prewavelets und Jacobi-Vorkonditio-

nierung ergibt eine Konditionszahl κ = O (1) für hochdimensionale Probleme [21].

Dadurch ergibt sich für die Anzahl der Iterationen der Methode der konjugierenden

Gradienten eine Iterationszahl O (1) und unter der Voraussetzung linearer Laufzeit

der Matrix-Vektor-Multiplikation eine lineare Skalierung mit der Anzahl der Gitter-

punkte des dünnen Gitters.

Zur Berechnung der Matrix-Vektor-Multiplikation werden volle Untergitter Vt mit

Tiefe |t| < n verwendet. Deren Speicheraufwand ist größer als bei der ausschließlichen

Speicherung der Überschüsse.

Lemma 4. Die Summe der Gitterpunkte aller vollen Untergitter Ndn für ein d-dimensionales

Dünngitter mit Tiefe n, skaliert mit O(2n nd−1).

52


Beweis. Der Beweis erfolgt mithilfe der vollständigen Induktion. Für d = 1 gilt

N1n =

n−1

∑t=0

(2i+1 − 1

)= O

(2n+1

).

Hochdimensionale dünne Gitter mit Tiefenvektor t = (t1, . . . , td) werden als Tensor-

produkt konstruiert. Dessen Basis ist das (d− 1)-dimensionale dünne Gitter der Tiefe

(n− td) mit jeweils 2td+1 Gitterpunkten.

Ndn = ∑

td<n2td+1Nd−1

n−td= ∑

td<n2td+1O

(2n−td nd−2

)= nO

(2n nd−2

)= O

(2n nd−1

)

Als Nächstes wird der Rechenaufwand für die rekursive Matrix-Vektor-Multiplika-

tion betrachtet.

Lemma 5. Die Laufzeit der Matrix-Vektor-Multiplikation skaliert linear mit der Anzahl der

Gitterpunkte des dünnen Gitters und ist daher O(2n nd−1).

Beweis. Auch hier wird wieder der Beweis durch Induktion angewendet. Dafür müs-

sen drei Fälle unterschieden werden:

1. Prolongation

2. Restriktion, wobei im rekursiven Aufruf eine Restriktion folgt.

3. Restriktion, wobei im rekursiven Aufruf eine Prolongation folgt. Daher erfolgt

zusätzlich eine Matrix-Vektor-Multiplikation

Für d = 1 erfolgt kein rekursiver Funktionsaufruf. In Algorithmus 4 entspricht dies

δ = 0. Der Beweis reduziert sich auf Prolongation und Restriktion, da kein rekursiver

Aufruf erfolgt. Für die Prolongation wird auf jedem Gitterpunkt des feinen Gitters eine

Rechenoperation durchgeführt:

n−1

∑i=1

(2i+1 − 1

)= O

(2n+1

)Für die Restriktion wird jeweils eine Rechenoperation für jeden Gitterpunkt des

groben Gitters benötigt. Zusätzlich werden alle Gitterpunkte mit dem 3d-Punkte-Stern

53


multipliziert:

n−2

∑i=0

(2i+1 − 1

)+

n−1

∑i=0

(3d 2i+1 − 1

)= O

(2n+1

)Für d ≥ 1 wird zusätzlich der rekursive Aufruf berücksichtigt.

Fall 1 setzt sich aus der Prolongation und dem rekursiven Aufruf zu

n−1

∑i=1

(2i+1 + 1

)O(

2n−i (n− i)d−2)+

n−1

∑i=0

(2i+1 + 1

)O(

2n−i (n− i)d−2)= O

(2nnd−1

)zusammen. Der rekursive Aufruf löst für jeden der 2i+1 Gitterpunkte ein (d− 1)-

dimensionales Problem mit Tiefe n− i.

Für Fall 2 wird ein rekursiver Aufruf sowie eine Restriktion und Matrix-Vektor-

Multiplikation für das aktuelle Vollgitter benötigt:

n−1

∑i=1

(2i+1 + 1

)O(

2n−i (n− i)d−2)+

n−1

∑i=0

(2i+1 + 1

)O(

2n−i (n− i)d−2)+

n−2

∑i=0

3d(

2i+1 − 1)O(

2n−i (n− i)d−2)= O

(2nnd−1

)Für den Wechsel von Prolongation auf Restriktion (Fall 3) wird zusätzlich eine

Matrix-Vektor-Multiplikation der Prolongationen des rekursiven Aufrufs mit dem 3d-

Punkte-Stern durchgeführt:

n−1

∑i=1

(2i+1 + 1

)O(

2n−i (n− i)d−2)+

n−1

∑i=0

(2i+1 + 1

)O(

2n−i (n− i)d−2)

n−2

∑i=0

3d(

2i+1 − 1)O(

2n−i (n− i)d−2)= O

(2nnd−1

)

54

Kapitel 4

Hochdimensionale partielle

Differentialgleichungen auf dünnen

Gittern

In Kapitel 3 wurde ein effizientes Verfahren zur Berechnung der Matrix-Vektor-

Multiplikation für die Prewavelet-Diskretisierung vorgestellt. Dieses kann direkt in

der Methode der konjugierenden Gradienten (siehe Algorithmus 3.1) verwendet wer-

den. Außerdem wurden Algorithmen zur Umrechnung von der Prewavelet-Basis in

die nodale Basis und umgekehrt präsentiert.

Diese werden im Folgenden aufgegriffen und mit numerischen Beispielen getestet.

Zunächst werden dreidimensionale Helmholtz-Probleme mit einem konstanten und

variablen Helmholtz-Term verwendet.

Anschließend werden Gebiete mit gebogenen Kanten eingeführt. Daraus ergeben

sich variable Koeffizienten in den Ableitungen, und eine Darstellung als Tensorpro-

dukt ist nicht mehr möglich. Zur Berechnung der Koeffizienten der Steifigkeits- und

Massenmatrix wird auf numerische Integration zurückgegriffen. Aufgrund des hohen

Aufwands ist eine effektive Berechnung für höhere Dimensionen mit der aktuellen

Implementierung noch nicht möglich. Dazu sind noch weitere Anpassungen des Ab-

bruchkriteriums notwendig. Daher sind sechsdimensionale Probleme für die Berech-

nung der Diskretisierungssterne auf variable Koeffizienten als Tensorprodukt ange-

wiesen.

Alle vorgestellten Algorithmen arbeiten unabhängig von der Diskretisierung und

greifen auf 3d-Punkte-Diskretisierungssterne linearer finiter Elemente zurück.

55

KAPITEL 4. HOCHDIMENSIONALE PARTIELLE DIFFERENTIALGLEICHUNGENAUF DÜNNEN GITTERN

4.1 Prewavelet-vorkonditionierte Methode der konju-

gierenden Gradienten

Die Anzahl der Iterationen der Methode der konjugierenden Gradienten kann mit-

hilfe einer Vorkonditionierung erheblich verbessert werden. Die Verwendung von

Prewavelets in Kombination mit einem Jacobi-Vorkonditionierer ist sehr gut für

projektionsbasierte Methoden im Krylow-Raum geeignet [38]. Tabelle 4.1 vergleicht

die Konditionszahl κ (A) der Systemmatrix A für ein dreidimensionales Helmholtz-

Problem mit Prewavelet-Diskretisierung sowie zusätzlicher Jacobi-Vorkonditionie-

rung mit CT AC [15]. Anstelle der Diagonaleinträge ist die Verwendung des Faktors

2−1 als Vorkonditionierung ausreichend [38]. Die Berechnung von κ erfolgte mithil-

fe der Potenzmethode. Listing 4.1 zeigt die Implementierung der vorkonditionierten

Methode der konjugierenden Gradienten mit 2−|t|. Dadurch kann sowohl für konstan-

te als auch variable Koeffizienten die Ordnung O (1) für die Konditionszahl erreicht

werden.

Listing 4.1: vorkonditioniertes CG-Verfahren

1 multiply(A_matrix,u_vector,r_vector);

2 r_vector = rhs_vector - r_vector;

3 h_vector = r_vector;

4 precondition(h_vector,0.5);

5 d_vector = h_vector;

6

7 for(int i = 0; i < max_iterations; ++i)

8 const double res_product = product(r_vector,h_vector);

9 if(sqrt(res_product) < 1e-14)

10 return;

11

12 multiply(A_matrix,d_vector,z_vector);

13 const double alpha = res_product/

14 product(d_vector,z_vector);

15 u_vector = u_vector + alpha*d_vector;

16 r_vector = r_vector - alpha*z_vector;

17 h_vector = r_vector;

18 precondition(h_vector,0.5);

19

56


20 const double beta = product(r_vector,h_vector)

21 /res_product;

22 d_vector = h_vector + beta*d_vector;

23

n DOF κ (A) κ(CT AC

)2 7 7.70 1.633 31 33.07 2.594 111 156.75 2.856 1023 454.82 3.147 2815 673.84 3.428 7423 836.71 3.619 18943 880.15 3.79

Tabelle 4.1: Konditionszahl κ (A) der Prewavelet-Diskretisierung für d = 3 mit varia-blen Koeffizienten und Jacobi-Vorkonditionierung κ

(CT AC

)Die Effizienz der Vorkonditionierung soll am Beispiel der Helmholtz-Gleichung mit

konstantem Helmholtz-Koeffizienten

−∆u + λu = f in Ω ⊂ R3 (4.1)

u = g on ∂Ω.

gezeigt werden.

Das Residuum in Abbildung 4.1 sinkt für große Tiefen n > 6 nur sehr langsam.

Die Methode der konjugierenden Gradienten verwendet als Abbruchkriterium die

gewichtete diskrete L2-Norm. Dies führt ohne Vorkonditionierung zu relativ großen

Iterationszahlen. Die Verwendung der Maximumsnorm zeigt ein ähnliches Verhalten

(ebenfalls Abbildung 4.1).

Abbildung 4.2 zeigt die Abweichung e der numerischen Lösung uDn von der exak-

ten Lösung u (x, y, z) = sin (π x) sin (π y) sin (π z) in der diskreten L2-Norm

en,∞ = ‖u− uDn‖∞ (4.2)

sowie der Maximumsnorm

en,2 = ‖u− uDn‖2. (4.3)

Ohne Vorkonditionierung wird der Diskretisierungsfehler auch nach vielen Itera-

57


10-10

10-08

10-06

10-04

10-02

10+00

0 5 10 15 20 25 30

Iterationen

L∞

-Norm

n = 2

n = 3

n = 4

n = 5

n = 6

n = 7

n = 8

n = 9

n = 10

10-10

10-08

10-06

10-04

10-02

10+00

0 5 10 15 20 25 30

Iterationen

L∞

-Norm mit Jacobi-Vorkonditionierung

10-05

10-04

10-03

10-02

10-01

10+00

0 5 10 15 20 25 30

Iterationen

L2-Norm

n = 2

n = 3

n = 4

n = 5

n = 6

n = 7

n = 8

n = 9

n = 10

10-05

10-04

10-03

10-02

10-01

10+00

0 5 10 15 20 25 30

Iterationen

L2-Norm mit Jacobi-Vorkonditionierung

Abbildung 4.1: Konvergenz des Residuums für L∞-Norm (oben) und L2-Norm (unten)jeweils ohne (links) und mit (rechts) Vorkonditionierung.

tionen nicht erreicht (Abbildung 4.2 linke Hälfte), wogegen mit Vorkonditionierung

selbst für Tiefe n = 10 und 47103 bereits nach 20 Iterationen der Diskretisierungsfehler

erreicht wird. In Tabelle 4.2 ist der Diskretisierungsfehler für beide Normen aufgeführt.

Für die Konvergenz des Interpolationsfehlers gilt [3]

‖u− uDn‖∞ = O(

h2 log2 (h)d−1)

(4.4)

‖u− uDn‖2 = O(

h2 log2 (h)d−1)

(4.5)

sowie für die H1-Norm [31]

‖u− uDn‖H1 ≤ ‖u‖M2(Ω)

(h log2 (h)

d−1)

. (4.6)

Daher ergibt sich mit n = 10 und d = 3 ein theoretischer Konvergenzfaktor füren−1,2

en,2=

en−1,∞en,∞

= 4(

n−1n

)d−1von 3.16 sowie 1.58 für

en−1,H1

en,H1= 2

(n−1

n

)d−1. Alle in

58


10-05

10-04

10-03

10-02

10-01

10+00

0 5 10 15 20 25 30

Iterationen

L∞

-Norm

n = 2

n = 3

n = 4

n = 5

n = 6

n = 7

n = 8

n = 9

n = 10

10-05

10-04

10-03

10-02

10-01

10+00

0 5 10 15 20 25 30

Iterationen

L∞

-Norm mit Jacobi-Vorkonditionierung

10-06

10-05

10-04

10-03

10-02

10-01

10+00

0 5 10 15 20 25 30

Iterationen

L2-Norm

n = 2

n = 3

n = 4

n = 5

n = 6

n = 7

n = 8

n = 9

n = 10

10-06

10-05

10-04

10-03

10-02

10-01

10+00

0 5 10 15 20 25 30

Iterationen

L2-Norm mit Jacobi-Vorkonditionierung

Abbildung 4.2: Konvergenz des Fehlers für L∞-Norm (oben) und L2-Norm (unten)jeweils ohne (links) und mit (rechts) Vorkonditionierung.

Tabelle 4.2 gemessenen Werte übertreffen diese Abschätzung und erreichen für große

Tiefen nahezu den Konvergenzfaktor voller Gitter.

59


n DOF en,∞en−1,∞

en,∞en,2

en−1,2en,2

en,H1en−1,H1

en,H1

2 7 1.41× 10−1 7.58× 10−3 1.36× 10−1

3 31 7.84× 10−2 1.80 6.66× 10−3 2.63 1.07× 10−1 1.274 111 3.08× 10−2 2.54 2.33× 10−3 2.86 6.81× 10−2 1.575 351 1.04× 10−2 2.96 7.78× 10−4 3.00 3.81× 10−2 1.796 1023 3.27× 10−3 3.19 2.50× 10−4 3.12 2.00× 10−2 1.907 2815 9.83× 10−4 3.33 7.75× 10−5 3.22 1.02× 10−2 1.968 7423 2.98× 10−4 3.29 2.35× 10−5 3.30 5.16× 10−3 1.989 18943 8.87× 10−5 3.37 6.95× 10−6 3.37 2.59× 10−3 1.99

10 47103 2.62× 10−5 3.38 2.02× 10−6 3.43 1.29× 10−3 2.00

Tabelle 4.2: Diskretisierungsfehler für konstante Koeffizienten

60


4.2 Variable Koeffizienten für krummlinig umrandete

Gebiete

Als nächstes sollen Helmholtz-Probleme mit variablem Helmholtz-Koeffizienten

λ (x, y, z) für d = 3 untersucht werden. Die exakte Lösung u wird wie zuvor für kon-

stante Koeffizienten gewählt. Die rechte Seite f ergibt sich entsprechend aus der Wahl

des variablen Koeffizienten:

−∆u + λu = f in Ω ⊂ R3 (4.7)

u = g auf ∂Ω.

Der variable Koeffizient

λ (x, y, z) =1

1 + x2 + y2 + z2 (4.8)

wird dabei so gewählt, dass keine Zerlegung in Faktoren mit separierten Variablen

(Tensorprodukt) mehr möglich ist.

Während für konstante Koeffizienten sowie für die meisten Tensorprodukt-

Zerlegungen eine exakte Integration möglich ist, muss für Gleichung 4.8 auf nume-

rische Integration ∫Ω

a(vt,i, vt′,j

)dx

des Bilinearoperators a(vt,i, vt′,j

):= ∇u · ∇v + λu v zur Berechnung der Steifigkeits-

matrix zurückgegriffen werden.

Hierzu wurde im Rahmen einer Bachelorarbeit [34] eine Software entwickelt. Mit

dieser können finite Elemente auf einem dünnen Gitter integriert werden. Entschei-

dend ist dabei, dass der variable Koeffizient nur an den Stützstellen des dünnen Git-

ters ausgewertet wird. Hierzu muss bei der Integration die aktuelle Tiefe sowie die

maximale Tiefe n berücksichtigt werden.

Für Tabelle 4.3 wurden numerische Integration für den Helmholtz-Koeffizienten so-

wie analytische Integration für den Laplace-Operator verwendet. Die Fehlerkonver-

genz ist dabei nahezu identisch mit konstanten Koeffizienten in Tabelle 4.2. Für große

Tiefen n > 8 kommt es zu einem Absinken der Fehlerkonvergenz. Dies ist auf das

Abbruchkriterium der Integration zurückzuführen. Eine vollständige Kopplung zwi-

schen Integrator und dünnem Gitter ist zum aktuellen Zeitpunkt noch nicht realisiert.

Dies führt zu überflüssigen Berechnungen. Um die Laufzeit für große Tiefen zu kon-

61


trollieren, muss daher ein fixes Abbruchkriterium für die maximale Tiefe gesetzt wer-

den. Dies hat zur Folge, dass für flächenmäßig große Gebiete zu früh abgebrochen

wird, obwohl das dünne Gitter noch eine höhere Genauigkeit bieten würde. Entspre-

chend können variable Koeffizienten für kleine |t| nicht mit voller Genauigkeit inte-

griert werden und weisen eine reduzierte Fehlerordnung auf. Auf konstante Koeffizi-

enten hat dies keinen Einfluss, da diese exakt integriert werden können.


en,∞en,2

en−1,2en,2

en,H1en−1,H1

en,H1

2 7 1.40× 10−1 1.73× 10−2 1.35× 10−1

3 31 7.80× 10−2 1.80 6.59× 10−3 2.62 1.07× 10−1 1.264 111 3.07× 10−2 2.54 2.32× 10−3 2.85 6.81× 10−2 1.575 351 1.04× 10−2 2.95 7.75× 10−4 2.99 3.81× 10−2 1.796 1023 3.27× 10−3 3.18 2.49× 10−4 3.11 2.00× 10−2 1.907 2815 9.86× 10−4 3.31 7.78× 10−5 3.20 1.02× 10−2 1.968 7423 3.03× 10−4 3.25 2.38× 10−5 3.26 5.16× 10−3 1.989 18943 9.39× 10−5 3.23 7.41× 10−6 3.22 2.59× 10−3 1.99

10 47103 3.14× 10−5 2.99 2.74× 10−6 2.71 1.29× 10−3 2.00

Tabelle 4.3: Diskretisierungsfehler für variable Koeffizienten λ (x, y, z) = 11+x2+y2+z2

Bisher wurden lediglich Einheitshyperwürfel ]0, 1[ betrachtet. Damit auch komple-

xere Geometrien verwendet werden können, werden krummlinige Koordinatensyste-

me eingeführt [11]. Diese bilden planare Gebiete durch invertierbare Abbildungen auf

den Hyperwürfel ab. Durch Verknüpfung mehrerer Würfel können auch komplexere

Gebiete auf Einheitswürfel abgebildet werden. Abbildung 4.4 zeigt eine Kreisschei-

be, bestehend aus 5 zusammenhängenden strukturierten Gebieten, die jeweils auf das

Einheitsquadrat abgebildet werden. Wobei jedes Teilgebiet durch gemeinsame Kanten

mit seinen Nachbarn verbunden ist. In diesem Fall ergeben sich für die Anzahl der

Gitterpunkte drei Freiheitsgrade. Jeder Freiheitsgrad ist dabei wie eine Dimension zu

behandeln.

Hierzu wurde die Bibliothek „UGblocks“ für zweidimensionale block-strukturierte

Gitter um dünne Gitter erweitert. In „UGblocks“ können Vierecke durch gemeinsa-

me Kanten miteinander verknüpft werden. Anschließend wird die Anzahl der Frei-

heitsgrade durch Färbung ermittelt. Nun erfolgt für jede Farbe eine Verfeinerung des

dünnen Gitters. Der Übergang zwischen regulär verfeinerten Vierecken erfolgt mithil-

fe der Neumann„=Prewavelet-Randelemente sowie des Korrekturverfahrens aus Ab-

schnitt 3.4.3. Durchgehende Prewavelets sind aufgrund unterschiedlicher Färbungen

nicht möglich.

62


Jedes Viereck kann außerdem durch Koordinatentransformationen der Kanten an-

gepasst werden. Abbildung 4.3 zeigt die Abbildung Ψ : Q 7→ P vom Einheitsquadrat

P auf das krummlinige Gebiet Q, wobei (s1, s2) 7→ (x1, x2) = Ψ (x1x2), sodass

xi = Ψi (s1, s2, . . . , sn) (4.9)

si = Ψ−1i (x1, x2, . . . , xn) . (4.10)

Partielle Differentialgleichungen der Form

∇ (A (x)∇u) +∇u b (x) + c (x) u = f (x) (4.11)

werden dazu überführt in [9]

∇ (A∗ (s)∇u) +∇u b∗ (s) + c∗ (s) u = f ∗ (s) (4.12)

mit

A∗ (s) :=J−1Ψ (s)

(J−1Ψ (s) (A (Ψ (s)))

)|det JΨ (s)|

b∗ (s) :=J−1Ψ (s) (b (Ψ (s))) |det JΨ (s)|

c∗ (s) :=c (Ψ (s)) |det JΨ (s)|

f ∗ (s) := f (Ψ (s)) |det JΨ (s)| .

s1

s2

PΨ

x1

x2

Q

Abbildung 4.3: Koordinatentransformation mit stetiger Abbildung Ψ

Als numerisches Testbeispiel wird der dreidimensionale Einheitshyperwürfel ent-

63


Abbildung 4.4: Block-strukturiertes dünnes Gitter mit krummlinigen Rändern

sprechend Abbildung 4.5 mit

x1 =12

cos(

π

2

(s1 +

12

))(s2 + 1)

x2 =12

sin(

π

2

(s1 +

12

))(s2 + 1)

x3 = s3 (4.13)

transformiert.

Dadurch erhält man für das Poisson-Problem folgenden variablen Koeffizienten:

A∗ (s1, s2) =

− 2

π (s2+1) 0 0

0 −π (s2+1)2 0

0 0 −π3 (s2+1)8

(4.14)

Tabelle 4.4 zeigt die Entwicklung des Diskretisierungsfehlers für verschie-

64


dene Tiefen. Hierzu wurde die Abweichung von der exakten Lösung u =

sin (xπ) sin (yπ) sin (zπ) mit verschiedenen Normen bestimmt (Vgl Tabelle 4.4).

Für die rechte Seite ergibt sich daher

f =π2 cos

(π s22

)cos(π z) sin

(π s12

)4

−π cos(π z) sin

(π s12

)sin(π s2

2

)2 (s2 + 1)

(4.15)

−π3 cos(π z) sin

(π s12

)sin(π s2

2

)(s2 + 1)

8

−π5 cos(π z) sin

(π s12

)sin(π s2

2

)(s2 + 1)

8.

Abbildung 4.5: Dünnes Gitter mit Tiefe n = 7 für ein dreidimensionales, krummlinigumrandetes Gebiet

4.3 Variable Koeffizienten in hohen Dimensionen

In [15] wurde gezeigt, dass die Konditionszahl sowohl in der Tiefe n als auch der Di-

mension d die Komplexität O (1) aufweist. Obwohl durch den Einsatz dünner Gitter

der Fluch der Dimension halbwegs umgangen werden kann, wächst der Speicherauf-

wand mit O(3dN(log N)d−1), da die Diskretisierungssterne der Steifigkeitsmatrix voll-

ständig abgespeichert werden. Zunächst wurde der Ansatz verfolgt, diese Einträge dy-

namisch zu berechnen, da sie für jeden Durchlauf von Algorithmus 4 nur ein einziges

Mal angewendet werden. Sofern jeder der 2d Fälle in einem eigenen Prozess ausge-

führt wird (Parallelisierung wird in Kapitel 5 behandelt), wird sogar pro Iteration der

65



en,∞en,2

en−1,2en,2

en,H1en−1,H1

en,H1

2 7 3.94× 10−2 7.58× 10−3 6.43× 10−2

3 31 2.23× 10−2 1.77 2.99× 10−3 2.53 3.44× 10−2 1.874 111 1.04× 10−2 2.14 1.02× 10−3 2.92 2.54× 10−2 1.355 351 4.02× 10−3 2.59 3.61× 10−4 2.83 1.60× 10−2 1.596 1023 1.34× 10−3 3.00 1.29× 10−4 2.81 9.23× 10−3 1.737 2815 4.23× 10−4 3.17 4.36× 10−5 2.95 4.87× 10−3 1.898 7423 1.28× 10−4 3.30 1.45× 10−5 3.02 2.51× 10−3 1.949 18943 3.77× 10−5 3.40 4.59× 10−6 3.15 1.27× 10−3 1.97

10 47103 1.08× 10−5 3.48 1.42× 10−6 3.23 6.41× 10−4 1.99

Tabelle 4.4: Diskretisierungsfehler für krummlinig umrandetes Gebiet für L∞-Norm,L2-Norm und H1-Norm

Methode der konjugierenden Gradienten nur ein einziger Zugriff ausgeführt. Selbst

bei konstanten Koeffizienten und variablen Koeffizienten als Tensorprodukt, und folg-

lich ohne numerische Integration, dauert die Berechnung der Diskretisierungssterne

wesentlich länger als die Matrix-Vektor-Multiplikation. Daher kann auf die statische

Berechnung mit Abspeicherung nicht verzichtet werden.

In diesem Abschnitt soll die Fehlerordnung für höhere Dimensionen betrachtet wer-

den. Damit ein Vergleich mit d = 3 gezogen werden kann, ist eine maximale Tiefe

n = 10 wünschenswert. Daraus ergibt sich anhand des Speicheraufwands eine Limi-

tierung auf d = 6. Das sechsdimensionale Helmholtz-Problem

−∆u + cu = f in Ω := [0, 1]6 (4.16)

u = 0 on ∂Ω

wird auf einem Cluster mit 8 Knoten und 256GB RAM pro Knoten ausgeführt. Es wer-

den sowohl der konstante Koeffizient c = 1 als auch der variable Koeffizient

c (x, y, z, u, v, w) :=(1− x2

) (1− y2

) (1− z2

) (1− u2

) (1− v2

) (1− w2

). (4.17)

betrachtet. Die rechte Seite f wird so gewählt, dass

u = sin (xπ) sin (yπ) sin (zπ) sin (uπ) sin (vπ) sin (wπ)

eine Lösung von Gleichung 4.16 ist.

66


Tabelle 4.5 zeigt den Diskretisierungsfehler für konstante Koeffizienten (c = 1) so-

wie den variablen Koeffizienten aus Gleichung 4.17 in der Maximumsnorm. Der Dis-

kretisierungsfehler verhält sich dabei entsprechend der Herleitung in [41]. Das Kon-

vergenzverhalten verschlechtert sich auch in der L2-Norm (Tabelle 4.6) nicht und kon-

vergiert für konstante Koeffizienten genauso schnell wie für variable Koeffizienten.

Dies zeigt, dass durch die Anwendung der Semi-Orthogonalität kein bemerkenswer-

ter Fehler entsteht.

konstant Koeffizient variabler Koeffizientn DOF en,∞

en−1,∞en,∞

en,∞en−1,∞

en,∞

2 13 4.04× 10−1 4.04× 10−1

3 97 2.84× 10−1 1.42 2.84× 10−1 1,424 545 1.07× 10−1 2.65 1.08× 10−1 2.645 2561 4.03× 10−2 2.65 4.03× 10−2 2.676 10625 1.53× 10−2 2.63 1.53× 10−2 2.637 40193 5.66× 10−3 2.71 5.66× 10−3 2.718 141569 2.13× 10−3 2.66 2.13× 10−3 2.669 471041 7.88× 10−4 2.70 7.88× 10−4 2.70

10 1496065 2.79× 10−4 2.82 2.79× 10−4 2.82

Tabelle 4.5: Fehlerkonvergenz für das sechsdimensionale Helmholtz-Problem ohnebzw. mit variablem Koeffizienten für die Maximumsnorm

konstant Koeffizient variabler Koeffizientn DOF en,2

en−1,2en,2

en,2en−1,2

en,2

2 13 6.37× 10−3 1.77× 10−2

3 97 4.38× 10−3 1.45 1.37× 10−2 1.294 545 2.52× 10−3 1.74 5.89× 10−3 2.335 2561 1.27× 10−3 1.99 2.26× 10−3 2.616 10625 5.76× 10−4 2.20 8.78× 10−4 2.577 40193 2.43× 10−4 2.37 3.47× 10−4 2.538 141569 9.7× 10−5 2.50 1.37× 10−4 2.549 471041 3.7× 10−5 2.62 5.3× 10−5 2.60

10 1496065 1.4× 10−5 2.72 2.0× 10−5 2.66

Tabelle 4.6: Fehlerkonvergenz für das sechsdimensionale Helmholtz-Problem ohnebzw. mit variablem Koeffizienten für die L2-Norm

67


4.4 Inhomogene Randprobleme

Inhomogene Randbedingungen wurden bereits in Abschnitt 3.4.3 theoretisch betrach-

tet. Daher wird sich dieser Abschnitt der praktischen Umsetzung sowie numerischen

Ergebnissen widmen. Algorithmus 1 verwendet die in Gleichung 2.28 vorgestellten

Prewavelets. Hierbei ist es vollkommen ausreichend, dem Vektor der nodalen Basis

lediglich Werte an den Randpunkten zuzuweisen. Nun erfolgt die Multiplikation mit

der Steifigkeitsmatrix. Diese beinhaltet bereits die Korrektur des Dualraums. Der resul-

tierende Korrekturvektor kann anschließend von der rechten Seite abgezogen werden.

Der folgende iterative Löser (Listing 3.1 und 4.1) löst ein homogenes Randproblem

und muss nicht weiter angepasst werden. Abschließend wird die Randfunktion der

Lösung aufaddiert und in die nodale Basis mit Algorithmus 2 umgewandelt.

Tabelle 4.7 zeigt die Abweichung e der numerischen Lösung uDn von der exakten

Lösung u (x, y, z) = exp (x) exp (y) exp (z) u (x, y, z) = ex ey ez in der diskreten L2-

Norm sowie der Maximumsnorm gemessen.


en,∞en,2

en−1,2en,2

en,H1en−1,H1

en,H1

2 81 1.70× 10−2 1.61× 10−3 1.97× 10−2

3 225 5.88× 10−3 2.89 6.95× 10−4 2.31 1.29× 10−2 1.524 593 1.68× 10−3 3.50 3.21× 10−4 2.16 8.25× 10−3 1.575 1505 5.05× 10−4 3.32 1.26× 10−4 2.55 4.48× 10−3 1.846 3713 1.49× 10−4 3.38 4.60× 10−5 2.74 2.41× 10−3 1.867 8961 4.33× 10−5 3.44 1.50× 10−5 3.06 1.25× 10−3 1.938 21249 1.35× 10−5 3.21 4.61× 10−6 3.26 6.34× 10−4 1.979 49665 4.13× 10−6 3.27 1.36× 10−6 3.38 3.22× 10−4 1.97

10 114689 1.22× 10−6 3.38 3.90× 10−7 3.49 1.61× 10−4 1.99

Tabelle 4.7: Diskretisierungsfehler für inhomogene Randbedingungen

68

Kapitel 5

Parallelisierung und Laufzeitanalyse

Bedingt durch die vielen Inter-Gitter-Operatoren (Prolongation, Restriktion, Vergröbe-

rung) ist eine Aufteilung des Gitters auf parallele Systeme nicht sinnvoll. Ebenso ist

die Anzahl der Gitterpunkte relativ gering und kann somit problemlos für jeden Pro-

zess oder zumindest auf jedem Knoten gespeichert werden. Der hohe Rechenaufwand

entsteht zum einen aus der rechenintensiven lokalen Matrix-Vektor-Multiplikation (3d

Operationen pro Gitterpunkt) und zum anderen aus der umschließenden Wiederho-

lungsschleife über alle 2d Fälle. Da jeder einzelne Fall nahezu den selben Rechenauf-

wand besitzt, wurde der Ansatz gewählt, diese auf verteilten Systemen mithilfe von

MPI zu parallelisieren. Zusätzlich wurde für die Matrix-Vektor-Multiplikation sowie

für alle weiteren lokalen Vektoroperationen eine Parallelisierung durch OpenMP ge-

wählt. In diesem Kapitel werden im Folgenden zunächst die parallelen Vektoropera-

tionen mit geteiltem Speicher untersucht. Anschließend soll die parallele Berechnung

der 2d Knoten sowie der Aufwand für den Austausch der Ergebnisse betrachtet wer-

den. Der große Vorteil des in Kapitel 3 vorgestellten Algorithmus ist, dass für die Par-

allelisierung außer der Aufteilung auf die Prozessoren sowie der Addition der Teiler-

gebnisse keine weiteren Anpassungen notwendig sind. Die Lastaufteilung erfolgt sehr

homogen, und der zusätzliche Aufwand für den Datenaustausch ist sehr gering.

69

KAPITEL 5. PARALLELISIERUNG UND LAUFZEITANALYSE

5.1 Parallelisierung der Vektoroperationen für geteilten

Speicher

Die Implementierung des in Kapitel 3 vorgestellten Verfahrens beruht auf einer Ex-

pression-Template-basierten Bibliothek. Die in Abschnitt 3.5 vorgestellten elementaren

Vektoroperationen lassen sich sehr einfach auf Shared-Memory-Architekturen paralle-

lisieren. In Listing 5.1 wird einem Vektor ein beliebiger Operator oper zugewiesen.

Hierzu wird im Zuweisungsoperator für jeden Punkt des Gitters der Operator ausge-

wertet. Eine einzige Schleife übernimmt die Iteration über alle Dimensionen und kann

über #pragma omp parallel parallelisiert werden.

Die Laufzeiten sind jeweils für eine Addition zweier Vektoren c = a + b für ein

3-dimensionales dünnes Gitter in Tabelle 5.1 und ein 6-dimensionales Gitter in Ta-

belle 5.3 aufgeführt. Diese sind offensichtlich hauptsächlich durch die Bandbreite des

Speicherzugriffs limitiert, da die Berechnung durch Parallelisierung nur unwesentlich

beschleunigt wird. Der Speedup in Tabelle 5.2 bzw. Tabelle 5.4 zeigt die Beschleuni-

gung der parallelen Addition im Vergleich zur Berechnung mit einem Thread. Selbst

für große Datenstrukturen (n = 10) wird der theoretische Speedup um die Anzahl der

Threads nicht erreicht. Für eine große Anzahl paralleler Threads kommt es sogar zu

einer Verlangsamung.

Als nächstes wird die Multiplikation c = A * b jedes Punktes mit einem Diskreti-

sierungsstern betrachtet. Für eine Dünngittervariable wird dazu für jedes volle Unter-

gitter eine Matrix-Vektor-Multiplikation ausgeführt. Somit sind für jeden Gitterpunkt

je 3d Additionen und Multiplikationen notwendig. Auch hier erweist sich die Speicher-

bandbreite als limitierender Faktor. Eine Parallelisierung der Multiplikation führt für

d = 3 sogar in den meisten Fällen zu einer Verlangsamung (vgl. Tabelle 5.6). Auch für

höherdimensionale Probleme zeigt sich in Tabelle 5.8 keine nennenwerte Beschleuni-

gung.

Während in Tabelle 5.5 für d = 3 die Laufzeit entsprechend der Anzahl der Gitter-

punkte skaliert, zeigen sich in Tabelle 5.7 für d = 6 erhebliche Sprünge zwischen n = 7

und n = 8. Die Laufzeit steigt in diesem Fall um mehr als den Faktor 102, während sich

die Anzahl der Gitterpunkte etwa verdreifacht. Daher werden nun die Einzellaufzeiten

näher betrachtet.

Für n = 8 beträgt die maximale Anzahl an Gitterpunkten der vollen Untergitter

1701, für n = 7 dagegen nur 729. Eine genaue Analyse der Laufzeiten ergab, dass es ab

1024 Gitterpunkten zu einem drastischen Anstieg der Laufzeiten um den Faktor 100

70


kommt. Der plötzliche Anstieg der Laufzeit lässt sich daher auf Verdrängungsstrate-

gien im Cache zurückführen. Der Diskretisierungsstern greift im Extremfall auf 567

Einträge benachbarter Elemente zu. Elementare Multiplikationen auf Vollgitterebene

werden auch für die Berechnung der Matrix-Vektor-Multiplikation benötigt und ver-

ursachen dort einen erheblichen Anteil am Rechenaufwand. Eine Parallelisierung der

Multiplikation für geteilten Speicher ist daher nicht sinnvoll.

Listing 5.1: Iterative Zuweisung

1 template <size_t DIM>

2 Variable<DIM>&

3 Variable<DIM>::operator=(const Operator<DIM>& oper)

4 assert(oper.getGrid() == getGrid());

5

6 int size = 1;

7 for(int i = 0; i < DIM; ++i)

8 size *= getGrid().getSize(i);

9

10

11 #pragma omp parallel

12

13 array<int,DIM> index;

14

15 #pragma omp for

16 for(int i = 0; i< size; ++i)

17

18 int tmp = i;

19 for(int k = 0; k < DIM; ++k)

20 index[k] = tmp%getGrid().getSize(k);

21 tmp /= getGrid().getSize(k);

22

23 getValue(index) = oper.getValue(index);

24

25

26 return *this;

27

71


ThreadsTiefe 1 2 4 8 16 32n = 1 9.34× 10−6 1.34× 10−5 1.63× 10−5 3.75× 10−5 2.24× 10−5 4.94× 10−5

n = 2 1.68× 10−5 2.60× 10−5 4.58× 10−5 2.59× 10−5 8.25× 10−5 1.48× 10−4

n = 3 2.66× 10−5 6.88× 10−5 9.87× 10−5 1.38× 10−4 2.23× 10−3 3.76× 10−4

n = 4 5.91× 10−5 1.38× 10−4 2.10× 10−4 3.08× 10−4 4.49× 10−4 8.75× 10−4

n = 5 1.46× 10−4 2.45× 10−4 3.57× 10−4 5.86× 10−4 9.61× 10−4 6.66× 10−3

n = 6 3.76× 10−4 4.84× 10−4 6.01× 10−4 7.44× 10−4 9.22× 10−4 2.18× 10−3

n = 7 1.00× 10−3 9.05× 10−4 1.36× 10−3 1.22× 10−3 2.01× 10−3 6.90× 10−3

n = 8 6.16× 10−3 3.80× 10−3 1.77× 10−3 2.12× 10−3 4.07× 10−3 7.49× 10−3

n = 9 6.06× 10−3 6.30× 10−3 2.97× 10−3 2.78× 10−3 4.36× 10−3 1.08× 10−2

n = 10 1.43× 10−2 9.17× 10−3 7.35× 10−3 4.64× 10−3 5.21× 10−3 8.41× 10−3

Tabelle 5.1: Laufzeit [s] für parallele Vektoraddition für ein 3-dimensionales dünnesGitter

ThreadsTiefe Gitterpunkte 2 4 8 16 32n = 1 1 0.70 0.57 0.25 0.42 0.19n = 2 13 0.65 0.37 0.65 0.20 0.11n = 3 97 0.39 0.27 0.19 0.01 0.07n = 4 545 0.43 0.28 0.19 0.13 0.07n = 5 2661 0.60 0.41 0.25 0.15 0.02n = 6 10625 0.78 0.62 0.50 0.41 0.17n = 7 40193 1.11 0.74 0.82 0.50 0.15n = 8 141569 1.62 3.49 2.90 1.51 0.82n = 9 471041 0.96 2.04 2.18 1.39 0.56n = 10 1496065 1.56 1.94 3.07 2.74 1.70

Tabelle 5.2: Speedup für parallele Vektoraddition für ein 3-dimensionales dünnes Git-ter

ThreadsTiefe 1 2 4 8 16 32n = 1 1.54× 10−5 2.41× 10−5 3.05× 10−5 4.24× 10−5 2.68× 10−5 7.29× 10−3

n = 2 4.36× 10−5 5.63× 10−5 6.88× 10−5 9.09× 10−5 1.64× 10−4 2.77× 10−4

n = 3 9.58× 10−5 2.10× 10−4 2.25× 10−4 3.68× 10−4 6.18× 10−4 6.70× 10−3

n = 4 3.49× 10−4 7.40× 10−4 7.74× 10−4 2.84× 10−3 1.68× 10−3 7.41× 10−3

n = 5 6.00× 10−3 2.92× 10−3 2.10× 10−3 2.84× 10−3 6.78× 10−3 1.09× 10−2

n = 6 5.60× 10−3 6.85× 10−3 5.99× 10−3 8.76× 10−3 7.63× 10−3 1.59× 10−2

n = 7 2.69× 10−2 1.69× 10−2 1.52× 10−2 1.96× 10−2 2.18× 10−2 4.47× 10−2

n = 8 1.05× 10−1 5.98× 10−2 3.91× 10−2 3.52× 10−2 3.40× 10−2 6.97× 10−2

n = 9 3.95× 10−1 2.13× 10−1 1.19× 10−1 8.99× 10−2 8.24× 10−2 8.62× 10−2

n = 10 1.47× 100 1.13× 100 4.79× 10−1 2.72× 10−1 2.42× 10−1 2.07× 10−1

Tabelle 5.3: Laufzeit [s] für parallele Vektoraddition für ein 6-dimensionales dünnesGitter

72



Tabelle 5.4: Speedup für parallele Vektoraddition für ein 6-dimensionales dünnes Git-ter

ThreadsTiefe 1 2 4 8 16 32n = 1 1.36× 10−5 1.62× 10−5 4.39× 10−5 8.95× 10−5 1.40× 10−4 2.11× 10−4

n = 2 2.29× 10−5 2.69× 10−5 1.39× 10−4 2.08× 10−4 4.10× 10−4 9.25× 10−4

n = 3 9.27× 10−5 7.56× 10−5 3.71× 10−4 5.86× 10−4 1.19× 10−3 2.07× 10−3

n = 4 2.55× 10−4 2.95× 10−4 8.30× 10−4 1.43× 10−3 2.59× 10−3 4.33× 10−3

n = 5 9.33× 10−4 8.55× 10−4 1.85× 10−3 2.70× 10−3 4.31× 10−3 8.59× 10−3

n = 6 2.70× 10−3 2.54× 10−3 3.83× 10−3 5.76× 10−3 8.74× 10−3 1.31× 10−2

n = 7 7.38× 10−3 6.80× 10−3 9.56× 10−3 1.08× 10−2 1.52× 10−2 2.19× 10−2

n = 8 2.13× 10−2 1.88× 10−2 2.28× 10−2 2.45× 10−2 3.41× 10−2 4.31× 10−2

n = 9 6.85× 10−1 7.69× 10−1 7.73× 10−1 7.78× 10−1 7.84× 10−1 7.96× 10−1

n = 10 2.99× 100 3.36× 100 3.35× 100 3.36× 100 3.37× 100 3.39× 100

Tabelle 5.5: Laufzeit [s] für parallele Stencil-Multiplikation für ein 3-dimensionalesdünnes Gitter


Tabelle 5.6: Speedup für parallele Stencil-Multiplikation für ein 3-dimensionales dün-nes Gitter

73


ThreadsTiefe 1 2 4 8 16 32n = 1 8.72× 10−5 1.02× 10−4 1.51× 10−4 1.33× 10−4 2.19× 10−4 3.33× 10−4

n = 2 1.50× 10−3 1.13× 10−3 1.38× 10−3 1.30× 10−3 1.86× 10−3 2.40× 10−3

n = 3 9.17× 10−3 7.63× 10−3 7.78× 10−3 9.51× 10−3 9.81× 10−3 1.37× 10−2

n = 4 6.37× 10−2 5.01× 10−2 5.17× 10−2 5.63× 10−2 6.32× 10−2 7.01× 10−2

n = 5 3.62× 10−1 2.93× 10−1 2.89× 10−1 2.95× 10−1 3.14× 10−1 3.25× 10−1

n = 6 1.81× 100 1.42× 100 1.46× 100 1.48× 100 1.48× 100 1.53× 100

n = 7 7.92× 100 6.63× 100 6.49× 100 6.49× 100 6.64× 100 6.97× 100

n = 8 1.77× 103 1.41× 103 1.40× 103 1.40× 103 1.40× 103 1.40× 103

n = 9 1.65× 104 1.40× 104 1.38× 104 1.38× 104 1.38× 104 1.38× 104

Tabelle 5.7: Laufzeit [s] für parallele Stencil-Multiplikation für ein 6-dimensionalesdünnes Gitter

ThreadsTiefe Gitterpunkte 2 4 8 16 32n = 1 1 0.85 0.58 0.65 0.40 0.26n = 2 13 1.33 1.09 1.15 0.81 0.63n = 3 97 1.20 1.18 0.96 0.94 0.67n = 4 545 1.27 1.23 1.13 1.01 0.91n = 5 2561 1.24 1.25 1.23 1.15 1.11n = 6 10625 1.27 1.24 1.22 1.22 1.18n = 7 40193 1.19 1.22 1.22 1.19 1.14n = 8 141569 1.26 1.26 1.26 1.26 1.26n = 9 471041 1.18 1.19 1.19 1.20 1.20

Tabelle 5.8: Speedup für parallele Stencil-Multiplikation für ein 6-dimensionales dün-nes Gitter

74


5.2 Parallelisierung für verteilte Systeme

Als Nächstes wird die Parallelisierung für verteilte Systeme betrachtet. Hierbei spei-

chert jeder Knoten eines Clusters sowohl alle Dünngitter-Variablen als auch die ent-

sprechenden Diskretisierungssterne ab. Der Aufwand der Initialisierung der Diskreti-

sierungssterne für die analytische Integration ist im Vergleich zur Gesamtlaufzeit mit

mehreren Iterationen der Multiplikation klein.

Der Speicheraufwand ist jedoch sehr groß, da für jeden Gitterpunkt ein Diskreti-

sierungsstern mit 3d Werten abgespeichert werden muss. Für numerische Integration

steigt der Rechenaufwand stark an. Da jeder Knoten dieselben Diskretisierungssterne

vorhält, erscheint eine Parallelisierung der Berechnung sinnvoll.

In der Regel entspricht die Anzahl der Knoten des Clusters einer Zweierpotenz.

Dadurch ergibt sich eine gleichmäßige Verteilung der 2d Fälle auf die Prozesse der

Knoten. Der Berechnungsaufwand eines jeden Falls ist in etwa identisch. Daher ist

keine weitere Optimierung der Lastverteilung notwendig.

Jeder Knoten speichert einen lokalen Ergebnisvektor mit seinem Beitrag der einge-

sammelten Überschüsse zum Ergebnis der Multiplikation. Diese Werte, die für jeden

Feingitterpunkt vorgehalten werden müssen, werden am Ende einer Multiplikation an

alle anderen Prozesse verteilt und addiert. Listing 5.2 und Listing 5.3 zeigen den Aus-

tausch sowie die Addition mithilfe von MPI_exchange. Hierzu wird für jedes volle

Untergitter MPI_Allreduce auf den gesamten lokalen Vektor angewendet.

Listing 5.2: MPI-Austausch SparseVariable


2 void

3 SparseVariable<DIM>::MPI_exchange()

4 array<int,DIM> index;

5 if(num_procs > 1)

6 MPI_exchange(DIM-1,index);

7

8


10 void

11 SparseVariable<DIM>::MPI_exchange(int dimension,

12 array<int,DIM>& index)

13 int depth = 0;

14 for(int i = dimension+1; i < DIM; ++i)

75


15 depth += index[i];

16 for(int i = 0; i < max(0,getMaxDepth()-depth); ++i)

17 index[dimension] = i;

18 if(dimension > 0)

19 MPI_exchange(dimension-1,index);

20 else

21 int lin_index = getVariableIndex(index);

22

23 variable_vector[lin_index]->MPI_exchange();

24

25

26

Listing 5.3: MPI-Austausch Variable


2 void Variable<DIM>::MPI_exchange()

3 int size = 1;

4 for(int i = 0; i < DIM; ++i)

5 size *= grid.getSize(i);

6

7 std::vector<double> sendbuffer (values, values + size);

8

9 MPI_Allreduce(&sendbuffer[0], values, size,

10 MPI_DOUBLE, MPI_SUM, MPI_COMM_WORLD);

11

Im Falle d = 3 gibt es 8 Fälle. Daher wurde in Tabelle 5.9 eine Parallelisierung für

maximal 8 Prozesse untersucht. In diesem Fall steigt die Laufzeit in etwa proportional

zur Anzahl der Gitterpunkte. Die Laufzeiten sind in Tabelle 5.10 aufgeführt. Lediglich

zwischen n = 8 und n = 9 kommt es zu einem erheblichen Anstieg der Laufzeit, da

erstmals die Anzahl der Gitterpunkte der vollen Untergitter die Größe 1024 übersteigt.

Dies ist für d = 6 besonders auffällig. In diesem Fall wird 1024 schon bei n = 8

erreicht. Tabelle 5.11 zeigt daher ein ähnliches Verhalten, wie es schon in Tabelle 5.7 zu

beobachten war.

Dagegen erzielt die Parallelisierung mit verteiltem Speicher eine gleichmäßig hohe

Beschleunigung. Für Tabelle 5.12 wurden bis zu 32 parallele Prozesse auf einem Cluster

mit 32 Kernen gestartet. Der Datenaustausch beschränkt sich dabei lediglich auf die

76


Anzahl der Gitterpunkte in der ersten Spalte der Tabelle.

ProzesseTiefe 1 2 4 8n = 1 5.81× 10−5 1.07× 10−4 1.16× 10−4 1.69× 10−4

n = 2 2.14× 10−4 5.03× 10−4 4.00× 10−4 5.30× 10−4

n = 3 1.05× 10−3 5.62× 10−4 5.78× 10−4 6.93× 10−4

n = 4 4.90× 10−3 3.65× 10−3 4.49× 10−3 1.59× 10−3

n = 5 1.64× 10−2 1.02× 10−2 7.99× 10−3 5.07× 10−3

n = 6 4.08× 10−2 2.26× 10−2 1.53× 10−2 1.13× 10−2

n = 7 1.27× 10−1 7.34× 10−2 4.69× 10−2 3.68× 10−2

n = 8 3.81× 10−1 2.27× 10−1 1.51× 10−1 1.19× 10−1

n = 9 1.20× 101 6.56× 100 3.31× 100 1.84× 100

n = 10 5.25× 101 2.65× 101 1.44× 101 7.77× 100

Tabelle 5.9: Laufzeit für parallele Matrix-Vektor-Multiplikation für ein 3-dimensionalesdünnes Gitter

ProzesseTiefe Gitterpunkte 2 4 8n = 1 1 0.54 0.50 0.34n = 2 7 0.42 0.53 0.40n = 3 31 1.86 1.81 1.51n = 4 111 1.34 1.09 3.07n = 5 351 1.60 2.05 3.23n = 6 1023 1.80 2.66 3.62n = 7 2815 1.74 2.71 3.47n = 8 7423 1.68 2.53 3.22n = 9 18943 1.82 3.61 6.49n = 10 47103 1.98 3.66 6.75

Tabelle 5.10: Speedup für parallele Matrix-Vektor-Multiplikation für ein 3-dimensiona-les dünnes Gitter

77


ProzesseTiefe 1 2 4 8 16 32n = 1 7.97× 10−3 3.59× 10−3 1.94× 10−3 6.56× 10−4 3.94× 10−4 1.74× 10−4

n = 2 8.17× 10−2 4.41× 10−2 2.44× 10−2 1.14× 10−2 5.04× 10−3 2.50× 10−3

n = 3 7.18× 10−1 3.59× 10−1 1.81× 10−1 9.12× 10−2 4.63× 10−2 2.40× 10−2

n = 4 4.96× 100 2.50× 100 1.25× 100 6.28× 10−1 3.21× 10−1 1.66× 10−1

n = 5 2.57× 101 1.33× 101 7.07× 100 3.54× 100 1.80× 100 9.67× 10−1

n = 6 1.25× 102 6.24× 101 3.18× 101 1.63× 101 8.94× 100 5.10× 100

n = 7 5.50× 102 2.85× 102 1.40× 102 7.32× 101 4.14× 101 2.46× 101

n = 8 1.20× 105 5.93× 104 3.14× 104 1.51× 104 8.37× 103 4.31× 103

Tabelle 5.11: Laufzeit für parallele Matrix-Vektor-Multiplikation für ein 6-dimensiona-les dünnes Gitter

ProzesseTiefe Gitterpunkte 2 4 8 16 32n = 1 1 2.22 4.11 12.15 20.23 45.80n = 2 13 1.85 3.35 7.14 16.19 32.68n = 3 97 2.00 3.98 7.88 15.51 29.98n = 4 545 1.98 3.97 7.89 15.47 29.82n = 5 2561 1.93 3.63 7.26 14.28 26.57n = 6 10625 2.00 3.92 7.65 13.95 24.45n = 7 40193 1.93 3.93 7.52 13.30 22.35n = 8 141569 2.03 3.84 7.98 14.38 27.97

Tabelle 5.12: Speedup für parallele Matrix-Vektor-Multiplikation für ein 6-dimensiona-les dünnes Gitter

78

Kapitel 6

Erweiterung für adaptive Verfeinerung

Für die Effizienz dünner Gitter wurde bisher stets eine gewisse Glattheit der Funktio-

nen angenommen. Das dünne Gitter trifft eine Vorauswahl an Gitterpunkten des Voll-

gitters, ohne dass Kenntnisse über die zu suchende Funktion notwendig sind. Durch

adaptive Verfeinerung können zusätzliche Erkenntnisse der zu suchenden Lösungs-

funktion berücksichtigt werden.

Die natürliche Datenstruktur für die Koeffizienten eines dünnen Gitters ist die

Baumstruktur. Der Verfeinerungsbaum wurde bisher stets vollständig aufgespannt

und wurde daher nicht explizit angegeben. Für unvollständige Bäume sind zwei An-

sätze möglich.

Die Gitterpunkte des dünnen Gitters können gleichzeitig als finite Elemente aufge-

fasst werden. Jedes Element entspricht dabei dem Träger der entsprechenden Hutfunk-

tion des Gitterpunktes. Für hierarchische Basisfunktionen wurden Elemente durch

Verfeinerung halbiert.

So könnte durch eine komplexe Baumstruktur für jedes Element einzeln festgelegt

werden, ob es verfeinert wird oder nicht. Dabei ist zu beachten, dass jedes Element

ein entsprechendes Elternelement in allen Dimensionen benötigt (vgl. [33]). Die re-

sultierende Baumstruktur weist eine hohe Komplexität und Verzweigung auf. Dies

ermöglicht sehr flexibel anpassbare adaptive Verfeinerungen. Allerdings können die

vorgestellten Operatoren aus Abschnitt 3.1 nicht mehr direkt angewendet werden. Sie

basieren auf Rekursion und benötigen dafür Tensorproduktstrukturen der dünnen Git-

ter.

Ein weiterer Ansatz erhält daher die Tensorproduktstruktur und verfeinert jede Di-

mension separat. Der Name Semi-Adaptivität deutet darauf hin, dass hierbei nicht

vollständig adaptiv verfeinert wird.

79

KAPITEL 6. ERWEITERUNG FÜR ADAPTIVE VERFEINERUNG

6.1 Semi-adaptive Verfeinerung

Abbildung 6.2 zeigt ein zweidimensionales dünnes Gitter mit semi-adaptiver Verfeine-

rung. In diesem Fall wurde für beide Dimensionen derselbe Verfeinerungsbaum ver-

wendet. Abbildung 6.1 zeigt die entsprechende Baumstruktur. Bis Level 2 handelt es

sich um ein reguläres dünnes Gitter. Anschließend wird adaptiv verfeinert, wobei das

entsprechende Element jeweils halbiert wird. Da es sich um ein homogenes Problem

handelt, können Dirichlet-Prewavelets an den Rändern verwendet werden. Für inho-

mogene Randbedingungen kann auf das Verfahren in Abschnitt 3.4.3 zurückgegriffen

werden.

Für Dirichlet-Prewavelets ist L2-Orthogonalität allerdings nur für nodale Basisfunk-

tionen im Inneren gegeben. Neumann-Prewavelets weisen zusätzlich L2-Orthogonali-

tät mit nodalen Basisfunktionen am Rand auf. Deren Einsatz ist jedoch aufgrund ihrer

Inhomogenität auf den Rand beschränkt. Daher müssen zusätzlich Geisterknoten ohne

zusätzliche Unbekannte eingeführt werden.

Abbildung 6.1 zeigt rechts die entsprechenden Basisfunktionen zur aufgeführten

Baumstruktur. Für den Einsatz am Rand wurden Dirichlet-Prewavelets verwendet. So-

bald die Verfeinerung nicht mehr vollständig durchgeführt wird (ab Level 3), werden

zusätzlich Geisterknoten am Rand benötigt. Dadurch reichen die Standard-Prewave-

lets über das verfeinerte Gebiet hinaus und können ihre Orthogonalitätseigenschaft

zum Grobgitter erhalten.

Zur Umrechnung von nodaler Basis zur Prewavelet-Basis wurde die fünf-diagona-

le Koeffizientenmatrix mithilfe einer LR-Zerlegung invertiert. Dieses Verfahren kann

weiterhin verwendet werden, da durch die Tensorproduktstruktur jede Dimension se-

parat gelöst werden kann. Statt des aktuellen Levels und des nächstgröberen Levels,

müssen nun unter Umständen weitere Level berücksichtigt werden. Hierzu wird ent-

sprechend über den Baum in Abbildung 6.1 iteriert.

Zur Aufstellung der Koeffizientenmatrix für Level 3 liegen die Grobgitterpunkte

vollständig auf Level 2. Für den linken Randpunkt wurden Dirichlet-Prewavelets ver-

wendet. Auf der rechten Seite wird für den Übergang ein Geisterknoten benötigt. Für

die Zerlegung in Prewavelets und Grobgitteranteil wird er nicht berücksichtigt. Hier-

für ergibt sich folgender Lösungsvektor

[x3,1 x2,1 x3,2 x2,2 x3,3 x2,3 x3,4 x2,4 x2,5 x2,6 x2,7 x2,8

]T. (6.1)

80


Anhand der Koeffizientenmatrix

WTadaptiv =

0.9 −35

110

12 1 1

21

10 −35 1 −3

51

1012 1 1

2110 −

35 1 −3

51

1012 1 1

21

10 −35 1 −3

5110

12 1 1

212 1

1

1

(6.2)

lassen sich durch Multiplikation die Überschüsse berechnen. Aufgrund des Geister-

knotens ist Matrix WTadaptiv nicht quadratisch.

Zur Aufstellung der Koeffizientenmatrix für Level 4 verteilen sich die Grobgitter-

punkte auf Level 2 und 3. Daher ergibt sich der Lösungsvektor

[x3,1 x3,2 x3,3 x3,4 x4,1 x3,5 x4,2 x3,6 x3,7 x2,4 x2,5 x2,6 x2,7 x2,8

]T. (6.3)

Da weiterhin über alle Level iteriert wird, müssen die Grobgitterwerte nur an das

nächstgröbere Gitter weitergereicht werden. Für die Aufstellung der Massen- und Stei-

figkeitsmatrix muss dagegen die unterschiedliche Maschenweite berücksichtigt wer-

den. Hierzu wird zusätzlich für jede Unbekannte deren Koordinate hinterlegt.

81


Es ergibt sich die Koeffizientenmatrix

WTadaptiv =

1

1

1 1212 1 1

21

10 −35 1 −3

51

1012 1 1

2110 −

35 1 −3

51

1012 1 1

212 1

1

1

1

1

. (6.4)

Der Vorteil dieser Methode ist die einfache Umsetzung sowie die effiziente Itera-

tion über die Punkte eines Gitters, da diese konsekutiv im Speicher abgelegt werden

können. Das resultierende Gitter (Abbildung 6.2) setzt sich wie zuvor aus regulären

Gittern zusammen. Abbildung 6.3 zeigt, wie aus den Gitterpunkten der einzelnen Le-

vel aus Abbildung 6.1 durch Tensorprodukte reguläre Gitter zu einem semi-adaptiven

Gitter kombiniert werden. Die Dreiecksstruktur ist jedoch nur gegeben, wenn die Tiefe

der Verfeinerung in allen Dimensionen identisch ist. Für jedes volle Untergitter wer-

den wie im regulären Fall zusätzlich alle Grobgitterpunkte vorgehalten. Durch eine un-

gleichmäßige Verfeinerung in einem bestimmten Teilgebiet entsteht ein sehr schlechtes

Verhältnis zwischen Grobgitterpunkten und Feingitterpunkten für Gitter mit großer

Tiefe. Dadurch steigt der Speicheraufwand. Das Gitter mit t = 4 muss daher 13 Grob-

gitterpunkte vorhalten und weist lediglich 2 Feingitterpunkte auf.

82


Level 0

Level 1

Level 2

Level 3

Level 4

x

y

1.0

x

y

1.0

x

y

1.0

x

y

1.0

x

y

1.0

Abbildung 6.1: Baumstruktur der semi-adaptiven Verfeinerung (links) sowie die zu-gehörigen Prewavelets (rechts). Am Rand werden Dirichlet-Prewavelets verwendet.Im Inneren am Übergang zum gröberen Gitter müssen zusätzliche Geisterpunkte (rot)hinzugefügt werden.

Abbildung 6.2: Zweidimensionales semi-adaptives Gitter

83


Abbildung 6.3: Das zweidimensionale semi-adaptive Gitter wird aus Tensorproduktenvon Abbildung 6.4 zusammengesetzt.

84


6.2 Adaptiv verfeinerte dünne Gitter

Adaptive dünne Gitter können lokal verfeinert werden. Die Verfeinerung bezieht sich

dabei auf ein bestimmtes Gebiet und nicht auf einen Anteil einer Dimension. Man er-

hält dadurch lokal verfeinerte dünne Gitter, die auch lokal die typischen Eigenschaften

dünner Gitter besitzen, allerdings die Tensorproduktstruktur verlieren. Damit bleibt

insbesondere auch im Fall adaptiver Verfeinerung die Eigenschaft erhalten, dass dün-

ne Gitter signifikant weniger Punkte als volle Gitter enthalten.

Im Gegensatz zu regulären dünnen Gittern und semi-adaptiv verfeinerten dünnen

Gittern wird für jedes Basiselement eines Teilraums gesondert festgelegt, ob dieses

verfeinert wird. In Abbildung 6.4 sind zu verfeinernde Basiselemente rot markiert.

Allerdings weist die entsprechende Baumstruktur zusätzliche hängende Knoten auf

(graue Knoten). Diese sind notwendig, da für jedes verfeinerte Element zwingend in

jeder Dimension ein Elternelement vorhanden sein muss [33]. Durchgezogene Pfeile

stehen dabei für Verzweigungen, die durch eine Verfeinerung entstanden sind, wäh-

rend gestrichelte Pfeile entweder von einem hängenden Knoten oder einem bereits

existierenden Elternelement ausgehen.

Die Eltern-Kind-Beziehungen in allen Dimensionen sind für eine Übertragung der

Dünngitteroperatoren aus Abschnitt 3.1 obligatorisch. Sie werden insbesondere für

Prolongation, Restriktion und Vergröberungs-Operatoren benötigt. Zusätzlich müssen

die in Abschnitt 6.1 eingeführten Geisterknoten (blaue Knoten) aufgegriffen werden.

Sie induzieren keinen zusätzlichen Freiheitsgrad und werden nur zur lokalen Anwen-

dung der Diskretisierungsmatrizen benötigt.

Im vorherigen Abschnitt wurden zur lokalen Berechnung volle Untergitter verwen-

det. Zur Addition der 2d Fälle mithilfe von Prolongationen und Restriktionen wurden

die Dimensionen soweit sortiert, dass Prolongationen vor Restriktionen ausgeführt

wurden. Abbildung 6.5 zeigt das Einsammeln der Inkremente für das zwei-dimensio-

nale Beispiel aus Abbildung 6.4. Die Summe setzt sich dabei analog zu Abbildung 3.4

zusammen.

Um Doppelungen zu vermeiden, wird für Restriktionen nicht der Eintrag selbst ad-

diert. Stattdessen wird der Vorgänger ohne das eigene Inkrement restringiert. Für den

Fall (Res,Res) gibt es keinen Vorgänger für doppelte Restriktion in beiden Dimensio-

nen. Für Prolongation in beiden Dimension (Pro,Pro) wird an der Wurzel begonnen.

Da jeder Knoten ein Elternteil jeder Dimension besitzt, ist die Reihenfolge der Abarbei-

tung der Dimensionen nicht relevant, solange Prolongationen vor Restriktionen abge-

85


arbeitet werden. Für Restriktionen wird für die entsprechende Dimension jeweils auf

dem feinsten Level begonnen. Hierzu wird die Baumstruktur, beginnend vom Wur-

zelknoten aus, rekursiv und nach Dimensionen sortiert traversiert. Dabei werden nur

Kinder mit Restriktionen berücksichtigt. Wird ein Blatt erreicht oder gehen von einem

Knoten nur noch Prolongationen aus, so wird folglich von diesem Knoten aus mit dem

Einsammeln der Inkremente begonnen.

Prinzipiell lassen sich die Algorithmen aus Kapitel 3 auf adaptive Gitter ohne große

Anpassungen übertragen. Für Abschnitt 6.1 konnte die Datenstruktur im Wesentlichen

erhalten bleiben. Sie wurde lediglich durch eine Baumstruktur erweitert. Aus dieser

konnten reguläre Untergitter generiert werden. Im Gegensatz zu vollen Untergittern

weisen sie einige Lücken auf. Hierzu mussten auch die Operatoren entsprechend an-

gepasst werden.

Im Falle adaptiver Gitter ist jedoch eine vollständig neue Datenstruktur zu imple-

mentierten, da keine regulären Untergitter mehr vorhanden sind. Für eine Implemen-

tierung ergeben sich folgende Anforderungen:

• Schneller Zugriff auf einen beliebigen Punkt des Gitters

• Iteration über alle Punkte einer bestimmten Tiefe

• Zugriff auf Eltern bzw. Kinder

• Dynamische Verwaltung der Geisterknoten

In [35] werden Baumstrukturen und Hash-Tabellen hinsichtlich ihrer Eignung für

adaptive dünne Gitter verglichen. Bisher wurde eine Baumstruktur verwendet. Dies

hatte zur Folge, dass für jedes Level zusätzlich zu den jeweiligen Inkrementen auch

die Grobgitterpunkte vorgehalten wurden. Der Speichermehraufwand wurde durch

die vollständige Trennung der einzelnen Level kompensiert. Im Falle adaptiver Gitter

würde dies jedoch bedeuten, dass für jedes Blatt der Baumstruktur des Gitters neben

den Inkrementen noch Grobgitterpunkte und Geisterpunkte vorgehalten werden müs-

sen. Daher ist eine Kombination aus Hash-Tabellen und einer Baumstruktur notwen-

dig. Wenn für jedes Level eine eigene Hash-Tabelle verwendet wird, können verschie-

dene Blätter auf dieselben Werte zugreifen, sofern sie auf demselben Level liegen.

86


(0,0)

(1,0) (1,1)

(2,0) (2,1) (2,2)

(3,1) (3,2)

(a) Träger der Basisfunktionen (b) Dünnes Gitter mit Baumstruktur

Abbildung 6.4: Baumstruktur für zweidimensionale adaptive Verfeinerung.Rote Gitterpunkte werden verfeinert, hängende Knoten sind grau, Geisterknoten blaudargestellt.

87


2,2 2,22,0 2,0

1,0 1,01,1 1,1

3,1 3,13,0 3,0

2,1 2,1

0,0 0,0

= +

2,22,0

1,0 1,1

3,13,0

0,0

2,1

(Pro,Pro) (Pro,Res)

x

x

x x

x

y

y

y

y

y

x

x

x x

x

y

y

y

y

y

x

x

x x

x

y

y

y

y

y

2,0

1,0

3,0

+

(Res,Pro)

x

x

x x

x

y

y

y

y

y

2,2 2,22,0

1,01,1 1,1

3,1 3,13,0

2,1 2,1

0,0 0,0

+

x

x

x x

x

y

y

y

y

y

(Res,Res)

Abbildung 6.5: Alle möglichen Kombinationen aus Prolongationen (Pro) und Restrik-tionen (Res) für die zweidimensionale Matrix-Vektor-Multiplikation auf adaptivendünnen Gittern.

88

Kapitel 7

Abschließende Bemerkungen

Ziel dieser Arbeit war es, elliptische partielle Differentialgleichungen in hohen Dimen-

sionen mit variablen Koeffizienten zu lösen. Entgegen bisherigen Ansätzen wurden

dazu keinerlei Annahmen bezüglich des variablen Koeffizienten getroffen. Zahlrei-

che Lösungsverfahren für Tensorprodukte verwenden das Unidirektionale Prinzip.

Dadurch lässt sich die Matrix-Vektor-Multiplikation auf eindimensionale Operatoren

zurückführen. Der Ansatz eindimensionaler Operatoren wurde aufgegriffen, da er ef-

fiziente rekursive Algorithmen ermöglicht.

Bereits in der Dissertation [27] wurde 1995 ein Verfahren für zweidimensionale

Probleme vorgestellt. Die dafür verwendete Semi-Orthogonalität lässt sich aber nicht

direkt auf hochdimensionale Probleme anwenden. Für zweidimensionale Probleme

kann auf die Berechnung der Einträge der Diskretisierungsmatrix für überlappende

Gebiete verzichtet werden, da die hierarchische Basisfunktion a-Orthogonalität für den

Laplace-Operator aufweist.

Für hochdimensionale Probleme kann stattdessen die L2-Orthogonalität von Prewa-

velets verwendet werden. Aus theoretischer Sicht lässt sich dies leicht realisieren, was

in [31] bewiesen wurde. Darauf aufbauend wurde ein geeignetes Lösungsverfahren

entwickelt. Hauptaugenmerk lag auf der Matrix-Vektor-Multiplikation. Für zweidi-

mensionale Probleme wurde mit dem Q-Zyklus ein Verfahren gefunden, um die Über-

lappung eines jeden Levels mit allen anderen effizient zu berechnen. Der Q-Zyklus ließ

sich allerdings nicht auf hochdimensionale Probleme übertragen.

In Anlehnung an das Unidirektionale Prinzip wurde die Kombination eindimen-

sionaler „TopDown“- und „BottomUp“-Durchläufe in verschiedenen Richtungen auf

2d Fälle aufgeteilt und jeweils separat berechnet. Im Zuge der Umsetzung entstand da-

bei eine umfangreiche Softwarebibliothek. Zahlreiche algorithmische Ansätze konnten

89

KAPITEL 7. ABSCHLIESSENDE BEMERKUNGEN

somit schnell umgesetzt werden, da sie sich auf eine Verkettung primitiver Operato-

ren zurückführen ließen. Die Implementierung beruht auf moderner objektorientierter

Softwareentwicklung und dem Einsatz von Expression Templates. Dies gewährleistet

ein hohes Maß am Lesbarkeit, da Implementierungsdetails gekapselt werden.

Durch die Kapselung können Datenstrukturen und Operatoren leicht ersetzt wer-

den. So ließ sich die semi-adaptive Verfeinerung sehr schnell umsetzen. Die Methode

der konjugierenden Gradienten sowie die Matrix-Vektor-Multiplikation konnte direkt

übertragen werden, da lediglich Variablen auf Gittern und Operatoren auf Variablen

verwendet werden. Folglich musste nur eine Datenstruktur für Variablen auf semi-

adaptiven Gittern ergänzt werden.

Da Umfang und Anforderungen an die Softwarebibliothek ständig gewachsen sind,

wurde am Ende dieser Arbeit ein Punkt erreicht, der eine Überarbeitung der Imple-

mentierung erfordert. Erste Grundlagen zur Adaptivität wurden bereits gelegt. Die

Verwendung von Geisterpunkten für den Übergang zwischen verfeinerten Gebieten

und dem Grobgitter fand bereits bei semi-adaptiven Gittern Verwendung. Ebenso die

Verwaltung der Adaptivität, wenn auch nur für jede Dimension separat, mithilfe einer

Baumstruktur sowie die Generierung eindeutiger Indizes als Grundlage einer Hashta-

belle.

Komplexere Geometrien können als blockstrukturiertes Gitter realisiert werden.

Anstelle der Dimension tritt dabei die Anzahl der Freiheitsgrade für die Anzahl der

Gitterpunkte in den Vordergrund. Diese ist noch für hochdimensionale Geometrien zu

erweitern. Im Zuge einer Neuentwicklung könnte dies mit der Adaptivität verbunden

werden.

Für reguläre Gitter führt die Koordinatentransformation für gebogene Kanten zu

verzerrten Elementen. Zur Berechnung der Einträge der Diskretisierungsmatrix wer-

den meist gerade Kanten angenommen. Für dünne Gitter haben die Basisfunktionen

oftmals eine sehr große Tiefe in einer Dimension, sind jedoch in allen anderen Dimen-

sionen sehr grob. Gerade Kanten würden bei der Integration einen großen Fehler indu-

zieren. Daher wurde für gebogene Kanten im Rahmen dieser Arbeit der bereits trans-

formierte Koeffizient integriert. Aus Anwendersicht wäre es wünschenswert, nur die

Transformation zu definieren und den variablen Koeffizienten daraus generieren zu

lassen.

Anschließend müssen die Einträge der Diskretisierungsmatrix der verzerrten Ele-

mente für variable Koeffizienten numerisch integriert werden. Auch hierzu sind An-

sätze bereits realisiert. Die Koppelung zwischen Integrator und dünnem Gitter ist aber

90

KAPITEL 7. ABSCHLIESSENDE BEMERKUNGEN

noch ausbaufähig und gerade in Bezug auf adaptive Verfeinerung nicht trivial.

Im Zuge einer Neuentwicklung ist von Beginn an der Rechenaufwand und der

Speicherbedarf im Auge zu behalten. Die Verwendung dünner Gitter ermöglichte

hochdimensionale Probleme. Immerhin konnte für d = 6 bis Tiefe n = 10 eine Lö-

sung gefunden werden. Die Anzahl der Gitterpunkte ist dabei kleiner 50000. Da der

Speicheraufwand einer einzigen Variablen durch die Verwendung regulärer voller Git-

ter für jedes Level jedoch weit größer ist, wurden dadurch bereits die Grenzen der

Rechenleistung erreicht. Für eine Parallelisierung mit verteiltem Speicher wurde die

vollständige Diskretisierungsmatrix auf jedem Prozess berechnet und vorgehalten. Im

Zuge der Erweiterung für adaptive Verfeinerung und blockstrukturierte Gitter kann

durch eine örtliche Verteilung der Geometrie auf einzelne Prozessoren der Speicher-

aufwand minimiert werden.

Es bleibt die Hoffnung, dass der Grundstein für weitere Entwicklungen mit dieser

Arbeit gelegt werden konnte. Daher lag der Fokus dieser Arbeit auf einer ausführli-

chen Beschreibung der Algorithmen sowie den Grundlagen zur Umsetzung. Dünne

Gitter haben sich in den letzten drei Jahrzehnten kontinuierlich weiterentwickelt. Ihr

Durchbruch scheiterte aber oftmals an ihrer Abhängigkeit von Annahmen und der feh-

lenden Verallgemeinerung. Ein weiterer Schritt zu einem universellen Löser wurde mit

dieser Arbeit in diese Richtung hoffentlich vollzogen.

91

Literaturverzeichnis

[1] ACHATZ, Stefan: Adaptive finite Dünngitter-Elemente höherer Ordnung für elliptische

partielle Differentialgleichungen mit variablen Koeffizienten, TU München, Dissertati-

on, 2003

[2] BALDER, Robert ; ZENGER, Christoph: The solution of multidimensional real

Helmholtz equations of sparse grids. In: SIAM J. Sci. Comp. 17 (1996), Nr. 3, S.

631–646

[3] BUNGARTZ, Hans-Joachim: Dünne Gitter und deren Anwendung bei der adaptiven

Lösung der dreidimensionalen Poisson-Gleichung, Fakultät für Informatik, Technische

Universität München, Dissertation, November 1992

[4] BUNGARTZ, Hans-Joachim: Concepts for higher order finite elements on sparse

grids. In: Proceedings of the 3. int. conf. on spectral and high order methods University

of Houston, 1996 (Houston Journal of Mathematics), S. 159–170

[5] BUNGARTZ, Hans-Joachim ; GRIEBEL, Michael: A note on the complexity of sol-

ving Poisson’s equation for spaces of bounded mixed derivatives. In: Journal of

Complexity 15 (1999), Nr. 2, S. 167–199

[6] BUNGARTZ, Hans-Joachim ; ZENGER, Christoph: A unidirectional approach for d-

simensional finite element methods of higher order on sparse grids. Copper Mountain,

CO, April 1996

[7] BUSE, Gerrit ; PFLÜGER, Dirk ; JACOB, Riko: Efficient pseudorecursive evaluation

schemes for non-adaptive sparse grids. In: GARCKE, Jochen (Hrsg.) ; PFLÜGER,

Dirk (Hrsg.): Sparse Grids and Applications - Munich 2012 Bd. 97, Springer Inter-

national Publishing, 2014 (Lecture Notes in Computational Science and Enginee-

ring), S. 1–27

93

LITERATURVERZEICHNIS

[8] DIJKEMA, Tammo J. ; SCHWAB, Christoph ; STEVENSON, Rob: An aaptive wavelet

method for solving high-dimensional elliptic PDEs. In: Constructive approximation

30 (2009), dec, Nr. 3, S. 423–455

[9] DORNSEIFER, Thomas ; PFLAUM, Christoph: Discretization of elliptic differential

equations on curvilinear bounded domains with sparse grids. In: Computing 56

(1996), Nr. 3, S. 197–213

[10] FISCHER, Patrick ; AVERBUCH, Amir ; ISRAELI, Moshe ; BEYLKIN, Gregory ; COIF-

MAN, Ronald: Adaptive solution of multidimensional PDEs via tensor product

wavelet decomposition. In: International Journal of Pure and Applied Mathematics 44

(2008), Nr. 1, S. 75–115

[11] GORDON, William J. ; HALL, Charles A.: Construction of curvilinear co-ordinate

systems and applications to mesh generation. In: International Journal for Numerical

Methods in Engineering 7 (1973), Nr. 4, S. 461–477

[12] GRIEBEL, Michael: Adaptive sparse grid multilevel methods for elliptic PDEs

based on finite differences. In: Computing 61 (1998), S. 151–179

[13] GRIEBEL, Michael: Sparse grids and related approximation schemes for higher di-

mensional problems. In: PARDO, L. (Hrsg.) ; PINKUS, A. (Hrsg.) ; SULI, E. (Hrsg.) ;

TODD, M.J. (Hrsg.): Foundations of Computational Mathematics (FoCM05), Santander,

Cambridge University Press, 2006, S. 106–161

[14] GRIEBEL, Michael ; HAMAEKERS, Jan: A wavelet based sparse grid method for

the electronic Schrödinger equation. In: SANZ-SOLÉ, M. (Hrsg.) ; SORIA, J. (Hrsg.)

; VARONA, J. (Hrsg.) ; VERDERA, J. (Hrsg.) ; European Mathematical Society (Ver-

anst.): Proceedings of the International Congress of Mathematicians Bd. III. Madrid,

Spain : European Mathematical Society, 2006, S. 1473–1506. – Also as INS Preprint

No. 0603

[15] GRIEBEL, Michael ; HULLMANN, Alexander: On a multilevel preconditioner and

its condition numbers for the discretized Laplacian on full and sparse grids in

higher dimensions. In: Singular Phenomena and Scaling in Mathematical Models.

Springer International Publishing Switzerland, 2014, S. 263–296

94


[16] GRIEBEL, Michael ; OSWALD, Peter: Tensor product type subspace splittings and

multilevel iterative methods for anisotropic problems. In: Advances in Computatio-

nal Mathematics 4 (1995), Nr. 1, S. 171–206

[17] HÄRDTLEIN, Jochen: Moderne Expression Templates Programmierung - Weiterentwi-

ckelte Techniken und deren Einsatz zur Lösung partieller Differentialgleichungen, Tech-

nische Fakultät der Universität Erlangen-Nürnberg, Dissertation, 2007

[18] HÄRDTLEIN, Jochen ; PFLAUM, Christoph ; LINKE, Alexander ; WOLTERS, Cars-

ten H.: Advanced expression templates programming. In: Computing and Visuali-

zation in Science 13 (2009), Nr. 2, S. 59

[19] HARTMANN, Rainer ; PFLAUM, Christoph: Efficient Ritz-Galerkin discretization

of PDEs with variable coefficients in arbitrary dimensions using sparse grids. In:

Proceedings in Applied Mathematics and Mechanics, 2017

[20] HARTMANN, Rainer ; PFLAUM, Christoph: A prewavelet-based algorithm for the

solution of second-order elliptic differential equations with variable coefficients

on sparse grids. In: Numerical Algorithms (2017)

[21] JAFFARD, Stéphane: Wavelet methods for fast resolution of elliptic problems. In:

SINUM 29 (1992), Nr. 4, S. 965–986

[22] NIEDERMEIER, Andreas ; ZIMMER, Stefan. ; LAI, C-H. (Hrsg.) ; BJOERSTAD, P.

(Hrsg.) ; CROSS, M. (Hrsg.) ; WIDLUND, O. (Hrsg.): Implementational aspects of

prewavelet sparse grid methods. 1999

[23] NOORDMANS, Jan ; HEMKER, Pieter W.: Convergence results for 3D sparse grid

approaches. In: Numerical Lin. Alg. with Applic. 5 (1998), Nr. 5, S. 363–376

[24] PEHERSTORFER, Benjamin: Model order reduction of parametrized systems with sparse

grid learning techniques, Department of Informatics, Technische Universität Mün-

chen, Dissertation, 2013

[25] PEHERSTORFER, Benjamin ; ZIMMER, Stefan ; ZENGER, Christoph ; BUNGARTZ,

Hans-Joachim: A multigrid method for adaptive sparse grids. In: SIAM Journal

on Scientific Computing 37 (2015), Nr. 5, S. 51–70

[26] PFLAUM, Christoph: Discretization of second order elliptic differential equations

on sparse grids. In: Progress in partial differential equations, Pont-a-Mousson 1994,

Harlow: Longman, 1994 (Pitman Research Notes in Mathematics Series 2)

95


[27] PFLAUM, Christoph: Diskretisierung elliptischer Differentialgleichungen mit dünnen

Gittern, Technische Universität München, Dissertation, 1995

[28] PFLAUM, Christoph: Convergence of the combination technique for second-order

elliptic differential equation. In: SIAM J. Numer. Anal. 34 (1997), Nr. 6, S. 2431–2455

[29] PFLAUM, Christoph: A multilevel algorithm for the solution of second order el-

liptic differential equations on sparse grids. In: Numer. Math. 79 (1998), S. 141–155

[30] PFLAUM, Christoph: Fast and robust multilevel algorithms, Julius-Maximilians-

Universität Würzburg, Diss., 1998

[31] PFLAUM, Christoph ; HARTMANN, Rainer: A sparse grid discretization of the

Helmholtz equation with variable coefficients in high dimensions. In: SIAM J.

Numerical Analysis 54 (2016), Nr. 4, S. 2707–2727

[32] PFLAUM, Christoph ; ZHOU, Aihui: Error analysis of the combination technique.

In: Numer. Math. 84 (1999), S. 327–350

[33] PFLÜGER, Dirk ; PEHERSTORFER, Benjamin ; BUNGARTZ, Hans-Joachim: Spatially

adaptive sparse grids for high-dimensional data-driven problems. In: Journal of

Complexity 26 (2010), Nr. 5, S. 508–522. – SI: HDA 2009

[34] RHEINFELS, Tim: Numerische Integration lokaler Steifigkeitsmatrizen auf dünnen

Gittern im d-dimensionalen Raum, Department Informatik, Friedrich-Alexander-

Universität Erlangen-Nürnberg, Bachelorarbeit, 2016

[35] SCHIEKOFER, Thomas: Die Methode der Finiten Differenzen auf dünnen Gittern

zur Lösung elliptischer und parabolischer partieller Differentialgleichungen, Universi-

tät Bonn, Dissertation, 1999

[36] SCHWAB, Christian ; TODOR, Radu A.: Sparse finite elements for stochastic elliptic

problems: higher order moments. In: Computing 71 (2003), September, Nr. 1, S. 43–

63

[37] SPRENGEL, Frauke: Periodic interpolation and wavelets on sparse grids. In: Nu-

merical Algorithms 17 (1998), May, Nr. 1, S. 147–169

[38] Kapitel a wavelet-based conjugate gradient method for solving Poisson equations.

In: TANAKA, Nobuatsu: Wavelets and Their Applications: Case Studies. Society for

Industrial and Applied Mathematics, 1998, S. 45–73

96


[39] VASSILEVSKI, Panayot S. ; WANG, Junping: Stabilizing the hierarchical basis by

approximate wavelets II: implementation and numerical results. In: SIAM J. Sci.

Comput. 20 (1998), Nr. 2, S. 490–514

[40] ZEISER, Andreas: Fast matrix-vector multiplication in the sparse-grid Galerkin

method. In: Journal of Scientific Computing 47 (2011), Nr. 3, S. 328–346

[41] ZENGER, Christoph: Sparse grids. In: HACKBUSCH, Wolfgang (Hrsg.): Parallel

algorithms for partial differential equations, proceedings of the sixth GAMM-Seminar,

Kiel, 1990 Bd. 31. Kiel : Vieweg, 1991 (Notes on Numerical Fluid Mechanics), S.

240–251

[42] Kapitel Hierarchische Datenstrukturen für glatte Funktionen mehrerer Veränder-

licher. In: ZENGER, CHRISTOPH: Informatik und Mathematik. Berlin, Heidelberg :

Springer Berlin Heidelberg, 1991, S. 142–150

[43] Kapitel A sparse grid PDE solver; discretization, adaptivity, software design and

parallelization. In: ZUMBUSCH, Gerhard W.: Advances in Software Tools for Scientific

Computing. Berlin, Heidelberg : Springer Berlin Heidelberg, 2000, S. 133–177

97

Documents

Effiziente Verfahren zur Lösung partieller ... · nauigkeit der Finite-Elemente-Methode auf voll besetzten Gittern nahezu erreicht wur- de. Die Konvergenzrate des Gauß-Seidel-Verfahrens