Decision problems and round-off machines
Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique42, Avenue Gaspard Coriolis
31057 Toulouse Cedex
Tel : 05 61 19 31 31 - Fax : 05 61 19 30 00
DECISION PROBLEMS AND ROUND-OFF MACHINES
Professor Jean-Pierre Dedieu
Universite Paul Sabatier Toulouse
Thursday July 16, 11.00 a.m. Parallel Algorithms Seminar CERFACS Conference Room
In this talk we consider a decision problem and, given a machine over the real numbers which solves such a problem, we study its behaviour when instead of the usual arithmetic operations we use a floating point arithmetic. In other words, to an exact machine M we associate a round-off machine M_r obtained in substituting in M each arithmetic operation by the corresponding floating point operation. We first prove that, if we avoid ill-posed instances (a concept depending only on the problem) and unstable instances (a concept depending on the machine) and if the round-off unit is small enough then the decisions taken by the exact machine and the round-off machines on this instance are the same. In a second result we adopt a backward error analysis point of view : the decision taken by the round-off machine on input x is identical to the decision taken by the exact machine on a nearby input.
Cerfacs' Conferences 1998 Home Page
