Hackbusch Hierarchische Matrizen

Algorithmen und Analysis
1. Auflage 2009
ISBN: 978-3-642-00222-9
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 451 Seiten

Bei der Diskretisierung von Randwertaufgaben und Integralgleichungen entstehen große, eventuell auch voll besetzte Matrizen. In dem Band stellt der Autor eine neuartige Methode dar, die es erstmals erlaubt, solche Matrizen nicht nur effizient zu speichern, sondern auch alle Matrixoperationen einschließlich der Matrixinversion bzw. der Dreieckszerlegung approximativ durchzuführen. Anwendung findet diese Technik nicht nur bei der Lösung großer Gleichungssysteme, sondern auch bei Matrixgleichungen und der Berechnung von Matrixfunktionen.

Arbeitsfeld des Autors:Diskretisierung partieller Differentialgleichungen, Diskretisierung von Integralgleichungen (Randelementmethoden), schnelle Lösung großer Gleichungssysteme, MehrgittermethodenAuszeichnungen:Leibniz-Preis, Brouwer-Medaille

Autoren/Hrsg.

Hackbusch, Wolfgang

Inhaltsverzeichnis

1;Vorwort;6
2;Inhaltsverzeichnis;10
3;Einleitung;20
3.1;Was ist die zu lösende Aufgabe, wo liegen die Schwierigkeiten?;20
3.1.1;Aufgabenbeispiele;20
3.1.2;Größenordnung der Dimension;22
3.1.3;Exakte oder näherungsweise Berechnung;22
3.2;Komplexität der Algorithmen;22
3.2.1;Komplexität;22
3.2.2;Warum braucht man (fast) lineare Komplexität für großskalige Probleme?;24
3.3;Zugrundeliegende Strukturen und Implementierungsdarstellungen;25
3.3.1;Vektor- und Matrixnotation;25
3.3.2;Implementierungsdarstellungen;26
3.3.3;Darstellungen und Operationen;31
3.4;In welchen Fällen ist lineare Komplexität erreichbar?;32
3.4.1;Familie der Diagonalmatrizen;32
3.4.2;Anwendung der schnellen Fourier-Transformation;32
3.4.3;Schwierigkeiten in anderen Fällen;33
3.5;Wo entstehen großskalige Probleme?;34
3.5.1;Diskretisierung elliptischer Differentialgleichungen;34
3.5.2;Integralgleichungen und ihre Diskretisierung;36
3.6;Angeordnete bzw. nicht angeordnete Indexmengen;40
3.6.1;Indexmengen;40
3.6.2;Vektoren xRI;41
3.6.3;Matrizen ARII;41
3.6.4;Anordnung bzw. Nichtanordnung bei hierarchischen Matrizen;42
3.7;Übersicht über die weiteren Kapitel;42
3.7.1;Lokale Rang-k-Matrizen;42
3.7.2;Hierarchie und Matrixoperationen;43
4;Rang-k-Matrizen;44
4.1;Allgemeines;45
4.2;Darstellung und Kosten;45
4.3;Operationen und ihre Kosten;47
4.4;Bestapproximation durch Rang-k-Matrizen;49
4.5;Bestapproximation von Rang--Matrizen durch Rang-k-Matrizen ;52
4.6;Rang-k-Matrix-Addition mit anschließender Kürzung;54
4.6.1;Formatierte Addition;54
4.6.2;Formatierte Agglomeration;55
4.6.3;Mehr als zwei Terme;55
4.6.4;Stufenweise ausgeführte Agglomeration;57
4.7;Varianten der Rang-k-Matrixdarstellungen;58
4.7.1;AKB-Darstellung;58
4.7.2;SVD-Darstellung;60
5;Einführendes Beispiel;62
5.1;Das Modellformat Hp;62
5.2;Zahl der Blöcke;63
5.3;Speicheraufwand;64
5.4;Matrix-Vektor-Multiplikation;64
5.5;Matrix-Addition;64
5.6;Matrix-Matrix-Multiplikation;65
5.7;Matrixinversion;67
5.8;LU-Zerlegung;68
5.8.1;Vorwärtssubstitution;68
5.8.2;Rückwärtssubstitution;69
5.8.3;Aufwand der LU-Zerlegung;69
5.9;Weitere Eigenschaften der Modellmatrizen und Semiseparabilität;70
6;Separable Entwicklung und ihr Bezug zu Niedrigrangmatrizen ;74
6.1;Grundbegriffe;75
6.1.1;Separable Entwicklungen;75
6.1.2;Exponentielle Konvergenz;76
6.1.3;Zulässigkeitsbedingungen an X,Y;78
6.2;Separable Polynom-Entwicklungen;79
6.2.1;Taylor-Entwicklung;79
6.2.2;Interpolation;81
6.2.3;Exponentielle Fehlerabschätzung;82
6.2.4;Asymptotisch glatte Kerne;83
6.2.5;Taylor-Fehlerabschätzung;84
6.2.6;Interpolationsfehler für d=1;85
6.2.7;Verschärfte Fehlerabschätzung;87
6.2.8;Interpolationsfehler für d>1;88
6.3;Weitere separable Entwicklungen;89
6.3.1;Andere Interpolationsverfahren;89
6.3.2;Transformationen;89
6.3.3;Stückweise separable Entwicklung;90
6.3.4;Kerne, die von x-y abhängen;91
6.3.5;L-harmonische Funktionen;91
6.3.6;Separable Entwicklungen mittels Kreuzapproximation;92
6.3.7;Die optimale separable Entwicklung ;92
6.4;Diskretisierung von Integraloperatoren mit separablen Kernfunktionen ;93
6.4.1;Einführung: Separable Entwicklung und Galerkin-Diskretisierung;93
6.4.2;Separable Entwicklung und allgemeine Diskretisierungen ;95
6.5;Approximationsfehler;97
6.5.1;Operatornormen;97
6.5.2;Matrixnormen;98
6.5.3;Sachgerechte Normen;100
7;Matrixpartition;102
7.1;Einleitung;102
7.1.1;Ziele;102
7.1.2;Eindimensionales Modellbeispiel;103
7.2;Zulässige Blöcke;104
7.2.1;Metrik der Cluster;104
7.2.2;Zulässigkeit;106
7.2.3;Verallgemeinerte Zulässigkeit;108
7.2.4;Erläuterung am Beispiel aus §5.1.2;109
7.3;Clusterbaum T(I);110
7.3.1;Definitionen;110
7.3.2;Beispiel;111
7.3.3;Blockzerlegung eines Vektors;112
7.3.4;Speicherkosten für T(I);113
7.4;Konstruktion des Clusterbaums T(I);115
7.4.1;Notwendige Daten;115
7.4.2;Geometriebasierte Konstruktion mittels Minimalquader;116
7.4.3;Kardinalitätsbasierte Konstruktion;120
7.4.4;Implementierung und Aufwand;120
7.4.5;Auswertung der Zulässigkeitsbedingung;121
7.5;Blockclusterbaum T(IJ);123
7.5.1;Definition des stufentreuen Blockclusterbaums;123
7.5.2;Verallgemeinerung der Definition;124
7.5.3;Alternative Konstruktion von T(IJ) aus T(I) und T(J);126
7.5.4;Matrixpartition;127
7.5.5;Beispiele;130
7.6;Alternative Clusterbaumkonstruktionen und Partitionen;131
8;Definition und Eigenschaften der hierarchischen Matrizen;132
8.1;Menge H(k,P) der hierarchischen Matrizen;132
8.2;Elementare Eigenschaften;134
8.3;Schwachbesetztheit und Speicherbedarf;135
8.3.1;Definition;135
8.3.2;Speicherbedarf einer hierarchischen Matrix;137
8.4;Abschätzung von Csp ;139
8.4.1;Erster Zugang;139
8.4.2;Abschätzung zu Konstruktion (5.30);142
8.4.3;Anmerkung zu Konstruktion (5.34);146
8.5;Fehlerabschätzungen;147
8.5.1;Frobenius-Norm;147
8.5.2;Vorbereitende Lemmata;147
8.5.3;Spektralnorm;154
8.5.4;Norm ;155
8.6;Adaptive Rangbestimmung;157
8.7;Rekompressionstechniken;159
8.7.1;Kompression durch TH;159
8.7.2;Vergröberung der Blöcke;160
8.8;Modifikationen des H-Matrixformates;160
8.8.1;H-Matrizen mit Gleichungsnebenbedingungen;160
8.8.2;Positive Definitheit;162
8.8.3;Positivität von Matrizen;163
8.8.4;Orthogonalität von Matrizen;165
9;Formatierte Matrixoperationen für hierarchische Matrizen;166
9.1;Matrix-Vektor-Multiplikation;167
9.2;Kürzungen und Konvertierungen;167
9.2.1;Kürzungen TkR, TkR und TkH;167
9.2.2;Agglomeration;169
9.2.3;Konvertierung TkRH ;169
9.2.4;Konvertierung TPPHH;171
9.2.5;Konvertierung TPPHH bei unterschiedlichen Blockclusterbäumen;171
9.3;Addition;173
9.4;Matrix-Matrix-Multiplikation;174
9.4.1;Komplikationen bei der Matrix-Matrix-Multiplikation;174
9.4.2;Algorithmus im konsistenten Fall;176
9.4.3;Algorithmus im stufentreuen Fall;186
9.5;Matrix-Inversion;189
9.5.1;Rekursiver Algorithmus;189
9.5.2;Alternativer Algorithmus mittels Gebietszerlegung;191
9.5.3;Newton-Verfahren;191
9.6;LU- bzw. Cholesky-Zerlegung;192
9.6.1;Format der Dreiecksmatrizen;192
9.6.2;Auflösung von LUx=b;193
9.6.3;Matrixwertige Lösung von LX=Z und XU=Z;195
9.6.4;Erzeugung der LU- bzw. Cholesky-Zerlegung;196
9.7;Hadamard-Produkt;197
9.8;Aufwand der Algorithmen;198
9.8.1;Matrix-Vektor-Multiplikation;198
9.8.2;Matrix-Addition;198
9.8.3;Matrix-Matrix-Multiplikation;199
9.8.4;Matrix-Inversion;207
9.8.5;LU- bzw. Cholesky-Zerlegung;208
10;H2-Matrizen;210
10.1;Erster Schritt: M|bVbWb;210
10.2;Zweiter Schritt: M|VW;214
10.3;Definition der H2-Matrizen;216
10.3.1;Definition;216
10.3.2;Transformationen;216
10.3.3;Speicherbedarf;218
10.3.4;Projektion auf H2-Format;219
10.4;Hinreichende Bedingungen für geschachtelte Basen;221
10.4.1;Allgemeiner Fall;221
10.4.2;Beispiel: Approximation von Integraloperatoren durch Interpolation ;222
10.5;Matrix-Vektor-Multiplikation mit H2-Matrizen;223
10.5.1;Vorwärtstransformation;223
10.5.2;Multiplikationsphase;224
10.5.3;Rücktransformation;225
10.5.4;Gesamtalgorithmus;225
10.6;H2-Matrizen mit linearem Aufwand;226
10.7;Adaptive Bestimmung der H2-Räume V und W;228
10.8;Matrix-Matrix-Multiplikation von H2-Matrizen;232
10.8.1;Multiplikation bei gegebenem H2-Format;232
10.8.2;Multiplikation bei gesuchtem H2-Format;233
10.9;Numerisches Beispiel;234
11;Verschiedene Ergänzungen;236
11.1;Konstruktion schneller Iterationsverfahren;236
11.2;Modifizierte Clusterbäume für schwach besetzte Matrizen ;238
11.2.1;Problembeschreibung;238
11.2.2;Finite-Element-Matrizen;239
11.2.3;Separierbarkeit der Matrix;241
11.2.4;Konstruktion des Clusterbaums;243
11.2.5;Anwendung auf Invertierung;245
11.2.6;Zulässigkeitsbedingung;245
11.2.7;LU-Zerlegung;246
11.2.8;H-Matrixeigenschaften der LU-Faktoren;247
11.2.9;Geometriefreie Konstruktion der Partition;250
11.3;Schwache Zulässigkeit;251
11.3.1;Definition und Abschätzungen;251
11.3.2;Beispiel k(x,y)=log"026A30C x-y"026A30C ;253
11.3.3;Zusammenhang mit der Matrixfamilie Mk, ;254
11.4;Kreuzapproximation;257
11.4.1;Basisverfahren und theoretische Aussagen;257
11.4.2;Praktische Durchführung der Kreuzapproximation;258
11.4.3;Adaptive Kreuzapproximation;260
11.4.4;Erzeugung separabler Entwicklungen mittels Kreuzapproximation ;262
11.4.5;Die hybride Kreuzapproximation;264
11.5;Kriterien für Approximierbarkeit in H(k,P);265
11.6;Änderung der Matrizen bei Gitterverfeinerung;268
12;Anwendungen auf diskretisierte Integraloperatoren;270
12.1;Typische Integraloperatoren für elliptische Randwertaufgaben ;270
12.1.1;Randwertproblem und Fundamentallösung;271
12.1.2;Einfach-Schicht-Potential für das Dirichlet-Problem;271
12.1.3;Direkte Methode, Doppelschicht-Operator;272
12.1.4;Hypersingulärer Operator;273
12.1.5;Calderón-Projektion;273
12.2;Newton-Potential;274
12.3;Randelementdiskretisierung und Erzeugung der Systemmatrix in hierarchischer Form;274
12.4;Helmholtz-Gleichung für hohe Frequenzen;276
12.5;Allgemeine Fredholm-Integraloperatoren;277
12.6;Anwendungen auf Volterra-Integraloperatoren;277
12.6.1;Diskretisierungen von Volterra-Integraloperatoren;277
12.6.2;Implementierung als Standard-H-Matrix;279
12.6.3;Niedrigrangdarstellung von Profilmatrizen;280
12.6.4;Matrix-Vektor-Multiplikation;281
12.7;Faltungsintegrale;284
13;Anwendungen auf Finite-Element-Matrizen;286
13.1;Inverse der Massematrix;286
13.2;Der Green-Operator und seine Galerkin-Diskretisierung;290
13.2.1;Das elliptische Problem;290
13.2.2;Die Green-Funktion;291
13.2.3;Der Green-Operator G;291
13.2.4;Galerkin-Diskretisierung von G und der Zusammenhang mit A-1;292
13.2.5;Folgerungen aus separabler Approximation der Greenschen Funktion ;294
13.3;Analysis der Greenschen Funktion;298
13.3.1;L-harmonische Funktionen und innere Regularität;299
13.3.2;Approximation durch endlich-dimensionale Unterräume;301
13.3.3;Hauptresultat;303
13.3.4;Anwendung auf die Randelementmethode;308
13.3.5;FEM-BEM-Kopplung;309
14;Inversion mit partieller Auswertung;310
14.1;Baum der Gebietszerlegung und zugehörige Spurabbildungen;311
14.2;Diskrete Variante - Übersicht;313
14.3;Details;314
14.3.1;Finite-Element-Diskretisierung und Matrixformulierung;314
14.3.2;Zerlegung der Indexmenge;316
14.3.3;Die Abbildung ;317
14.3.4;Natürliche Randbedingung;317
14.3.5;Zusammenhang der Matrizen;318
14.3.6;Die Abbildung ;318
14.3.7;Konstruktion von aus 1 und 2;319
14.3.8;Konstruktion von aus 1 und 2;322
14.4;Basisalgorithmus;323
14.4.1;Definitionsphase;323
14.4.2;Auswertungsphase;324
14.4.3;Homogene Differentialgleichung;325
14.5;Verwendung hierarchischer Matrizen;325
14.6;Partielle Auswertung;327
14.6.1;Basisverfahren;328
14.6.2;Realisierung mit hierarchischen Matrizen;329
14.6.3;Vergröberung des Ansatzraumes für die rechte Seite;330
14.6.4;Berechnung von Funktionalen;330
15;Matrixfunktionen;332
15.1;Definitionen;332
15.1.1;Funktionserweiterung mittels Diagonalmatrizen;333
15.1.2;Potenzreihen;334
15.1.3;Cauchy-Integraldarstellung;335
15.1.4;Spezialfälle;336
15.2;Konstruktionen spezieller Funktionen;336
15.2.1;Approximation von Matrixfunktionen;336
15.2.2;Matrix-Exponentialfunktion;338
15.2.3;Inverse Funktion 1/z;343
15.2.4;Anwendung von Newton-artigen Verfahren;347
15.3;H-Matrix-Approximation;347
15.3.1;Matrix-Exponentialfunktion;347
15.3.2;Approximation nichtglatter Matrixfunktionen;347
16;Matrixgleichungen;348
16.1;Ljapunow- und Sylvester-Gleichung;349
16.1.1;Definition und Lösbarkeit;349
16.1.2;Andere Lösungsverfahren;350
16.2;Riccati-Gleichung;351
16.2.1;Definition und Eigenschaften;351
16.2.2;Lösung mittels der Signumfunktion;352
16.3;Newton-artige Verfahren zur Lösung nichtlinearer Matrixgleichungen;353
16.3.1;Beispiel der Quadratwurzel einer Matrix;353
16.3.2;Einfluss der Kürzung bei Fixpunktiterationen;354
17;Tensorprodukte;357
17.1;Tensor-Vektorraum;357
17.1.1;Notationen;357
17.1.2;Hilbert-Raum-Struktur;359
17.1.3;Datenkomplexität;359
17.2;Approximation im Tensorraum;359
17.2.1;k-Term-Darstellung;359
17.2.2;k-Term-Approximation;360
17.2.3;Darstellung mit Tensorprodukten von Unterräumen;361
17.3;Kronecker-Produkte von Matrizen;361
17.3.1;Definitionen;361
17.3.2;Anwendung auf die Exponentialfunktion;363
17.3.3;Hierarchische Kronecker-Tensorproduktdarstellung;364
17.4;Der Fall d=2;364
17.4.1;Tensoren;364
17.4.2;Kronecker-Matrixprodukte;366
17.4.3;Komplexitätsbetrachtungen;367
17.4.4;HKT-Darstellung;368
17.5;Der Fall d>2;369
17.5.1;Spezielle Eigenschaften;369
17.5.2;Inverse eines separablen Differentialoperators;371
18;Graphen und Bäume;373
18.1;Graphen;373
18.2;Bäume;374
18.3;Teilbäume;376
18.4;Bäume zu Mengenzerlegungen;377
19;Polynome;380
19.1;Multiindizes;380
19.1.1;Notation;380
19.1.2;Formelsammlung;380
19.2;Polynomapproximation;381
19.3;Polynominterpolation;383
19.3.1;Eindimensionale Interpolation;383
19.3.2;Tensorprodukt-Interpolation;386
20;Lineare Algebra, Funktionalanalysis, Singulärwertzerlegung ;388
20.1;Matrixnormen;388
20.2;Singulärwertzerlegung von Matrizen;390
20.3;Hilbert-Räume, L2-Operatoren;394
20.4;Singulärwertzerlegung kompakter Operatoren;396
20.4.1;Singulärwertzerlegung;396
20.4.2;Hilbert-Schmidt-Operatoren;398
20.5;Abbildungen zu Galerkin-Unterräumen;400
20.5.1;Orthogonale Projektion;400
20.5.2;Unterraumbasis, Prolongation, Restriktion, Massematrix;400
20.5.3;Norm ;402
20.5.4;Bilinearformen, Diskretisierung;405
21;Sinc-Interpolation und -Quadratur;408
21.1;Elementare Funktionen;408
21.2;Interpolation;409
21.2.1;Definitionen;409
21.2.2;Stabilität der Sinc-Interpolation;410
21.2.3;Abschätzungen im Streifen Dd;411
21.2.4;Abschätzungen durch e-CN/logN;414
21.2.5;Approximation der Ableitung;416
21.2.6;Meromorphes f;416
21.2.7;Andere Singularitäten;417
21.3;Separable Sinc-Entwicklungen;417
21.3.1;Direkte Interpolation;417
21.3.2;Transformation und Skalierung;418
21.3.3;Eine spezielle Transformation;420
21.3.4;Beispiel 1/(x+y);421
21.3.5;Beispiel log(x+y);425
21.4;Sinc-Quadratur;426
21.4.1;Quadraturverfahren und Analyse;426
21.4.2;Separable Entwicklungen mittels Quadratur;428
21.4.3;Beispiel: Integrand exp(-rt);429
21.4.4;Beispiel: Integrand exp(-r2t2);433
22;Asymptotisch glatte Funktionen;435
22.1;Beispiel | x-y| -a;435
22.1.1;Richtungsableitungen;435
22.1.2;Gemischte Ableitungen;439
22.1.3;Analytizität;440
22.2;Asymptotische Glattheit weiterer Funktionen;441
22.3;Allgemeine Eigenschaften asymptotisch glatter Funktionen;443
22.3.1;Hilfsabschätzungen;444
22.3.2;Abschätzung für Richtungsableitungen;445
22.3.3;Aussagen für beschränkte Gebiete;446
22.3.4;Produkte asymptotisch glatter Funktionen;447
23;Literaturverzeichnis;451
24;Notationen;459
25;Sachverzeichnis;463