Multiskalen- und Wavelet-Matrixkompression Analysisbasierte Methoden zur effizienten Lösung großer vollbesetzter Gleichungssysteme

Wir betrachten eine Methode zur effizienten numerischen Lösung einiger li- nearer Operatorgleichungen, dies können sowohl Integral-, als auch Differen- tialoperatoren sein. Zu diesem Zweck schlagen wir eine Wavelet-oder Multi- skalendarstellung vor. Wir zeigen, daß unter gewissen Voraussetzungen an die Basen und die Operatoren die auftretenden Matrizen gleichmäßig konditio- niert und numerisch dünn besetzt sind. Wir zeigen, daß man diese Matrizen durch clünn besetzte ersetzen kann, um damit das entstehende Gleichungssy- stem mit optimalem Aufwand O(N) oder zumindest fastoptimalen Aufwand 0( N log N) zu lösen, ohne die bestmögliche Konvergenzrate des zugrunde- liegenden Verfahrens, in der Regel Galerkin-oder Kollokationsverfahren, zu verletzen. Chemnitz, im Januar 1998 R. Schneider Inhaltsverzeichnis 1 Einleitung 7 1.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Ziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Beispiele von Problemen die zu großen voll besetzten Matrizen führen 11 1.4 Phasenraumlokalisierung und Multiresolutionsanalyse 13 1.5 Inhaltsübersicht . . . . . . . . . . . . . . . . . . . . . 17 2 Grundlegende Definitionen 21 3 Pseudodifferentialoperatoren auf glatten Mannigfaltigkeiten 25 4 Einige praktische Beispiele 35 4.1 Operatoren der Ordnung Null . . . . . . . . . . . . . . . . . . . 35 . . . . . 4.2 Stark Elliptische Randintegralgleichungen der Ordnung Null . . . . . . 36 . 4.3 Operatoren beliebiger Ordnung r: j; 0 und Integralgleichungen erster Art 44 5 Multiskalenbasen 53 5.1 Ziele ..... . 53 .5.2 Multiskalen-Transformationen ...... . 62 5.3 Multiskalenbasen auf periodischem Gitter . 80 .5.4 Lokale Konstruktion für Mannigfaltigkeiten. 81 5.4.1 Multiwavelets ............ . 81 5.4.2 Multiskalenräume stetiger Funktionen . 89 5.5 Momentenbedingung . . . . . 94 5.6 Beispiele ........... . 97 5. 7 Der Unterteilungsalgorithmus 101 5.8 Interpolationsbasen ..... . 109 6 Approximationsverhalten und Normcharakterisierung 113 6.1 Approximation und Regularität ..