Reliable Computation and Complexity on the Reals (Dagstuhl Seminar 17481)

Authors Norbert T. Müller, Siegfried M. Rump, Klaus Weihrauch, Martin Ziegler and all authors of the abstracts in this report



PDF
Thumbnail PDF

File

DagRep.7.11.142.pdf
  • Filesize: 2.21 MB
  • 26 pages

Document Identifiers

Author Details

Norbert T. Müller
Siegfried M. Rump
Klaus Weihrauch
Martin Ziegler
and all authors of the abstracts in this report

Cite AsGet BibTex

Norbert T. Müller, Siegfried M. Rump, Klaus Weihrauch, and Martin Ziegler. Reliable Computation and Complexity on the Reals (Dagstuhl Seminar 17481). In Dagstuhl Reports, Volume 7, Issue 11, pp. 142-167, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/DagRep.7.11.142

Abstract

Naive computations with real numbers on computers may cause serious errors. In traditional numerical computation these errors are often neglected or, more seriously, not identified. Two approaches attack this problem and investigate its background, Reliable Computing and Computable Analysis. Methods in Reliable Computing are essentially mathematical theorems, the assumptions of which are verified on the computer. This verification is performed using the very efficient floating point arithmetic. If the verification succeeds, the assertions are true and correct error bounds have been computed; if not, a corresponding message is given. Thus the results are always mathematically correct. A specific advantage of Reliable Computing is that imprecise data are accepted; the challenge is to develop mathematical theorems the assumptions of which can be verified effectively in floating-point and to produce narrow bounds for the solution. Computable Analysis extends the traditional theory of computability on countable sets to the real numbers and more general spaces by refining continuity to computability. Numerous even basic and simple problems are not computable since they cannot be solved continuously. In many cases computability can be refined to computational complexity which is the time or space a Turing machine needs to compute a result with given precision. By treating precision as a parameter, this goes far beyond the restrictions of double precision arithmetic used in Reliable computing. For practical purposes, however, the asymptotic results from complexity theory must be refined. Software libraries provide efficient implementations for exact real computations. Both approaches are established theories with numerous important results. However, despite of their obvious close relations these two areas are developing almost independently. For exploring possibilities of closer contact we have invited experts from both areas to this seminar. For improving the mutual understanding some tutorial-like talks have been included in the program. As a result of the seminar it can be stated that interesting joint research is possible.
Keywords
  • Computable Analysis
  • Verification Methods
  • Real Complexity Theory
  • Reliable Computing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail