Separation der Fundamentallösungen elliptischer Differentialgleichungen mit Hilfe von Quadraturverfahren
Final Report Abstract
Die Kombination der Greenschen Formel mit einem geeigneten Quadraturverfahren führt erwartungsgemäß zu einem neuen analytischen Approximationsverfahren für Kernfunktionen. Wir konnten beweisen, dass die Approximationen exponentiell konvergieren: Der erste Beweis beruht auf der Leibniz-Formel für höhere Ableitungen, der zweite auf einer polynomiellen Approximation des Integranden. Numerische Experimente zeigen, dass für zweidimensionale Gebiete die Quadratur-Methode nicht nur mit der erwarteten Rate konvergiert, sondern auch weniger Zeit und Speicher benötigt als beispielsweise der klassischen Ansatz über Tensor-Interpolation. Für dreidimensionale Gebiete erwies sich die Quadratur-Methode als nicht konkurrenzfähig, da die Anzahl der Quadraturpunkte sehr hoch ist, und damit auch der Rang der resultierenden Approximationen. Deshalb haben wir ein hybrides Verfahren entwickelt, das den Speicherbedarf und die Rechenzeit erheblich reduziert. Dabei machen wir uns zunutze, dass die Quadratur-Methode eine Approximation der Form G|t×s ≈ Wt BTts konstruiert, deren erster Faktor nur von den Zeilenindizes t abhängt. Mit Hilfe eines Kreuzapproximationsalgorithmus’ konstruieren wir aus Wt eine Indexmenge ιt ⊆ t und eine Matrix Vt, die einen algebraischen Interpolationsoperator zu den in ιt enthaltenen Interpolationspunkten und den durch die Spalten der Matrix Vt gegebenen Lagrange-Funktionen definieren. Die Approximation G|t×s ≈ Vt G|ιt ×s lässt sich dann wesentlich schneller berechnen und benötigt erheblich weniger Speicher als das Ergebnis der ursprünglichen Quadratur-Methode. Um die Effizienz des Verfahrens weiter zu verbessern wenden wir diesen Ansatz auch auf die Spaltenindizes s an und erhalten eine Approximation der Form G|t×s ≈ Vt G|ιt ×ιs VsT, bei der für jede Teilmatrix nur noch die sehr kleine Matrix G|ιt ×ιs gespeichert werden muss. Indem wir Vt und Vs durch geschachtelte Basen ersetzen, erhalten wir eine H2-Matrix-Approximation, die deutlich weniger Speicher als konkurrierende Verfahren benötigt und sich schnell konstruieren lässt. Es überrascht, dass diese Approximation bis zu einer gewissen Genauigkeit sehr schnell konvergiert und dann deutlich an Geschwindigkeit verliert. Die Ursachen dieses Verhaltens sind zur Zeit unklar, sollen aber weiter untersucht werden. Es besteht die Hoffnung, dass der Bereich der schnellen Konvergenz mit dem Diskretisierungsfehler Schritt hält, wenn wir die Diskretisierung verfeinern, so dass in der Praxis immer in diesem Bereich gearbeitet wird und das Verfahren die optimale Effizienz erreicht. Auch in seiner derzeitigen Form zählt die hybride H2-Quadratur-Methode allerdings schon zu den effizientesten Verfahren für die Approximation von Randintegralmatrizen. Infolge der für H2-Matrix-Techniken typischen linearen Komplexität eignet sie sich besonders gut für sehr große Matrizen.
Publications
- Low-rank approximation of integral operators by using the Green formula and quadrature, Numerical Algorithms, online Januar 2013
S. Börm, J. Gördes
(See online at https://doi.org/10.1007/s11075-012-9679-2) - Approximation of integral operators by Green quadrature and nested cross Approximation. Numerische Mathematik, Vol. 133. 2016, Issue 3, pp 409–442.
Steffen Börm, Sven Christophersen
(See online at https://doi.org/10.1007/s00211-015-0757-y)
