http://www.dagstuhl.de/06021

### January 8 – 13 , 2006, Dagstuhl Seminar 06021

# Reliable Implementation of Real Number Algorithms: Theory and Practice

## Organizers

Peter Hertling (Universität der Bundeswehr – München, DE)

Christoph M. Hoffmann (Purdue University – West Lafayette, US)

Wolfram Luther (Universität Duisburg-Essen, DE)

Nathalie Revol (ENS – Lyon, FR)

## For support, please contact

## Documents

Dagstuhl Seminar Proceedings

List of Participants

Dagstuhl's Impact: Documents available

External Homepage

## Summary

Real numbers are objects containing an infinite amount of information. Therefore, they cannot be represented precisely in a computer. This leads to well known problems caused by unverified finite precision implementations of real number algorithms. There are several scientific communities, not only in mathematics but also in computer science, that are concerned with reliable real number algorithms.

There are several scientific communities, not only in mathematics but also in computer science, that are concerned with reliable real number algorithms. Computable analysis is a fast growing subdiscipline of theoretical computer science that analyses real number computation problems in the context of the Turing machine model. Another theoretical approach is domain theory. Here one of the goals is to lay foundations for a programming language for exact real arithmetic. There are many approaches that deal with the reliable implementation of real number algorithms from a practical point of view. The basic idea of interval arithmetic, to start with, is to compute with intervals that are known to contain the real number in question. It is striking that the space of intervals is a special case of a domain. Other, in many cases related approaches are Taylor models, high precision software, exact arithmetic, algorithms using result verification, symbolic representations of part of the data, algebraic computation schemes, perturbation schemes, and many more. These approaches are being applied in order to solve numerical as well as geometric problems. In computational geometry the special problem of implementing real number algorithms reliably is complicated by the interplay of numerical predicates and hidden dependencies between them that arise from geometry theorems that may not be known. This creates opportunities for inconsistent decisions that lead to faulty data structures and, ultimately, to failure of the computation.

It was the goal of the seminar to bring together people who are dealing with the reliable implementation of real number algorithms either from a theoretical or from a practical point of view and to stimulate an exchange of ideas between the different communities that will bring an advance for the reliable solution of numerical and geometric problems. Some particular goals of the seminar were:

- to point out the most urgent current practical problems in the implementation of real number algorithms, to analyze them using the tools and notions from topology, computability theory and complexity theory, and hopefully to understand them better and make progress towards a solution,
- to explore the practical aspects of the computability and complexity notions for various types of continuous objects, based on various topologies and the resulting types of information and of representation methods that are used in order to describe the objects in an approximating way,
- to analyze and compare the various software tools for reliable implementation of real number algorithms, to analyze and compare their advantages and limits, and to explore the need and the possibilities to develop further software tools specially suited for developing and implementing reliable algorithms over the real numbers,
- to integrate reliable functions and algorithms into computer algebra systems as well as recent modeling and simulation software.

## The Seminar

Forty eight researchers from many different disciplines attended the seminar: people concerned with constructive mathematics or logic, with computability theory or complexity theory over the real numbers, with interval arithmetic, with robustness problems in computational geometry or solid modeling, with computer arithmetic, and with software for fast, arbitrarily high precision computations. The program consisted of 35 talks of 30 minutes each, and of three evening sessions with additional presentations and discussions. Many presentations showed that there are already strong interconnections between various disciplines. There were also lively discussions about different theoretical models and practical approaches for reliable real number computations.

## Topics of the Seminar

- Constructive Mathematics and Computability Theory over the Real Numbers
- Complexity Theory over the Real Numbers and Software for Fast, Arbitrarily High Precision Computation
- Computational Geometry and Solid Modeling, Robustness Problems
- Interval Arithmetic and Software Systems for Reliable Computations
- to integrate reliable functions and algorithms into computer algebra systems as well as recent modeling and simulation software.
- Floating Point Arithmetic, Verification of Software

## Classification

- Interdisciplinary
- Data Structures / Algorithms / Complexity
- Modelling Simulation
- Reliable Numerical Computation
- Geometric Modelling
- Computability

## Keywords

- Real number computability
- Real number algorithms
- Reliable computing
- Algorithms with result verification
- Interval arithmetic
- Taylor arithmetic
- Geometric computing
- Robustness