Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation
maximize


Abschlußbericht des Projekts Nr. 2 innerhalb des DFG-Paketantrags

"Mehrgitteralgorithmen für unsymmetrische und heterogene Probleme"



Thema: Multilevelmethoden für nichtsymmetrische Probleme als Iterationsverfahren über Erzeugendensystemen
Mitwirkende: Michael Griebel, Frank Kiefer
Berichtszeitraum: 01.08.1998 - 01.04.2001

1. Arbeits- und Ergebnisbericht:



1.1. Problemstellung und Ziele:

Modellhaft betrachteten wir in diesem Projekt das folgende stationäre Konvektions-Diffusions Problem mit homogenen Dirichletschen Randbedingungen auf dem Einheitsquadrat

\begin{displaymath}
Tu :=-\Delta u+\vec{b}\cdot\nabla u=f\,\,\mbox{\rm in }\Omeg...
...^2\quad
\mbox{\rm und}\quad u=0\,\,\mbox{ auf }\partial\Omega.
\end{displaymath} (1)

Das Konvektionsfeld $\vec{b}=(b_1(x,y),b_2(x,y))$ ist hierbei im allgemeinen ortsabhängig und die zugehörige ${\cal L}^{\infty}(\Omega)$-Norm kann sehr große Werte annehmen. Die Lösung der nach Diskretisierung von (1) - zum Beispiel durch ein Petrov-Galerkin Finite-Elemente Verfahren mit Feingitter Ansatz- und Testräumen ${\cal V}_0$ und ${\cal S}_0$ - entstehenden schwachbesetzten unsymmetrischen linearen Gleichungssysteme
\begin{displaymath}
T_0u_0=f_0,
\end{displaymath} (2)

erfolgt heute zumeist mit Hilfe von Iterationsverfahren (z.B. Jacobi- und Gauß-Seidel-Verfahren, SOR, aber auch moderne Krylovraum-Methoden, etwa GMRES oder BICGSTAB, zusammen mit einfachen Vorkonditionierern). Diese nähern sich ausgehend von einer Startapproximation schrittweise der diskreten Lösung [29,43]. Iterationsverfahren haben gegenüber direkten Lösungsverfahren wie der Gauß-Elimination den Vorteil, daß sie nur einen geringen Rechenaufwand pro Iteration benötigen. Außerdem lassen sie sich ohne großen zusätzlichen Speicheraufwand implementieren. Man trifft dabei in der Regel aber auf die folgenden beiden Schwierigkeiten. Die Konvergenz der Verfahren Diese Problematik bezeichnet man auch als die Frage nach der Robustheit der Verfahren [52]. Der ersten Schwierigkeit begegnet man im Fall des ungestörten Poissonproblems (1) mit $\vec{b}\equiv\mathbf{0}$ durch Multilevel-Methoden ( Mehrgitter-Verfahren, Multilevel-Vorkonditionierer) [11,26,28]. Sie führen im Idealfall zu Konvergenzraten, die nicht mehr von der Maschenweite $h_0$ des Gitters abhängen, das zur Diskretisierung benutzt wurde [35]. Man kann sagen, daß die Entwicklung von Multilevel-Methoden für symmetrisch positiv definite elliptische Randwertaufgaben abgesehen von auch hier sich möglicherweise stellenden Robustheitsfragen mit den Arbeiten [27,53] einen Zustand finaler Reife erreicht hat. Dies gilt auch aus theoretischer Sicht. Ganz anders verhält es sich im Fall unsymmetrischer Probleme wie der Konvektions-Diffusions Gleichung (1). Robuste Multilevel-Verfahren, die also zusätzlich die zweite oben genannte Schwierigkeit beheben, sind im allgemeinen nur sehr schwer zu konstruieren, wie die Erfahrung lehrt. Es existieren zwar einige in der Praxis recht erfolgreiche Ansätze [19,21,24,31,33,38,55], wirkliche Robustheitsbeweise liegen bislang aber fast nur für (triviale) eindimensionale Probleme vor.

Ziel des Projekts war es, ausgehend von einem Erzeugendensystem-Ansatz [25,26] und dem sich darüber ergebenden Verständnis von Multilevel-Verfahren robuste Multilevel-Löser für allgemeine Konvektions-Diffusions Probleme zu entwickeln.



1.2. Durchgeführte Arbeiten:


1.2.1. Konstruktion von Petrov-Galerkin Multiskalen-Verfahren:

Im Fall des ungestörten Poissonproblems bieten neben klassischen Multilevel-Verfahren auch Wavelet-Ansätze eine geeignete Möglichkeit, die Maschenweitenabhängigkeit iterativer Löser zu überwinden. Wavelet-Methoden zur Lösung elliptischer partieller Differentialgleichungen liegt eine spezielle Multiskalen-Basis des Lösungsraums zugrunde. Man nutzt dabei eine geschickte Multiskalen-artige direkte Zerlegung des Lösungsraums in Unterräume, die von den Dilaten und Translaten einer einzigen Funktion, nämlich dem Wavelet, aufgespannt werden. Mit entsprechenden schnellen Algorithmen können die Lösungen dann in Bestandteile, die zu unterschiedlichen Skalen gehören, aufgespalten werden, was insbesondere nützlich zur Entwicklung von Fehlerschätzern und adaptiven Verfahren ist [15]. Für symmetrisch positiv definite elliptische Randwertprobleme erhält man ausgehend von Wavelet-Zerlegungen mit Algorithmen, die den bekannten Multilevel-Methoden nachempfunden sind, Multiskalen-Verfahren, die ebenfalls zu gitterweitenunabhängigen Konvergenzraten führen [9,16,30,50,51]. Wavelet-basierte Multiskalen-Löser, die für allgemeine Konvektions-Diffusions Probleme robuste Methoden liefern, sind bislang jedoch nicht bekannt.

In [22,23] wird eine schnelle Wavelet-basierte LU-Faktorisierung als direkter Löser für lineare Gleichungssysteme vorgestellt, die durch Diskretisierung von Integralgleichungen mit $N_0$ Freiheitsgraden entstehen. Das Bestimmen der Lösung solcher Gleichungssysteme ist dabei bis auf eine Genauigkeit $\varepsilon$ mit ${\cal O}(N_0)$ Aufwand möglich. Das Verfahren basiert auf der Nichtstandardform des Operators, die im Rahmen eines Wavelet-basierten Erzeugendensystem-Ansatzes entsteht, und eignet sich ebenfalls zur Lösung linearer Gleichungssysteme, die von Diskretisierungen elliptischer partieller Differentialgleichungen herrühren. Etwas abweichend vom ursprünglichen Konzept konzentrierte sich unser Interesse bald auf die Konstruktion robuster Nichtstandardform-basierter Multiskalen-Löser für das diskrete Konvektions-Diffusions Problem (2). Dazu mußte das Nichtstandardform-Konzept aus [22,23], das sich auf ${\cal L}^2$-orthogonale Multiskalen-Zerlegungen innerhalb eines periodisierten Settings stützt, auf den Kontext allgemeiner Petrov-Galerkin Multiskalen-Zerlegungen unter Berücksichtigung von Randbedingungen erweitert werden. Weiterhin sollte die Beziehung des zur Nichtstandardform gehörenden Erzeugendensystem-Ansatzes zu dem Ansatz aus [25,26] und damit das Verhältnis zwischen Wavelet- und klassischen Multilevel-Methoden zur Lösung von (2) geklärt werden.


1.2.1.1. Standard-, Nichtstandardform und Multiskalen-Erzeugendensysteme:

Interessiert man sich für Petrov-Galerkin Multiskalen-Verfahren zur effizienten Lösung des Systems (2), so ist zunächst zu untersuchen, wie sich solche linearen Gleichungssysteme unter den allgemeinen Multiskalen-Zerlegungen der Tiefe $lt$

\begin{displaymath}
{\cal V}_0=\bigoplus_{k=1}^{lt}{\cal W}_{k}\oplus{\cal V}_{l...
...{\cal S}_0=\bigoplus_{k=1}^{lt}{\cal F}_{k}\oplus{\cal S}_{lt}
\end{displaymath} (3)

im Rahmen eines Petrov-Galerkin Ansatzes transformieren. Es wird dabei vorausgesetzt, daß die Zerlegungen (3) rekursiv für $k=1,...,lt$ über Zweiskalen-Zerlegungen ${\cal V}_{k-1}={\cal W}_{k}\oplus{\cal V}_{k}$ und ${\cal S}_{k-1}={\cal F}_{k}\oplus{\cal S}_{k}$ der Räume ${\cal V}_{k-1}$ und ${\cal S}_{k-1}$ in Unterräume mit Detail- und grobskaligen Anteilen entstehen. Eine natürliche Darstellung von (2) relativ zu den Zerlegungen (3) wird durch die zugehörigen Basiswechsel induziert. Man erhält als Systemmatrix des entsprechend transformierten linearen Gleichungssystems die sogenannte Standardform $\tilde{T}_{0,s}$ von $T_0$ [10]. Will man Multiskalen-Verfahren konstruieren, die auf wesentlich mehr Information über den transformierten Operator zugreifen als nur seine (Block-) Diagonale, so ist die Standardform $\tilde{T}_{0,s}$ schon wegen der Anzahl ihrer nichtverschwindenden Einträge keine adäquate Darstellung mehr. Sie besitzt nämlich eine $(lt+1)\times(lt+1)$ Blockstruktur, deren einzelne Blöcke die gegenseitigen Kopplungen der an den Zerlegungen beteiligten Unterräume durch den Operator beschreiben. Aufgrund der sich so ergebenden (Multi-),,Fingerstruktur`` von $\tilde{T}_{0,s}$ ist klar, daß die Standardform im Falle uniformer Gitterverfeinerung im allgemeinen wenigstens ${\cal O}(N_0(lt+1))$ signifikante Einträge besitzt. Alleine das Aufstellen der Standardform bewirkt, daß ein damit gebildetes Multiskalen-Verfahren nicht mehr mit linearer Komplexität, also mit einem Aufwand proportional zur Anzahl der Feingitterunbekannten, durchgeführt werden kann. Eine interessante Frage ist daher, ob es für diskrete Operatoren $T_0$ mit einem Besetzungsmuster mit ${\cal O}(N_0)$ Einträgen möglich ist, eine Multiskalen-Darstellung mit ebenfalls nur ${\cal O}(N_0)$ Einträgen zu finden.

In [10] wurde im Zusammenhang mit der Entwicklung schneller Algorithmen für allgemeine Caldéron-Zygmund Operatoren die sogenannte Nichtstandardform eingeführt, die beispielsweise für Integraloperatoren nach Kompression ${\cal O}(N_0)$-Algorithmen zur schnellen Lösung der zugehörigen Integralgleichungen ermöglicht. Mit ihrer Hilfe läßt sich eine positive Antwort auf die oben gestellte Frage finden. Die Kernidee zur Konstruktion der Nichtstandardform $\tilde{T}_{0,ns}$ des diskreten Feingitteroperators $T_0$ bezüglich der Multiskalen-Zerlegungen (3) besteht darin, rekursiv nur die Grobgitteroperator-Blöcke $T_k$ weiter zu zerlegen, die bei den Transformationen hinsichtlich einfacher Zerlegungen entstehen. Mit Hilfe der Nichtstandardform lassen sich dann effiziente Algorithmen im betrachteten Multiskalen-Kontext formulieren [10,22,23], die äquivalent zu entsprechenden mittels der Standardform gebildeten Verfahren sind. Hierauf wird näher in 1.2.1.2. eingegangen.



Standardform (links) und Nichtstandardform (rechts) eines diskreten Operators in 1D (3-Punkte Stern)



Standardform (links) und Nichtstandardform (rechts) eines diskreten Operators in 2D (5-Punkte Stern)

Wir untersuchten schließlich die wichtige Frage nach den Beziehungen zwischen Wavelet- und klassischen Multilevel-Methoden zur Lösung von (2). In diesem Zusammenhang konnten wir zeigen, daß die zur Standardform gehörenden Multiskalen-Transformationen jeweils auch als Produkte von Erzeugendensystem-Transformationen mit geeigneten Blockdiagonalmatrizen darstellbar sind. Die Erzeugendensystem-Transformationen gehen dabei aus einer Multilevel-nodalen Darstellung hervor, die zu der nichtklassischen Mehrgitter-Sichtweise aus [25,26] führt. Dies erlaubt es, die von uns betrachteten Multiskalen-Methoden auch auf der Basis der in [25,26] vorgestellten Erzeugendensysteme zu interpretieren. Ferner konnten wir zeigen, daß es möglich ist, die Standard- und Nichtstandardform eines Operators sowie auch seine klassische Erzeugendensystem-Darstellung in eine allgemeinere Multiskalen-Erzeugendensystem-Darstellung einzubetten.



Schematische Darstellung der Petrov-Galerkin Multiskalen-Erzeugendensystem-Darstellung (oben links), der darin enthaltenen Multilevel-Erzeugendensystemdarstellung (oben rechts, grau unterlegt), der Standardform (unten links, grau unterlegt) und der Nichtstandardform (unten rechts, grau unterlegt) im Fall lt=2


1.2.1.2. Iterative Verfahren für Multiskalen-transformierte Gleichungssysteme:

Gemäß der Aufgabenstellung 3.1.2. des Fortsetzungsantrags (``Anwendung traditioneller Iterationsverfahren auf die modifizierten erweiterten Systeme'') wendeten wir uns dann im Detail der Untersuchung iterativer Verfahren für die sich ergebenden Multiskalen-transformierten linearen Gleichungssysteme zu. Wir betrachteten dazu zuerst in recht allgemeiner Weise additive Matrixsplittings der Standard- und Nichtstandardform des diskreten Operators $T_0$ und untersuchten, unter welchen Bedingungen darüber definierte Iterationsverfahren im Standard- und Nichtstandardsystem einander äquivalent sind. In diesem Zusammenhang konnte gezeigt werden, wie sich solche Iterationen auch aus Sicht von Multilevel-Erzeugendensystemen, das heißt auf der Basis klassischer Multilevel-Verfahren darstellen lassen. Sowohl additive (BPX-artige) als auch multiplikative (Mehrgitter-artige) Wavelet-Löser können mit Hilfe einer Multiskalen-Korrektur bzw. -Glättung, die wesentlich von den für die Unterraumzerlegungen verwendeten Multiskalen-Basen abhängt, als spezielle Multilevel-Methoden aufgefaßt werden.

Danach entwickelten wir zwei zunächst unterschiedlich erscheinende multiplikative Multiskalen-Verfahren. Das erste Verfahren basiert auf einer approximativen Faktorisierung der Nichtstandardform $\tilde{T}_{0,ns}$ von $T_0$, die äquivalent zu einer entsprechenden approximativen Faktorisierung der Standardform $\tilde{T}_{0,s}$ ist. Man gelangt so zu einer approximativen Multiskalen-Inversen $M_{0,ns}^{-1}$ von $T_0$, die sich effizienter berechnen läßt als die dazu äquivalente über die Standardform definierte approximative Multiskalen-Inverse $M_{0,s}^{-1}$. Es kann $M_{0,ns}^{-1}$ beispielsweise innerhalb einer linearen Iteration der Form
\begin{displaymath}
x_0^{i+1}=x_0^i+M_{0,ns}^{-1}(f_0-T_0x_0^i),\quad (i=0,1,2,...),
\end{displaymath} (4)

oder auch als Multiskalen-Vorkonditionierer für Krylovraum-Verfahren eingesetzt werden. Die Iteration (4) läßt sich zudem als Block-Gauß-Seidel Verfahren im Nichtstandardsystem interpretieren, das äquivalent zu einem entsprechenden Block-Gauß-Seidel Verfahren für das Standardsystem ist. Die zweite Technik beruht auf dem sukzessiven approximativen Lösen der Teilgleichungen für die Detail- und grobskaligen Komponenten des auf Nichtstandardform transformierten Systems, wobei die vorhergehenden Korrekturen jeweils in die darauffolgenden einfließen. Das Verfahren gehört damit zur Klasse der multiplikativen Unterraumkorrektur-Methoden [53]. Es kann auch als eine Verallgemeinerung der klassischen Hierarchischen Basis Mehrgitter-Methode (HBMG) angesehen [6,8] und mittels der oben erwähnten Multiskalen-Glättungsiterationen sogar als spezielles Mehrgitter-Verfahren interpretiert werden. Beide von uns betrachteten Verfahren sind bei jeweils exakter Invertierung der Blöcke $A_k$ ($k=1,...,lt$), die die gegenseitigen Kopplungen der hochfrequenten Anteile innerhalb von $\tilde{T}_{0,ns}$ beschreiben, äquivalent. Bei lediglich approximativer Invertierung dieser Blöcke ist die zweite Technik der ersten überlegen, da hierbei in den Nachkorrekturschritten modifizierte Residuen gebildet werden, die genau zu den zu lösenden Teilproblemen passen. Wir konnten zeigen, daß eine effiziente Implementierung beider Verfahren auch ohne das vollständige Aufstellen der Nichtstandardform möglich ist. Neben den Zweiskalen-Transformationen für die Ansatz- und Testseite werden dazu im Fall einer lediglich approximativen Invertierung der Blöcke $A_k$ nur deren approximative Inversen $\breve{A}_k^{-1}$ und die jeweiligen Grobgitteroperatoren $T_k$ bezüglich der verschiedenen Skalen sowie der Feingitteroperator $T_0$ benötigt.

Darüberhinaus untersuchten wir Modifikationen der Grundversionen der beiden multiplikativen Multiskalen-Algorithmen. Wir konstruierten verbesserte Varianten, die genauere Schur-Komplement-Approximationen zur Bestimmung der im Verlauf der Verfahren zu berechnenden verallgemeinerten hierarchischen Residuen verwenden. Diese Varianten sind unseres Wissens neu und bislang nicht in der Literatur bekannt. Dabei verglichen wir unsere Verfahren im Detail mit drei verwandten Ansätze aus der Literatur. Es sind dies die in [22,23] vorgeschlagene schnelle Wavelet-basierte LU-Faktorisierung, die Multilevel-Vorkonditionierung mittels AMLI (AMLI = Algebraic MultiLevel Iteration) gemäß [1,2] sowie die Methode der Approximativen Zyklischen Reduktion [39,40] (siehe auch 2.3.). Der in [23] vorgestellte Löser, der einen Ausgangspunkt für unsere Überlegungen darstellt, wird in [22,23] lediglich für eindimensionale ungestörte Probleme getestet. Die Frage, ob man damit zu robusten Lösern für zweidimensionale Konvektions-Diffusions Probleme gelangt, wurde im Rahmen einer Diplomarbeit, die im Verlauf des Projekts entstand, genauer untersucht und negativ beantwortet [44]. Die erfolgreiche Implementierung des Verfahrens für den weitaus aufwendiger zu programmiernden höherdimensionalen Fall kann hier dennoch als Erfolg gewertet werden.

Die vorgestellten Verfahren wurden im Rahmen eines Computerprogramms unter ANSI C implementiert. Durch die Anbindung einer bestehenden Bibliothek linearer Löser (PETSc) [3,4,5] war es auf einfache Weise möglich, unterschiedliche Verfahren zur (approximativen) Invertierung der $A_k$ auszutesten (klassische Iterationsverfahren sowie gängige Krylovraum-Löser (z.B. BICGSTAB, GMRES, QMR, TFQMR) zusammen mit einfachen Vorkonditionierern). Es zeigte sich, daß insbesondere unvollständige Faktorisierungen der Blöcke $A_k$ (ILU($0$)) zu guten und verläßlichen Ergebnissen führen, vorausgesetzt man verwendet problemangepaßte Petrov-Galerkin Multiskalen-Zerlegungen.


1.2.2. Problemangepaßte Petrov-Galerkin Multiskalen-Zerlegungen:

Es ist klar, daß die Robustheit der entwickelten Verfahren wesentlich von den Multiskalen-Transformationen abhängt, die implizit die Zerlegungen (3) festlegen. Um robuste Multiskalen-Verfahren für Konvektions-Diffusions Probleme zu erhalten, sollte daher die Wahl der zugehörigen Transformationsmatrizen $P^{k}_{k+1,{\cal V}\slash{\cal S}}$ und $Q^{k}_{k+1,{\cal V}\slash{\cal S}}$ zwischen den Skalen $k$ und $k+1$ problemangepaßt erfolgen. Hierbei kennzeichnet der untere Index $_{{\cal V}}$ die Transformationen für die Ansatzseite, der Index $_{{\cal S}}$ diejenigen für die Testseite und mit $_{{\cal V}\slash{\cal S}}$ werden diese gleichzeitig angesprochen. Die problemangepaßte Wahl dieser Transformationen unterscheidet unseren Ansatz wesentlich von den Wavelet-basierten Methoden [13,14,23,36,37,41].


1.2.2.1. Geometrische Multiskalen-Zerlegungen:


a) Problemangepaßte Wahl der Grobgitterräume:

Ausgehend von einer Standardvergröberung der zugrundeliegenden Gitter untersuchten wir zunächst die problemabhängige Wahl der Prolongationen $P^{k}_{k+1,{\cal V}\slash{\cal S}}$, die dazu dient, physikalisch sinnvolle Grobgitterprobleme im Verlauf der rekursiven Zerlegung aufzustellen. Problemabhängige Prolongationen $P^{k}_{k+1,{\cal V}\slash{\cal S}}$ können über eine durch den Operator induzierte Interpolation berechnet werden, die auf der Lösung lokaler homogener kontinuierlicher Probleme beruht und mittels operatorabhängiger Finite-Elemente Basen ($L$-Splines) interpretiert werden kann. Wir konnten zeigen, daß diese lokalen Greenschen Funktionen für allgemeine eindimensionale und separable zweidimensionale Probleme ( $\vec{b}=(b_1(x),b_2(y)$) verallgemeinerte Skalierungsgleichungen erfüllen, was den Zusammenhang mit einer Multiskalen-Analyse herstellt [34]. Mit Hilfe der über $L$-Splines berechneten Steifigkeitsmatrix kann dann eine äquivalente matrixabhängige Prolongation durch die Lösung entsprechender lokaler homogener diskreter Probleme bestimmt werden. Letzteres entspricht gerade einer lokalen Gauß-Elimination und ist für Probleme mit variablen Koeffizientenfunktionen der einzig gangbare Weg zur Bestimmung einer solchen problemabhängigen Prolongation, da die Lösung der lokalen homogenen kontinuierlichen Probleme im allgemeinen viel zu aufwendig ist. Die Konstruktion matrixabhängiger Prolongationen für zweidimensionale separable Probleme erfolgte über einen Tensorpodukt-Ansatz durch Reduktion auf eindimensionale gemittelte Probleme.

Zur Bestimmung einer matrixabhängigen Prologation im allgemeinen Fall nichtseparabler Konvektion $\vec{b}=(b_1(x,y),b_2(x,y))$ verwendeten wir anstelle der gemittelten die ursprünglichen Operatorsterne. Die damit berechneten Eckgewichte der lokalen Prolongationssterne tragen dann ebenfalls zur lokalen Gauß-Elimination bei. Eine verallgemeinerte lokale Skalierungsgleichung ist hier aber nicht mehr erfüllt und man gelangt insbesondere zu nichtkonformen Grobgitterräumen. Darüberhinaus existieren verfeinerte Techniken von de Zeeuw, die zur Definition matrixabhängiger Prolongationen die Aufspaltung der lokalen Operatorsterne in ihren symmetrischen und schiefsymmetrischen Anteil verwenden [54,55]. Sie wurden von uns ebenfalls implementiert und getestet.


b) Problemangepaßte Wahl der Basen der Komplementräume:

Die Frage der Wahl geeigneter Basen der Komplementräume ${\cal W}_{k+1}$ und ${\cal F}_{k+1}$ auf der Ansatz- und Testseite ist ebenfalls von großer Bedeutung für die Robustheit von Multiskalen-Verfahren. Sie ist gleichbedeutend mit der Auswahl geeigneter Matrizen $Q_{k+1,{\cal V}\slash{\cal S}}^{k}$, deren Spalten angeben, wie sich Basisfunktionen der jeweiligen Komplementräume mittels Basisfunktionen der zugehörigen Feingitterräume darstellen lassen. Es wurde von uns hier lediglich gefordert, daß die Matrizen $Q_{k+1,{\cal V}\slash{\cal S}}^{k}$ die bisher bestimmten Prolongationsmatrizen $P_{k+1,{\cal V}\slash{\cal S}}^{k}$ zu Basiswechseln der Form $W_{k+1,{\cal V}\slash{\cal S}}^{k}=[Q_{k+1,{\cal V}\slash{\cal S}}^{k},P_{k+1,{\cal V}\slash{\cal S}}^{k}]$ ergänzen. Die einfachste Möglichkeit für die Wahl einer Basis von ${\cal F}_{k+1}$ auf der Testseite besteht aus den in den Fein-ohne-Grobgitterpunkten verankerten Feingitterfunktionen, was mit Hilfe des trivialen in den Fein-ohne-Grobgitterpunkten aufsitzenden Moleküls $(Q_{k+1,{\cal S}}^{k})_{*}=[\quad 1\quad]$ realisiert werden kann ( hierarchische Wahl).



Klassische (links) und mittels L-Splines gebildete einfache eindimensionale hierarchische Zerlegung bzgl. des Einheitsintervalls


Für eindimensionale Probleme sieht man, daß bei matrixabhängiger Wahl der Prolongation $P_{k+1,{\cal V}}^k$ auf der Testseite und hierarchischer Wahl der komplementären Prolongation $Q_{k+1,{\cal S}}^k$ für die Ansatzseite die Einträge im Block $B_{k+1}=(Q_{k+1,{\cal S}}^{k})^t T_k
P_{k+1,{\cal V}}^{k}$ der Zweiskalen-transformierten Steifigkeitsmatrix $\tilde{T}_k=(W_{k+1,{\cal S}}^{k})^t T_k W_{k+1,{\cal V}}^{k}$ verschwinden. Durch ein Dualitätsargument findet man, daß bei matrixabhängiger Wahl von $P_{k+1,{\cal S}}^k$ (nun aber abhängig vom adjungierten Problem!) und hierarchischer Wahl von $Q_{k+1,{\cal S}}^k$ ebenfalls die Einträge im Block $C_{k+1}=(P_{k+1,{\cal S}}^{k})^t T_k
Q_{k+1,{\cal V}}^{k}$ Null sind. Dies entspricht also einer vollständigen Entkopplung des matrixabhängig hierarchisch transformierten Systems. Aufgrund der hierarchischen Wahl der Basen von ${\cal W}_{k+1}$ und ${\cal F}_{k+1}$ ist $A_{k+1}=(Q_{k+1,{\cal S}}^{k})^t T_k Q_{k+1,{\cal V}}^{k}$ diagonal. Da der Grobgitteroperator $T_{k+1}=(P_{k+1,{\cal S}}^{k})^t T_k P_{k+1,{\cal V}}^{k}$ wieder durch einen 3-Punkte Stern gegeben ist, kann die matrixabhängige Bestimmung der Prolongationsmatrizen in Bezug auf die Ansatz- und Testräume rekursiv fortgesetzt werden. Die Standardform $\tilde{T}_{0,s}$ des Feingitteroperators $T_0$ zu den so erhaltenen problemabhängigen Multiskalen-Zerlegungen der Ansatz- und Testräume ${\cal V}_0$ und ${\cal S}_0$ ist damit diagonal und das transformierte System kann trivial gelöst werden. Für die Nichtstandardform $\tilde{T}_{0,ns}$ ergibt sich entsprechend, daß sämtliche Nebendiagonalblöcke verschwinden. Beide Implementierungen des additiven Verfahrens (mittels Standard- und Nichtstandardsystem) entarten hier also zu einem direkten Löser.

Verwendet man für höherdimensionale Konvektions-Diffusions Probleme die von uns berechneten matrixabhängigen Prolongationen zusammen mit einer hierarchischen Wahl der Komplementbasen, so ist die Block-Gauß-Elimination nur noch unvollständig. In höheren Raumdimensionen besitzen außerdem die über die hierarchische Wahl gebildeten Zerlegungen nicht mehr die gleichen optimalen Stabilitätseigenschaften wie im eindimensionalen Fall. Betrachtet man anstelle der hierarchischen Zerlegungen jedoch Wavelet-artige Zerlegungen, so zeigen die darüber gewonnenen Multiskalen-Zyklen optimale Konvergenzeigenschaften [50]. Dies liegt aus Sicht der Mehrgitter-Interpretation insbesondere an dem stärkeren Einfluß der zugehörigen Multiskalen-Glätter. Wir beschäftigten uns deshalb mit der Konstruktion Wavelet-artiger Basisfunktionen für die Komplementräume, wobei wir zunächst einen Tensorprodukt-Ansatzes ausgehend von eindimensionalen Wavelet-artigen Zerlegungen verfolgten. Aufgrund unseres allgemeinen Petrov-Galerkin Zugangs konnten wir somit Wavelet-artige Multiskalen-Zerlegungen auf der Ansatzseite mit hierarchischen Zerlegungen der Testseite einfach kombinieren. Dadurch ist es dann möglich, in einem multiplikativen Verfahren eine approximative Elimination beispielsweise der Grobgitterunbekannten aus den transformierten Feingittergleichungen unter verbesserten Stabilitäts- und Glättungseigenschaften zu erhalten. Explizit konstruierte lokale eindimensionale $L$-Spline Prewavelet-Filter waren innerhalb unseres Tensorprodukt-Ansatzes leider nicht erfolgreich. Dies liegt vermutlich an den schlechten Regularitätseigenschaften des Haar-Systems, das hierbei im Grenzfall entartender Konvektionsstärke $b\rightarrow\infty$ auftritt. Die Verwendung konstanter eindimensionaler Wavelet-artiger Filter führte jedoch bei separablen Problemen zu robusten Methoden wie unsere numerischen Experimente zeigen, etwa im Rahmen von Multiskalen W-Zyklen.



Klassische (links) und mittels L-Splines gebildete einfache eindimensionale Prewavelet-Zerlegung bzgl. des Einheitsintervalls


1.2.2.2. Algebraische Multiskalen-Zerlegungen:

Die im vorherigen Abschnitt aufgezeigten problemangepaßten Tensorprodukt-artigen Multiskalen-Zerlegungen sind über eine fest vorgegebene geometrische Vergröberung der zugrundeliegenden Gitter entstanden ( geometrische Multiskalen-Zerlegungen). Für Randwertprobleme in kompliziert berandeten Gebieten ist ein in diesem Sinne geometrisch orientiertes Multiskalen-Konzept, zumindest was einfache ungestörte Probleme betrifft, zwar immer noch möglich, es führt jedoch schon in diesen einfachen Fällen zu recht komplizierten Konstruktionen [17,20,32,45,46]. Eine Mehrgitter-Variante, die mit Erfolg Multilevel-Löser für nur schwer oder tatsächlich unzugängliche Geometrien konstruiert, ist die Klasse der Algebraischen Mehrgitter-Verfahren (AMG) [12,24,42,47]. Im Unterschied zu geometrischen Mehrgitter-Verfahren, bei denen die Folge der Grobgitterpunkte vorgegeben ist, werden bei AMG zunächst geeignete Grobgitterfreiheitsgrade ausgewählt, was mit Hilfe zweier reeller Parameter $\alpha$ und $\beta$ über die Konzepte starker und schwacher Kopplungen sowie algebraisch glatter Fehler geschieht. Durch diese Auswahl sind die Fein-ohne-Grobgitterfreiheitsgrade automatisch festgelegt. Danach werden zugehörige Prolongationen und Restriktionen problemabhängig berechnet. Sowohl für die Auswahl der entsprechenden Freiheitsgrade als auch für die Berechnung der Prolongationen und Restriktionen wird ausschließlich die Systemmatrix des zu lösenden Gleichungssystems benutzt. Die auf diese Weise algebraisch bestimmten Prolongationen und Restriktionen können dann innerhalb gewöhnlicher Mehrgitter-Löser eingesetzt werden.

Algebraische Mehrgitter-Verfahren haben sich insbesondere aber auch als sehr robuste Löser für Probleme mit kompliziert gearteten Koeffizientenfunktionen des Differentialoperators erwiesen, etwa bei der Behandlung von wirbelbehafteten Konvektions-Diffusions Problemen [24]. Aufgrund der einschränkenden Mehrgitter-Interpretation unserer Multiskalen-Zyklen erschien es aussichtslos, solch schwierige Probleme mit den bisherigen Tensorprodukt-Techniken erfolgreich angehen zu können. Sämtliche Versuche, etwa eine Kreisströmung auf der Basis geometrisch definierter Multiskalen-Zerlegungen und matrixabhängiger Multiskalen-Transformationen zu behandeln, führten zu nicht zufriedenstellenden Ergebnissen. Da das algebraische Mehrgitter-Konzept bewußt auf speziell definierte Glättungsprozeduren verzichtet, stellten wir uns die Frage, ob im Fall einer Kreisströmung mit Hilfe AMG-basierter Zerlegungen und Komponenten ein robuster Multiskalen-Löser gefunden werden kann, der auf direkten algebraischen Multiskalen-Zerlegungen beruht.


a) AMG-hierarchische Zerlegungen:

Eine naheliegende Unterraumzerlegung ist hier durch eine AMG-basierte hierarchische Basis Zerlegung gegeben. Dabei werden auf jedem Level nach Festlegen der Basen der nächstgrobskaligeren Räume, was mittels der AMG-Prolongationen geschieht, die zugehörigen Komplemente durch die bisherigen in den Fein-ohne-Grobgitterpunkten befindlichen Basisfunktionen aufgespannt. Für den gewöhnlichen Laplace-Operator ergeben sich mit AMG jedoch (approximativ) wieder geometrische Vergröberungen und bilineare Interpolationen. Deshalb war nicht zu erwarten, daß man mittels AMG-basierter hierarchischer Zerlegungen einen zumindest optimalen Multiskalen-Löser erhält. Mit einem AMG-hierarchischen W-Zyklus würde man ähnlich wie mit AMLI-Verfahren, die höhere Polynomgrade zwecks einer verbesserten Schur-Komplement-Approximation verwenden, zwar eine Stabilisierung des Lösers hinsichtlich seiner Gitterweitenabhängigkeit erreichen, für komplizierte Probleme kann ein solcher W-Zyklus aber sehr aufwendig sein. Dies liegt daran, daß die Zahl der ausgewählten Grobgitterfreiheitsgrade aufgrund der algebraischen Auswahl nicht notwendig mit einer geometrischen Rate abfällt. Ein entsprechender W-Zyklus ist dann im allgemeinen nicht mehr mit einem Aufwand von ${\cal O}(N_0)$ implementierbar, wenn $N_0$ die Dimension des Gleichungssystems ist. Man gelangt so zur Frage nach möglichen Wavelet-artigen Stabilisierungen AMG-basierter hierarchischer Basen.


b) AMGlet Zerlegungen:

Die Konstruktion AMG-basierter Prewavelets über eine explizite Orthogonalisierung jeweils relativ zum nächstgrobskaligeren Raum führt -- wenn überhaupt möglich -- zu äußerst komplizierten und unüberschaubaren Bestimmungsgleichungen für die jeweiligen Filterkoeffizienten. Ihr Erfolg ist zudem fraglich, wie unsere Erfahrung mit den explizit konstruierten $L$-Spline Prewavelets zeigt. Auch Lifting-Konstruktionen [48] leiden in unserem Fall unter ähnlichen Schwierigkeiten. Daher haben wir uns für eine wesentlich einfachere Möglichkeit entschieden, die sich auf die folgende elementare Beobachtung stützt.

Betrachtet man den trivialen Fall eindimensionaler Konvektions-Diffusions Probleme, so fällt auf, daß bei geometrischer Vergröberung und verschwindender Konvektion der 3-Punkte Operatorstern, also die zweite Ableitung mittels zentraler Differenzen, bis auf eine Skalierung mit dem Pre-Prewaveletfilter $[-1 \hspace{5mm} \underline{2} \hspace{1mm}-1]/2$ übereinstimmt. Im umgekehrten Grenzfall verschwindender Diffusion ist der einfache Upwind-Stern mit dem von uns berechneten $L$-Spline-Prewaveletfilter identisch. Wir konstruierten deshalb AMG-basierte Detailfilter als Baupläne von Basisfunktionen der Komplementräume über lokale Operatorsterne, die sich in den entsprechenden Fein-ohne-Grobgitterpunkten befinden. Die resultierenden in der Praxis stabilisierenden Basisfunktionen der Komplementräume bezeichnen wir als AMGlets. Im Verlauf des algebraischen Vergröberungsprozesses verbreitern sich bekanntlich zunehmend die über die Galerkin-Produkte $(P^k_{k+1,{\cal V}})^tT_kP^k_{k+1,{\cal V}}$ bestimmten Grobgitteroperator-Sterne. Die Träger der so konstruierten AMGlets vergrößern sich entsprechend. Dem Verbreitern der Grobgitteroperator-Sterne kann man entgegenwirken, indem man mittels eines Paramaters $\gamma_P$ die Zeilen der an dem Galerkin-Produkt beteiligten AMG-Prolongationen abschneidet und eine Reskalierung durchführt [47]. Ferner wurden von uns danach relativ zum betragsmäßig größten nichtzentralen Eintrag der resultierenden Operatorsterne die kleinsten Sterneinträge mit Hilfe eines weiteren Parameters $\gamma_Q$ abgeschnitten und zum zentralen Sterneintrag hinzuaddiert (``lumping''). Wir konstruierten damit die Matrizen $Q^k_{k+1,{\cal V}}$ über die abgeschnittenen Sterne $(Q^k_{k+1,(i,j),{\cal V}})_{*}=[(T_{k,(i,j)})_{*}]_{\gamma_Q}.$ Ein solches algebraisches Abschneiden entspricht genau der klassischen AMG-Philosophie und bewirkt anschaulich eine Konzentration und Lokalisierung der AMGlets. Die Kombination einer so bestimmten AMGlet-Zerlegung auf der Ansatzseite zusammen mit einer AMG-hierarchischen Zerlegung der Testseite führte im Rahmen eines Multiskalen V-Zyklus für ein wirbelbehaftetes Konvektions-Diffusions Problem zu einem Verfahren mit robusten Konvergenzraten.



Kreisströmung; linkes Bild: Veranschaulichung der ersten fünf groben Gitter, die durch AMG ausgewählt werden (gröbere Gitter entsprechen dickeren und dunkleren Punkten; rechtes Bild: zugehöriges AMGlet, erzeugt durch die Stabilisierung der AMG hierarchischen Zerlegung auf der Ansatzseite.



1.3. Diskussion der Ergebnisse:

Die von uns in diesem Projekt geleistete Arbeit kann als eine praktisch orientierte Antwort auf die Frage angesehen werden, inwieweit es möglich ist, robuste Multiskalen-Verfahren für Konvektions-Diffusions Probleme zu entwickeln, wenn man ausgeht von direkten Unterraumzerlegungen der zugrundeliegenden Funktionenräume. Dies kann als eine Konkretisierung der in [49] gestellten Aufgabe verstanden werden, die nach der Konstruktion effizienter Multiskalen-Löser für allgemeine elliptische Randwertprobleme auf der Basis direkter Unterraumzerlegungen fragt. Die in [49] vorgestellten Antworten sind nicht ohne weiteres erfolgreich auf singulär gestörte Probleme anwendbar sondern führen lediglich im ungestörten Fall wie etwa beim Poissonproblem (1) mit $\vec{b}\equiv\mathbf{0}$ zu Verfahren, die Gitterweiten-unabhängige Konvergenzeigenschaften ähnlich wie klassische Mehrgitter-Methoden aufweisen.

Auf dem Weg hin zu robusten Multiskalen-Methoden für Konvektions-Diffusions Probleme begegnet man den folgenden drei Hauptschwierigkeiten: Dementsprechend besteht die von uns gefundene Antwort aus drei Teilen. Als erstes ist die problemabhängige Wahl der Prolongationsoperatoren $P_{k+1,{\cal V}\slash{\cal S}}^k$ innerhalb unseres Petrov-Galerkin Multiskalen-Ansatzes unverzichtbar, um physikalisch sinnvolle Grobgitterprobleme zu erhalten. Wir verwendeten dazu entscheidend Techniken zur Konstruktion geeigneter Prolongationen, die bei robusten variationellen Mehrgitter-Verfahren eingesetzt werden. Hierbei konnten die von uns auf der Basis geometrischer Vergröberungen konstruierten problemangepaßten Prolongationen über ihre Interpretation mittels (Tensorprodukt) $L$-Splines in den Kontext verallgemeinerter Multiskalen-Analysen eingeordnet werden. Damit gelingt es, eine Brücke von der Welt der Mehrgitter- und Multilevel-Verfahren hin zu Wavelet-basierten Methoden zu schlagen. Dies zeigen nicht zuletzt auch unsere Untersuchungen der Standard- und Nichtstandardform von Operatoren sowie deren Einbettung in ein Multiskalen-Erzeugendensystem. Im Fall des herausfordernden Testbeispiels mit einem wirbelbehafteten Konvektionsfeld mußten wir sogar auf Prolongationstechniken zurückgreifen, die von algebraischen Mehrgitter-Verfahren herrühren. Es ist ebenfalls möglich, den Kontext variationeller Vergröberungen zu verlassen und stattdessen mit expliziten Diskretisierungen bezüglich gröberer Gitter zu arbeiten. Man erhält damit jedoch zumeist schlechtere numerische Ergebnisse, was von traditionellen Mehrgitter-Lösern her ebenfalls bekannt ist [28].

Betrachtet man hierarchische Zerlegungen der Feingitter Ansatz- und Testräume ${\cal V}_0$ und ${\cal S}_0$, so erscheint (für höherdimensionale Probleme) der Wechsel hin zu einer Wavelet-artigen Zerlegung auf einer der beiden Seiten notwendig für die Robustheit unserer Verfahren zu sein. Dies gilt sogar für ein im wesentlichen eindimensionales Testbeispiel mit achsenorientierter Konvektion. Zwar reichen hierarchische W-Zyklen aus, um für das Poissonproblem eine Stabilisierung eines hierarchischen Multiskalen-Lösers bezüglich seiner Gitterweitenabhängigkeit zu erreichen. Im Konvektions-Diffusions Fall erhält man dadurch jedoch keine Stabilisierung in Bezug auf die Konvektionsstärke $b$. Wavelet-artige Multiskalen-Zerlegungen besitzen für das Poissonproblem und einen Galerkin-Ansatz optimale Stabilitätseigenschaften hinsichtlich der Abhängigkeit der Konvergenzeigenschaften resultierender Multiskalen-Löser von $h_0$. Diese Stabilitätseigenschaften manifestieren sich in einer Normäquivalenz zwischen der zugehörigen Energienorm und einer gewichteten Multiskalennorm, bei der die Konstanten unabhängig von $h_0$ sind. Dies führt zu optimalen additiven und multiplikativen Multiskalen-Verfahren. Unsere Experimente zeigen, daß für multiplikative Multiskalen-Verfahren basierend auf unterschiedlichen Zerlegungen der Ansatz- und Testseite, eine Wavelet-artige Zerlegung auf einer der beiden Seiten für solche optimalen Löser sogar ausreicht. Aus Sicht der Mehrgitter-Interpretation unserer Multiskalen-Zyklen ist die im Vergleich zu rein hierarchischen Glättern verbesserte Glättungsarbeit auf den einzelnen Skalen dafür verantwortlich.

Der dritte Grund für den Erfolg der von uns vorgeschlagenen Verfahren, ist die Kombination der hierarchischen Zerlegung auf der Testseite mit einer problemangepaßten Vergröberung auf der Ansatzseite. Dies ist für eindimensionale Probleme äquivalent zu einer Entkopplung des transformierten linearen Gleichungssystems. Für höherdimensionale Probleme ist diese Entkopplung nur noch approximativ möglich. Sie scheint dennoch wesentlich für das Erhalten erfolgreicher Verfahren zu sein, wie weitere numerische Experimente zeigen.

Durch das von uns verwendete Petrov-Galerkin Multiskalen-Konzept ist es möglich, alle soeben aufgelisteten Ideen, die eng miteinander verzahnt sind, zu vereinigen. Dies verdeutlicht auch die folgende Abbildung.

Unser Ansatz geht damit weit über die uns bekannten Verfahren, die auf direkten Unterraumzerlegungen beruhen hinaus, wie der ausführlicher Vergleich etwa mit den Methoden aus [1,2,22,23,39,40] verdeutlicht. Die in [22,23] als direkter Multiskalen-Löser vorgeschlagene Wavelet-basierte LU-Faktorisierung scheitert in Bezug auf singulär gestörte Konvektions-Diffusions Probleme, da sie keine problemangepaßten Multiskalen-Zerlegungen verwendet [44]. Viele andere Wavelet-Methoden zur Lösung von partiellen Differentialgleichungen leiden unter der gleichen Schwierigkeit [13,14,23,36,37,41]. Dies trifft auch auf die Vorkonditionierung mittels AMLI zu, die zudem lediglich von hierarchischen Multiskalen-Zerlegungen ausgeht und daher eine W-Zyklus-artige Stabilisierung hinsichtlich $h_0$ durch innere Rekursionen benötigt. Die verallgemeinerte Hierarchische Basis Mehrgitter-Methode [7], die auf der Verwendung problemangepaßter Prolongationen $P_{k+1,{\cal V}\slash{\cal S}}^k$ zusammen mit zugehörigen hierarchischen Zerlegungen beruht, leidet spürbar unter der mehrfach herausgestellten prinzipiellen Schwäche hierarchischer Glätter, was die Ergebnisse in [33] auch belegen. Das gilt ebenfalls für die Arbeit [18], die einen adaptiven Mehrgitter-Löser auf der Basis verallgemeinerter hierarchischer Basis Transformationen vorstellt. Obwohl die Methode der Approximativen Zyklischen Reduktion problemangepaßte hierarchische Multiskalen-Zerlegungen auf der Basis algebraischer Vergröberungen verwendet und damit gute Voraussetzungen für ein robustes Verfahren erfüllt, scheinen die durch sie gewonnenen Verfahren noch mit einer Gitterweitenabhängigkeit behaftet zu sein. Mit den von uns entwickelten AMGlet-Zerlegungen, die ebenfalls auf rein algebraischen Prinzipien beruhen, gelingt es, auf einfache Weise hier Abhilfe zu schaffen. Es ist darüberhinaus damit möglich, die für separable Probleme erfolgreichen Tensorprodukt-Ansätze zu verlassen, um schwierige nichtseparable Aufgaben in unter Umständen kompliziert berandeten Gebieten behandeln zu können. Dies eröffnet den Übergang von Modellproblemen hin zu praxisnahen Fragestellungen.

Wegen der unterschiedlichen Wechselwirkungen der drei Hauptbausteine unseres Konzepts -- problemangepaßte Vergröberung, Wavelet-artige Testraumzerlegung und hierarchische Ansatzraumzerlegung -- sowie der prinzipiellen Schwäche zugehöriger Multiskalen-Glätter, ist es unserer Erfahrung nach ungleich schwieriger, robuste Multiskalen-Verfahren zu konstruieren als etwa mittels spezieller Mehrgitter-Techniken. Durch unseren Ansatz ist es unseres Wissens allerdings erstmalig gelungen, robuste Multiskalen-Methoden für allgemeine Konvektions-Diffusions Probleme auf der Basis direkter Unterraumzerlegungen zu konzipieren und in die Praxis umzusetzen.



2. Zusammenfassung:

In diesem Projekt wurden erstmalig über einen zur Nichtstandardform gehörenden Erzeugendensystemansatz robuste Wavelet-basierte Multiskalen-Löser für allgemeine stationäre Konvektions-Diffusions Probleme entworfen und praktisch umgesetzt.

Für Methoden, die lediglich direkte Unterraumzerlegungen verwenden, ist es im allgemeinen nicht mehr möglich, Multiskalen-Glätter zu konstruieren, die im Grenzfall sehr starker Konvektion auf jeder Skala zu einem direkten Löser entarten. Als eine Möglichkeit zur Konstruktion robuster Multiskalen-Verfahren bleibt die Wahl der Multiskalen-Zerlegungen selbst. Es ist sicherzustellen, daß man sowohl hinsichtlich der singulären Störung stabile Grobgitterprobleme als auch bezüglich der Maschenweite stabile Unterraumzerlegungen erhält. Gleichzeitig muß der Aspekt der approximativen Gauß-Elimination beachtet werden, der durch das Zusammenspiel matrixabhängiger Prolongationen und Restriktionen mit einer hierarchischen Basis Zerlegung gegeben ist.

Um alle diese Forderungen zu erfüllen, wurde zunächst ausgehend von geometrischen Vergröberungen ein allgemeines Petrov-Galerkin Multiskalen-Konzept entwickelt, bei dem die Zerlegungen auf der Ansatz- und Testseite unterschiedlich sind. Es wurden matrixabhängige Prolongationen, die von robusten Mehrgitter-Techniken her bekannt sind, verwendet, zusammen mit Wavelet-artigen und hierarchischen Multiskalen-Zerlegungen der Ansatz- und Testräume bezüglich des feinsten Gitters. Die Kernidee bei den vorgeschlagenen Verfahren ist, jeweils einen der Komplementräume auf der Ansatz- oder Testseite hierarchisch zu wählen, um zusammen mit einer problemabhängigen Vergröberung auf der anderen Seite physikalisch sinnvolle Grobgitterdiskretisierungen und gleichzeitig einen approximativen Eliminationseffekt zu erreichen. Die Komplementräume auf der entsprechend anderen Seite werden hingegen Wavelet-artig aufgespannt, was zu einer Stabilisierung des Verfahrens bezüglich der Abhängigkeit von der Maschenweite der Diskretisierung führt. Mit den weiterhin entwickelten AMGlet-Zerlegungen, die auf rein algebraischen Prinzipien beruhen, gelingt es, geometrisch orientierte Tensorprodukt-Konstruktionen, die für separable Probleme erfolgreich sind, zu durchbrechen. Dies eröffnet darüberhinaus auch den Übergang von Modellproblemen hin zu praxisnahen Fragestellungen.

Unterschiedliche numerische Beispiele zeigen, daß man durch die vorgeschlagenen Konstruktionen zu verallgemeinerten Hierarchische Basis Mehrgitter-Verfahren mit robusten Konvergenzeigenschaften gelangt.

Publikationen aus dem Projekt:




Frank Kiefer
2001-10-24