�������� � �� � � � ��� � ��������� � � �! " # $ % &'()*+,-
Universitat Stuttgart Fakultat Mathematik
Große lineare Gleichungssysteme
I. Lineare Gleichungssysteme II. Direkte Verfahren
Numerische Simulationsverfahren fuhren oftmals auf große linea-re Gleichungssysteme. Bei nichtlinearen Problemen sind in derRegel in jedem Teilschritt lineare Probleme zu losen. Die Dis-kretisierung komplexer Geometrieen in drei Raumdimensionenkann bereits bei geringen Genauigkeitsanforderungen auf Syste-me mit mehreren Hunderttausend oder gar Millionen Unbekanntenfuhren. Somit bilden Losungsverfahren fur lineare Gleichungssy-steme das Herzstuck einer numerischen Simulation. Ein linearesGleichungssystem ist ein Problem der Gestalt
.0/2143mit einer
bekannten Matrix.
und der rechten Seite3. Viele Problemklas-
sen fuhren auf dunnbesetzte Matrizen.
mit Bandstruktur. DasHauptziel ist eine moglichst schnelle und billige Berechnung einergenau genugen Naherungslosung. Grundsatzlich unterscheidetman zwischen direkten und iterativen Methoden. Man spricht vonoptimalen Verfahren, falls der Aufwand linear von der Anzahl derUnbekannten abhangt.
Direkte Verfahren berechnen die Losung exakt. Die Matrix.
wirdin ein Produkt
.514687zweier Matrizen zerlegt. Diese sind so
gewahlt, dass sich6:9<;>=
(bzw.7?9<;>=
) leicht berechnen lassen.Die Losung ergibt sich als
/@1A. 9<; 3B1C7 9<; 6 9<; 3.
Bandmatrix unstrukturierte Matrix
nz = 480
n = 64
nz = 909
nz = 2112
n = 256
nz = 7709
nz = 8832
n = 1024
nz = 63549
A
L
nz = 480
n = 64
nz = 1237
nz = 2112
n = 256
nz = 14775
nz = 8832
n = 1024
nz = 223209
A
L
Fill-in Effekt einer LU-Zerlegung
Zur Anwendung auf große Systeme sind direkte Verfahren aller-dings oftmals zu langsam und benotigen zuviel Speicherplatz.
III. Iterative Verfahren IV. VorkonditioniererIterative Verfahren berechnen die Losung naherungsweise. Aus-gehend von einem Startwert wird in jedem Schritt die neueNaherung aus den vorhergehenden Iterationswerten berechnet.Ist eine gewunschte Genauigkeit erreicht, so endet der Algorith-mus. Die Qualitat eines Iterationsverfahrens hangt entscheidendvon der Konvergenzrate und dem Aufwand pro Schritt ab.
0 1 2 3 4 5 6 7
x 104
0
50
100
150
200
250
Anzahl Unbekannte
Zei
t
iterativ (CG−Verfahren)direkt (LU−Zerlegung)
101
101
102
103
104
105
Dimension der Matrix ist n2
Anz
ahl d
er It
erat
ione
n (A
bbru
chkr
iteriu
m: r
el. R
esid
uum
<=
1e−
8)
Vergleich von Jacobi, Gauss−Seidel und opt. SOR
JacobiGauss−Seidelopt. SOR
Zeitvergleich (links) und klassische Iterationsverfahren (rechts)
Iterative Loser gibt es in einer Vielzahl von Varianten. Die Auswahlrichtet sich vor allem nach der Beschaffenheit der Matrix
.. Fur
große Systeme sind iterative Verfahren im allgemeinen schnellerals direkte und benotigen weniger Speicherplatz.
Vorkonditionierer werden zur Beschleunigung von iterativen Ver-fahren eingesetzt. Ein guter Vorkonditionierer D ist eine Matrix,die zwei Anforderungen erfullt. Zum einen sollte die Konditions-zahl EGFHD 9<; .JI
moglichst klein sein. Außerdem muss sich dasProdukt D 9<; =
gunstig berechnen lassen. Gelost wird nun daszum Ausgangsproblem aquivalente System D 9<; .K/@1 D 9<; 3
. Oh-ne den Einsatz von Vorkonditionierern ware die Losung anwen-dungsrelevanter Probleme oft nicht in akzeptabler Zeit moglich.Fur die Effizienz ist die richtige Auswahl aus dem breiten Ange-bot von zentraler Bedeutung. Eingesetzt werden unter anderemVorkonditionier basierend auf der
L Schurkomplement–Methode,L Dirichlet–Neumann–Methode,L Multilevel–Methode,L uberlappenden Schwarzmethode.
V. Mehrgitter VI. ParallelisierungMehrgitterverfahren sind opti-
V-Zylus
male iterative Losungsverfah-ren, die auf einer Frequenz-zerlegung des (elliptischen)Differentialoperators basieren.Hoch- und niederfrequenteAnteile werden dabei von un-terschiedlich feinen Gittern re-prasentiert, auf denen sukzes-sive die Losung berechnet wird. Im Gegensatz zu direkten Losernist der Losungsaufwand hier proportional zur Anzahl der Unbe-kannten. Das macht Mehrgitterverfahren besonders geeignet furgroße Probleme mit vielen Unbekannten.
Parallelrechner bieten eine ausge-
2 4 8 16 32 640
10
20
30
40
50
60
70
Anzahl Prozessoren
Spe
edup
ideale Beschleunigungrealisierte Beschleunigung
Beschleunigung
zeichnete Moglichkeit additive aberauch multiplikative Losungsverfah-ren zu beschleunigen. Die Rechen-arbeit wird dabei auf mehrere Pro-zessoren aufgeteilt. Idealerweisesollte das Verfahren beim Einsatzvon M Prozessoren M -mal schnellersein als bei Verwendung eines Pro-zessors. In der Praxis wird dies aber selten erreicht. Zusatzlichzur eigentlichen Rechenzeit wird Zeit fur die Kommunikation zwi-schen den einzelnen Prozessoren benotigt. Daher ist ein schnel-les Kommunikationsnetz sehr wichtig.
Kontakt: Lehrstuhl 7, Mathematisches Institut ANumerische Mathematik fur HochstleistungsrechnerE-Mail: [email protected]