Wrapping Representations in Exact Real Arithmetic (WERA)

• Applicant: Professor Dr. Norbert Müller
• Subject Area: Theoretical Computer Science
• Term: from 2016 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 321126787

Exact real arithmetic is an implemented version of 'computable analysis' being the theory of computability on uncountable sets. This theory was originated by Alan Turing and largely influenced by Klaus Weihrauch. For real numbers and functions this theory uses interval arithmetic on floating point numbers with arbitrarily long mantissas. Here numbers are represented as converging sequences of intervals.Interval arithmetic, however, suffers from the 'wrapping effect'. Long computations tend to deliver only useless results. To counteract this effect, numerical analysis uses Taylor models, where multivariate polynomials are used instead of simple intervals.Two publications by the applicant from last year concern a prototypical implementation of Taylor models in exact real arithmetic. They show that these models are also a promising approach in computable analysis. Numbers are now represented by sequences of such models, which in exact real arithmetic lead to increased efficiency using the improved control of the wrapping effect. We will continue this research and thoroughly investigate the newly introduced 'wrapping representations', which for the first time in computable analysis use and generalize the principle of wrapping sets of real numbers inspired by Taylor models.More precisely, the project deals with (1) the effects of applying these representations in exact real arithmetic,(2) modifications of the concept, for example replacing multivariate polynomials the by other structures, and(3) generalizations of the concept, for example to further metric or Hausdorff spaces.Our research will concentrate on (a) aspects of computational complexity as well as on(b) aspects of algorithm engineering by using concrete implementations of algorithms.To describe the properties of the representations we will develop a useful definition of complexity bounds that simultaneously describe the asymptotic behavior of computation times and as well contain precise information about the quality of wrappings. Concrete implementations will allow to analyze areas of efficiency that are practically relevant but asymptotically hard to track. Additionally, interoperability between existing approaches for exact real arithmetic is expected to be gained by concrete implementations.Discrete-time and real-time dynamical systems (like iterated function systems and differential equations) will be the core examples, having many applications in mathematics, physics, or biology. The treatment of the continuous time systems will contain research on formal transformations with power series and will be a base for applications on complex analysis.

• DFG Programme: Research Grants
• International Connection: Japan, Russia, South Korea
• Cooperation Partners: Dr. Akitoshi Kawamura, Ph.D.; Dr. Margarita Korovina; Professor Dr. Martin Ziegler