TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 06021

Reliable Implementation of Real Number Algorithms: Theory and Practice

( Jan 08 – Jan 13, 2006 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/06021

Organizers





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

Participants
  • Götz Alefeld (KIT - Karlsruher Institut für Technologie, DE)
  • Ekaterina Auer (Universität Duisburg-Essen, DE)
  • Andrej Bauer (University of Ljubljana, SI) [dblp]
  • Jens Blanck (Swansea University, GB) [dblp]
  • Sylvie Boldo (University of Paris South XI, FR) [dblp]
  • Vasco Brattka (University of Cape Town, ZA) [dblp]
  • Jean-Marie Chesneaux (UPMC - Paris, FR)
  • George F. Corliss (Marquette University - Milwaukee, US) [dblp]
  • Eva Dyllong (Universität Duisburg-Essen, DE)
  • Eric Goubault (CEA - Gif sur Yvette, FR) [dblp]
  • Peter Hertling (Universität der Bundeswehr - München, DE) [dblp]
  • Ralph Baker Kearfott (Univ. of Louisiana - Lafayette, US)
  • Sebastian Kempken (Universität Duisburg-Essen, DE)
  • Margarita Korovina (A. P. Ershov Institute - Novosibirsk, RU) [dblp]
  • Vladik Kreinovich (University of Texas - El Paso, US) [dblp]
  • Branimir Lambov (Aarhus University, DK)
  • Philippe Langlois (Université de Perpignan, FR) [dblp]
  • David Lester (University of Manchester, GB)
  • Nicolas Louvet (Université de Perpignan, FR)
  • Wolfram Luther (Universität Duisburg-Essen, DE) [dblp]
  • Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Guillaume Melquiond (ENS - Lyon, FR) [dblp]
  • Dominique Michelucci (Universite de Bourgogne, FR)
  • Bernard Mourrain (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
  • Norbert T. Müller (Universität Trier, DE) [dblp]
  • Stefan Näher (Universität Trier, DE)
  • Markus Neher (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Thomas J. Peters (University of Connecticut - Storrs, US)
  • Sylvain Pion (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
  • John D. Pryce (Cranfield University, GB) [dblp]
  • Sylvie Putot (CEA - Gif sur Yvette, FR) [dblp]
  • Nathalie Revol (ENS - Lyon, FR) [dblp]
  • Fabien Rico (UPMC - Paris, FR)
  • Siegfried M. Rump (TU Hamburg-Harburg, DE) [dblp]
  • Stefan Schirra (Universität Magdeburg, DE)
  • Matthias Schröder (University of Edinburgh, GB) [dblp]
  • Vadim Shapiro (University of Wisconsin - Madison, US) [dblp]
  • Spencer Smith (McMaster University - Hamilton, CA)
  • Christoph Spandl (Universität der Bundeswehr - München, DE)
  • Dieter Spreen (Universität Siegen, DE) [dblp]
  • Neil Stewart (Université de Montréal, CA)
  • Paul Taylor (University of Manchester, GB) [dblp]
  • Joris van der Hoeven (University Paris Sud, FR) [dblp]
  • Klaus Weihrauch (FernUniversität in Hagen, DE) [dblp]
  • Jürgen Wolff von Gudenberg (Universität Würzburg, DE)
  • Chee K. Yap (New York University, US) [dblp]
  • Martin Ziegler (Universität Paderborn, DE) [dblp]
  • Paul Zimmermann (INRIA Lorraine - Nancy, FR) [dblp]

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