WP2 — Exact Computation in real analysis

In this investigation the connection between computability and important areas of applied mathematics such as dynamical systems, stochastic processes as well as differential equations will be explored. Moreover, the problem of algorithmic efficiency and computer realisations will be considered.

Research objectives.

(I) to determine which long term (asymptotic) properties of a dynamical system can be computed, at least in theory, and in a more refined manner, which ones can be computed given reasonable amount of resources such as time or memory;

(II) to study in how much the theory of Kolmogorov complexity and algorithmic randomness applied to Brownian motion and other stochastic processes may help in understanding the complexity of computational problems over such processes;

(III) to measure the computational hardness of problems such as root finding or solving differential equations;

(IV) to improve and extend existing software packages in ERA.


Objective 2-I: Dynamical systems are a very versatile mathematical tool for modelling natural phenomena and have large number of applications, also in the undertaking of this proposal. However, this versatility comes with a cost: dynamical systems are very hard to analyse in general. For that reason, the last decades have seen an increasing use of computers in the study and analysis of dynamical systems, which has resulted in a number of theoretical breakthroughs; for example, the discovery and proof of existence of the Lorenz attractor.

Since dynamical systems are subject to phenomena such as the sensitive dependence on initial conditions or, more broadly, to chaos, the use of standard numerical simulations may not always provide correct information, especially when it concerns the long-term evolution of the system. Thus, it becomes highly desirable to understand rigorously which asymptotic properties of a dynamical system can be (theoretically) computed by Turing-machine-based models of computation such as TTE and whether it is possible to devise algorithms which can be implemented in practise to compute those properties. More precisely, we are interested in the computation of attractors, basins of attraction, and the statistical properties of dynamical systems. Project participants have already a proven track-record of analysing such problems. We will continue this line of research. In particular, the computability of the Lorenz attractor and its physical measure will be analysed.

It is well known that parameterised families of dynamical systems can exhibit “exceptional” behaviour for some isolated parameter values that is not representative of their usual dynamical behaviour. In dynamical systems theory most of the theory focuses on what happens on a typical (from a statistical perspective) dynamical system. For example, it is known that typical dynamical systems on compact 2-dimensional spaces are structurally stable. We will investigate if the semi-computability of attractors obtained for the general case still applies if only structurally stable systems are considered, or if instead full computability of attractors can be obtained. We expect the latter to be true.

Summary of this research objective: (a) investigate the computability of attractors, basins of attraction, the statistical properties of dynamical systems, as well as any other related properties;

(b) study the question whether the semi-computability of attractors true for the general case still applies if only structurally stable systems are considered, or whether instead full computability of attractors can be obtained.

Objective 2-II: The study of stochastic processes is an important subfield of applied mathematics. Brownian motion, for example, is used in finance, in biochemistry, and the fractal analysis of medical imaging, to mention only a few. We are interested in the computational aspects of such processes.

Summary of this research objective: (a) study the local time of Brownian motion via a computable analytic understanding of stochastic integration;

(b) investigate Gaussian processes from the viewpoint of effective DST and internal set theory;

(c) study Tsirelson’s theory of countably dense sets of reals from the viewpoint of computable probability theory and explore the links with de Finetti’s exchangeability theorem.

Objective 2-III: In general, mere computability statements do not include information about practical efficiency; information about the computational complexity of the problem is needed in addition. Computational complexity theory, as presented in text books, takes into consideration quantitative aspects of algorithmic costs such as run time or memory consumption, but this is limited to the discrete realm. Several project participants contributed to the development of a theory of bit-complexity over continuous universes where algorithmic costs are measured in dependence on the desired output precision. This research will be continued. The results will allow us to predict the practical performance of rigorous numerical methods, and choosing the most promising ones for actual implementation.

In general, complexity statements describe worst-case behaviour. Solving smooth ordinary differential equations, e.g., has been proven hard. Many examples, though, do admit efficient solutions. In the COMPUTAL project it was discovered that better complexity information for concrete cases could be obtained if complexity measures are made to depend additionally on certain characteristic input parameters.

It is already known that maximising a (smooth) univariate real function corresponds to NP, one-dimensional Riemann integration to #P, solving Lipschitz ordinary differential equations to PSPACE, and root finding to P. The goal is to devise similar characterisations for other complexity classes.

Summary of this research objective: (a) study the parameterised complexity of solving differential equations (ordinary as well as partial), real root finding, and functional maximisers;

(b) characterise common complexity classes in terms of real problems.

Objective 2-IV: ERA implementations under active development and maintained by participants of the planned interaction are AERN (Konečný, written in Haskell), ARIADNE (Collins, written in C++), iRRAM (Müller, written in C++), and Marshall (Bauer, written in OCaml). We will extend and improve these software packages as well as increase their interoperability. Enhancement of formal verifiability will be an important issue in this undertaking. This will be done in interaction with WP3 — Logical representation of data. The extensions will include complex arithmetic as well as implementations of various data types for function spaces.

Almost all problems in applied mathematics deal with spaces of real-valued functions on Euclidean domains in their formulation and solution, representing dependencies on parameters, time- and space-dependent solutions, or distributions of random variables. There are many function spaces in use, each appropriate for particular problem classes. Every such space may have several abstract interpretations and concrete representations: continuous functions may be defined by interval extensions or by completions in the uniform norm, and may be represented symbolically, by polynomials or splines, and in various bases. We will specify abstract data types for various function spaces, and develop miscellaneous concrete symbolic and numeric implementations of these spaces which may then be combined interchangeably. The abstractions developed will facilitate passing functions as first-class objects from one computational process to another, which has the potential to be a powerful tool in creating integrated computational work-flows.

Summary of this research objective: (a) extend and improve the software packages AERN, ARIADNE, iRRAM and Marshal as well as increase their interoperability;

(b) specify abstract data types for various function spaces, and develop miscellaneous concrete symbolic and numeric implementations of these spaces which may then be combined interchangeably.