Wrapping Representations in Exact Real Arithmetic (WERA)

精确实数算术是“可计算分析”的实现版本，它是不可数集合上的可计算性理论。这一理论是由艾伦·图灵首创的，并在很大程度上受到了克劳斯·魏劳赫的影响。对于实数和函数，该理论对尾数任意长的浮点数使用区间算术。在这里，数字被表示为区间的收敛序列。然而，区间算术受到“包络效应”的影响。长时间的计算往往只会产生无用的结果。为了抵消这种影响，数值分析使用了泰勒模型，其中使用了多元多项式而不是简单的区间。申请人去年发表的两篇论文涉及泰勒模型在精确实数运算中的原型实现。它们表明，这些模型在可计算分析中也是一种很有前途的方法。数字现在由这些模型的序列表示，这在精确的实数运算中通过改进对包装效果的控制来提高效率。我们将继续这项研究并深入研究新引入的‘包裹表示’，它在可计算分析中首次使用并推广了受泰勒模型启发的实数集包裹的原理。更准确地说，该项目涉及(1)在精确实数运算中应用这些表示的效果，(2)对概念的修改，例如用其他结构取代多元多项式，以及(3)概念的推广，例如，进一步的度量或Hausdorff空间。我们的研究将集中在(A)计算复杂性的方面以及(B)通过使用算法的具体实现来实现算法工程的方面。为了描述表示的性质，我们将提出一个有用的复杂性界限的定义，它同时描述计算时间的渐近行为，以及包含关于包装质量的精确信息。具体的实现将允许分析实际相关但逐渐难以跟踪的效率领域。此外，现有的精确实数运算方法之间的互操作性有望通过具体的实现来实现。离散时间和实时动力系统(如迭代函数系统和微分方程)将是核心例子，在数学、物理或生物学中有许多应用。对连续时间系统的处理将包含对形式变换的研究，并将为复杂分析的应用奠定基础。

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.