Wrapping-Darstellungen in Exakter Reeller Arithmetik (WERA)

• Antragsteller: Professor Dr. Norbert Müller
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2016 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 321126787

Exakte reelle Arithmetik ist die Implementierung der von Alan Turing begründeten und wesentlich von Klaus Weihrauch beeinflussten 'berechenbaren Analysis', der Berechenbarkeitstheorie auf überabzählbaren Mengen. Für den Bereich der reellen Zahlen und Funktionen nutzt diese Theorie Intervall-Arithmetik auf Fließkommazahlen mit Mantissen variabler Länge und stellt Zahlen als konvergierende Folgen von Intervallen dar. Intervall-Arithmetik leidet jedoch unter dem Einhüllungs- oder 'Wrapping'-Effekt, der bei längeren Berechnungen die Resultate unbrauchbar werden lässt. Um diesem Effekt gegenzuwirken, werden in der Numerik Taylor-Modelle eingesetzt, die multivariate Polynome an Stelle einfacher Intervalle nutzen. Zwei Veröffentlichungen durch den Antragsteller aus dem vergangenen Jahr über eine prototypische Implementierung zeigen, dass die Verwendung dieser Taylor-Modelle auch in der berechenbaren Analysis ein vielversprechender Ansatz ist. Zahlen werden dabei durch Folgen dieser Taylor-Modelle dargestellt, wobei in der exakten reellen Arithmetik die Effizienz von Algorithmen durch die verbesserte Kontrolle des Wrapping-Effekts sogar deutlich steigt. Diese Vorarbeiten sollen nun fortgesetzt und dabei die vorgestellten 'Wrapping-Darstellungen' genauer untersucht werden, die erstmals in der berechenbaren Analysis das Prinzip der Einhüllung reeller Mengen durch Taylor-Modelle verwenden bzw. verallgemeinern. Im Projekt geht es dabei konkret (1) um den praktischen Einsatz dieser Darstellungen in der exakten reellen Arithmetik, (2) um Modifikationen des Konzeptes, z.B. durch Verwendung anderer Strukturen an Stelle multivariater Polynome, und(3) um Übertragbarkeit des Konzeptes, z.B. auf weitere metrische oder Hausdorff-Räume.Die Untersuchungen werden dabei sowohl (a) aus Sicht einer asymptotischen Komplexitätstheorie als auch (b) aus Sicht des Algorithm Engineering mit konkreten Implementierungen erfolgen.Für die Beschreibung der Eigenschaften der Darstellungen wird eine tragfähige Definition von Komplexitätsschranken entwickelt, bei denen simultan das asymptotische Verhalten der Rechenzeit beschrieben und präzise Aussagen über die Güte von Einhüllungen getroffen werden. Durch konkrete Implementierungen können auch Effizienzbereiche untersucht werden, die praktisch relevant aber asymptotisch schwer fassbar sind. Ein Zusatznutzen dieser Implementierungen wird Interoperabilität zwischen existierenden Ansätzen für exakte reelle Arithmetik sein.Als Testbeispiele dienen iterierte Funktionensysteme und Differentialgleichungen, also zeitdiskrete bzw. zeitkontinuierliche dynamische Systeme, die vielfältige Anwendungen etwa in Mathematik, Physik oder Biologie haben. Die Untersuchung der zeitkontinuierlichen Systeme beinhaltet die Betrachtung formaler Transformationen auf Potenzreihen und bilden eine Basis für die Anwendung auf dem Gebiet der komplexen Analysis.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Japan, Russische Föderation, Süd-Korea
• Kooperationspartnerinnen / Kooperationspartner: Dr. Akitoshi Kawamura, Ph.D.; Dr. Margarita Korovina; Professor Dr. Martin Ziegler