New types of adaptivity for the cross approximation of non-local operators
Final Report Abstract
Während des Projekts wurden zwei neue Verfahren entwickelt. Die erste Methode ist eine effiziente Generierung von Matrixapproximationen, welche auf die rechte Seite zugeschnitten ist. Dadurch wurde eine anerkannte Methodik auf Problemstellungen erweitert, für die sie bisher nicht sinnvoll anwendbar war. Zudem konnte eine adaptive Form der Matrix-Vektor Multiplikation ausgearbeitet werden, mit der eine Steigerung der Effizienz erzielt werden konnte. Bei beiden neu entstandenen Verfahren mussten block-basierte bzw. blockzeilen-basierte Fehlerschätzer entwickelt und analysiert werden. Beim blockzeilen-basierten Fehlerschätzer für die adaptive Matrix-Vektor Multiplikation konnte eine vollständige Theorie, d.h. Zuverlässigkeit, Effizienz, Fehlerschätzerreduktionsprinzip und Konvergenz des Fehlerschätzers, gezeigt werden. Mit Hilfe der Konvergenz des Fehlerschätzers und dessen Zuverlässigkeit wurde auch die Konvergenz der neuen adaptiven Matrix-Vektor Multiplikation gezeigt. Für den neuen Zugang zur Matrixapproximation konnte bis auf die Effizienz des block-basierten Fehlerschätzers eine ähnliche Theorie aufgebaut werden. Das neue Verfahren wurde zusätzlich mit der Kombination aus Approximation und Lösung des zugrundeliegenden Gleichungssystems Ax = b weiter verbessert, d.h. es wurde ein Verfahren entwickelt, welches eine Sequenz aus Matrixapproximationen und Lösungen der Probleme mit approximierter Matrix berechnet. Am Ende der Iteration erhält man die Lösung von Ax = b für eine vorgegebene Genauigkeit. In jedem Iterationsschritt kann der Lösungsvektor des vorherigen Schritts als Startvektor des verwendeten iterativen Lösers dienen. Beide neuen Verfahren arbeiteten in den numerische Experimenten bezüglich des Speicherbedarfs und der Rechenzeit besser als die adaptive Kreuzapproximation, welche einen universellen Approximant berechnet. Die genauen Zahlen können dem beigefügten Artikel entnommen werden. Da die neuen Verfahren auf die rechten Seiten zugeschnitten sind, liefern sie umso bessere Ergebnisse desto größer die strukturellen Unterschiede in der rechten Seite sind. Eine weitere Neuerung bei dieser Art von Matrixapproximation ist, dass qualitativ schlechtere Gitter, wie z.B. Gitter mit teilweise zu stark aufgelösten Regionen, an Bedeutung verlieren. Der neue Algorithmus kann die partiell zu stark verfeinerten Gebiete erkennen und stellt je nach Beschaffenheit der rechten Seite fest wie sie in der Systemmatrix aufgelöst werden müssen. Somit kann wertvolle Rechenzeit und wertvoller Speicherplatz gespart werden. Als Überraschungen im Projektverlauf sind zwei Punkte zu nennen. Zum einen wurde nicht erwartet, dass die Analyse der Effizienz des block-basierten Fehlerschätzers im Fall des neuen Zugangs zur Matrixapproximation so komplex und schwierig ist. Ein Grund hierfür könnte die Art des zugrundeliegenden Problems sein, welches eher einem inversen Problem entspricht. Zum anderen waren einige Ergebnisse in den numerischen Tests nicht in diesem Ausmaß zu erwarten. Der neue Algorithmus kann bei partiell bzw. komplett zu stark verfeinerten Gittern eingesetzt werden, um diese zu detektieren, was zur Folge hat, dass die zu diesen Gebieten gehörenden Matrixblöcke nicht komplett berechnet bzw. nicht so gut approximiert werden müssen wie der universelle Approximant approximiert ist. Gravierend konnte dies auch im verwendeten Löser festgestellt werden. In den numerischen Tests mit den partiell zu stark verfeinerten Gebieten konnte die Rechenzeit mehr als halbiert werden.
Publications
- Block-Adaptive Cross Approximation of Discrete Integral Operators, Computational Methods in Applied Mathematics, De Gruyter online: 05.02.2020
M. Bauer, M. Bebendorf
(See online at https://doi.org/10.1515/cmam-2019-0085)
