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

Dagstuhl Service Team

Documents

Dagstuhl Seminar Proceedings DROPS
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

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.