Dagstuhl Seminar Proceedings, Volume 6021



Publication Details

  • published at: 2006-09-13
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
06021 Abstracts Collection – Reliable Implementation of Real Number Algorithms: Theory and Practice

Authors: Peter Hertling, Christoph M. Hoffmann, Wolfram Luther, and Nathalie Revol


Abstract
From 08.01.06 to 13.01.06, the Dagstuhl Seminar 06021 ``Reliable Implementation of Real Number Algorithms: Theory and Practice'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Peter Hertling, Christoph M. Hoffmann, Wolfram Luther, and Nathalie Revol. 06021 Abstracts Collection – Reliable Implementation of Real Number Algorithms: Theory and Practice. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{hertling_et_al:DagSemProc.06021.1,
  author =	{Hertling, Peter and Hoffmann, Christoph M. and Luther, Wolfram and Revol, Nathalie},
  title =	{{06021 Abstracts Collection – Reliable Implementation of Real Number Algorithms: Theory and Practice}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.1},
  URN =		{urn:nbn:de:0030-drops-7491},
  doi =		{10.4230/DagSemProc.06021.1},
  annote =	{Keywords: Real number algorithms, reliable implementation}
}
Document
06021 Summary – Reliable Implementation of Real Number Algorithms: Theory and Practice

Authors: Peter Hertling, Christoph M. Hoffmann, Wolfram Luther, and Nathalie Revol


Abstract
The seminar brought together researchers from many different disciplines concerned with the reliable implementation of real number algorithms either from a theoretical or from a practical point of view. In this summary we describe the topics, the goals, and the contributions of the seminar.

Cite as

Peter Hertling, Christoph M. Hoffmann, Wolfram Luther, and Nathalie Revol. 06021 Summary – Reliable Implementation of Real Number Algorithms: Theory and Practice. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{hertling_et_al:DagSemProc.06021.2,
  author =	{Hertling, Peter and Hoffmann, Christoph M. and Luther, Wolfram and Revol, Nathalie},
  title =	{{06021 Summary – Reliable Implementation of Real Number Algorithms: Theory and Practice}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.2},
  URN =		{urn:nbn:de:0030-drops-7117},
  doi =		{10.4230/DagSemProc.06021.2},
  annote =	{Keywords: Real number computability, real number algorithms, reliable computing, algorithms with result verification, interval arithmetic, geometric computing, robustness, solid modeling}
}
Document
A Descartes Algorithms for Polynomials with Bit-Stream Coefficients

Authors: Kurt Mehlhorn, Arno Eigenwillig, Lutz Kettner, Werner Krandick, Susanne Schmitt, and Nicola Wolpert


Abstract
The Descartes method is an algorithm for isolating the real roots of square-free polynomials with real coefficients. We assume that coefficients are given as (potentially infinite) bit-streams. In other words, coefficients can be approximated to any desired accuracy, but are not known exactly. We show that a variant of the Descartes algorithm can cope with bit-stream coefficients. To isolate the real roots of a square-free real polynomial $q(x) = q_nx^n+ldots+q_0$ with root separation $ ho$, coefficients $abs{q_n}ge1$ and $abs{q_i} le 2^ au$, it needs coefficient approximations to $O(n(log(1/ ho) + au))$ bits after the binary point and has an expected cost of $O(n^4 (log(1/ ho) + au)^2)$ bit operations.

Cite as

Kurt Mehlhorn, Arno Eigenwillig, Lutz Kettner, Werner Krandick, Susanne Schmitt, and Nicola Wolpert. A Descartes Algorithms for Polynomials with Bit-Stream Coefficients. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{mehlhorn_et_al:DagSemProc.06021.3,
  author =	{Mehlhorn, Kurt and Eigenwillig, Arno and Kettner, Lutz and Krandick, Werner and Schmitt, Susanne and Wolpert, Nicola},
  title =	{{A Descartes Algorithms for Polynomials with Bit-Stream Coefficients}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.3},
  URN =		{urn:nbn:de:0030-drops-7157},
  doi =		{10.4230/DagSemProc.06021.3},
  annote =	{Keywords: Root Isolation, Interval Arithmetic, Descartes Algorithm}
}
Document
A Proposal to add Interval Arithmetic to the C++ Standard Library

Authors: Sylvain Pion, Hervé Brönnimann, and Guillaume Melquiond


Abstract
I will report on a recent effort by Guillaume Melquiond, Hervé Br"onnimann and myself to push forward a proposal to include interval arithmetic in the next C++ ISO standard. The goals of the standardization are to produce a unified specification which will serve as many uses of intervals as possible, together with hoping for very efficient implementations, closer to the compilers. I will describe how the standardization process works, explain some of the design choices made, and list some of the other questions arising in the process. We welcome any comment on the proposal.

Cite as

Sylvain Pion, Hervé Brönnimann, and Guillaume Melquiond. A Proposal to add Interval Arithmetic to the C++ Standard Library. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{pion_et_al:DagSemProc.06021.4,
  author =	{Pion, Sylvain and Br\"{o}nnimann, Herv\'{e} and Melquiond, Guillaume},
  title =	{{A Proposal to add Interval Arithmetic to the C++ Standard Library}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.4},
  URN =		{urn:nbn:de:0030-drops-7189},
  doi =		{10.4230/DagSemProc.06021.4},
  annote =	{Keywords: Interval arithmetic, C++, ISO standard}
}
Document
Floating Point Geometric Algorithms for Topologically Correct Scientific Visualization

Authors: Thomas J. Peters and Edward L. F. Moore


Abstract
The unresolved subtleties of floating point computations in geometric modeling become considerably more difficult in animations and scientific visualizations. Some emerging solutions based upon topological considerations will be presented. A novel geometric seeding algorithm for Newton's method was used in experiments to determine feasible support for these visualization applications.

Cite as

Thomas J. Peters and Edward L. F. Moore. Floating Point Geometric Algorithms for Topologically Correct Scientific Visualization. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{peters_et_al:DagSemProc.06021.5,
  author =	{Peters, Thomas J. and Moore, Edward L. F.},
  title =	{{Floating Point Geometric Algorithms for Topologically Correct Scientific Visualization}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.5},
  URN =		{urn:nbn:de:0030-drops-7176},
  doi =		{10.4230/DagSemProc.06021.5},
  annote =	{Keywords: Geometry, algorithm, visualization}
}
Document
Interval Arithmetic Using SSE-2

Authors: Branimir Lambov


Abstract
We present an implementation of double precision interval arithmetic using the single-instruction-multiple-data SSE-2 instruction and register set extensions. The implementation is part of a package for exact real arithmetic, which defines the interval arithmetic variation that must be used: incorrect operations such as division by zero cause exceptions, loose evaluation of the operations is in effect, and performance is more important than tightness of the produced bounds. The SSE2 extensions are suitable for the job, because they can be used to operate on a pair of double precision numbers and include separate rounding mode control and detection of the exceptional conditions. The paper describes the ideas we use to fit interval arithmetic to this set of instructions, shows a performance comparison with other freely available interval arithmetic packages, and discusses possible very simple hardware extensions that can significantly increase the performance of interval arithmetic.

Cite as

Branimir Lambov. Interval Arithmetic Using SSE-2. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{lambov:DagSemProc.06021.6,
  author =	{Lambov, Branimir},
  title =	{{Interval Arithmetic Using SSE-2}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.6},
  URN =		{urn:nbn:de:0030-drops-7140},
  doi =		{10.4230/DagSemProc.06021.6},
  annote =	{Keywords: Interval Arithmetic, SSE2}
}
Document
Interval Subroutine Library Mission

Authors: George F. Corliss, R. Baker Kearfott, Ned Nedialkov, John D. Pryce, and Spencer Smith


Abstract
We propose the collection, standardization, and distribution of a full-featured production quality library for reliable scientific computing with routines using interval techniques for use by the wide community of applications developers.

Cite as

George F. Corliss, R. Baker Kearfott, Ned Nedialkov, John D. Pryce, and Spencer Smith. Interval Subroutine Library Mission. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{corliss_et_al:DagSemProc.06021.7,
  author =	{Corliss, George F. and Kearfott, R. Baker and Nedialkov, Ned and Pryce, John D. and Smith, Spencer},
  title =	{{Interval Subroutine Library Mission}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.7},
  URN =		{urn:nbn:de:0030-drops-7122},
  doi =		{10.4230/DagSemProc.06021.7},
  annote =	{Keywords: Subroutine library, problem-solving library, C++ interval standard}
}
Document
Robustness and Randomness

Authors: Dominique Michelucci, Jean Michel Moreau, and Sebti Foufou


Abstract
Robustness problems of computational geometry algorithms is a topic that has been subject to intensive research efforts from both computer science and mathematics communities. Robustness problems are caused by the lack of precision in computations involving floating-point instead of real numbers. This paper reviews methods dealing with robustness and inaccuracy problems. It discussed approaches based on exact arithmetic, interval arithmetic and probabilistic methods. The paper investigates the possibility to use randomness at certain levels of reasoning to make geometric constructions more robust.

Cite as

Dominique Michelucci, Jean Michel Moreau, and Sebti Foufou. Robustness and Randomness. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{michelucci_et_al:DagSemProc.06021.8,
  author =	{Michelucci, Dominique and Moreau, Jean Michel and Foufou, Sebti},
  title =	{{Robustness and Randomness}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.8},
  URN =		{urn:nbn:de:0030-drops-7167},
  doi =		{10.4230/DagSemProc.06021.8},
  annote =	{Keywords: Robustness, interval, randomness, inaccuracy, geometric computation}
}
Document
Transfinite interpolation for well-definition in error analysis in solid modelling

Authors: Neil Stewart and Malika Zidani


Abstract
An overall approach to the problem of error analysis in the context of solid modelling, analogous to the standard forward/backward error analysis of Numerical Analysis, was described in a recent paper by Hoffmann and Stewart. An important subproblem within this overall approach is the well-definition of the sets specified by inconsistent data. These inconsistencies may come from the use of finite-precision real-number arithmetic, from the use of low-degree curves to approximate boundaries, or from terminating an infinite convergent (subdivision) process after only a finite number of steps. An earlier paper, by Andersson and the present authors, showed how to resolve this problem of well-definition, in the context of standard trimmed-NURBS representations, by using the Whitney Extension Theorem. In this paper we will show how an analogous approach can be used in the context of trimmed surfaces based on combined-subdivision representations, such as those proposed by Litke, Levin and Schröder. A further component of the problem of well-definition is ensuring that adjacent patches in a representation do not have extraneous intersections. (Here, "extraneous intersections" refers to intersections, between two patches forming part of the boundary, other than prescribed intersections along a common edge or at a common vertex.) The paper also describes the derivation of a bound for normal vectors that can be used for this purpose. This bound is relevant both in the case of trimmed-NURBS representations, and in the case of combined subdivision with trimming.

Cite as

Neil Stewart and Malika Zidani. Transfinite interpolation for well-definition in error analysis in solid modelling. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{stewart_et_al:DagSemProc.06021.9,
  author =	{Stewart, Neil and Zidani, Malika},
  title =	{{Transfinite interpolation for well-definition in error analysis in solid modelling}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.9},
  URN =		{urn:nbn:de:0030-drops-7195},
  doi =		{10.4230/DagSemProc.06021.9},
  annote =	{Keywords: Forward/backward error analysis, robustness, well-definition, trimmed NURBS, combined subdivision, trimming, bounds on normals}
}
Document
Upper and Lower Bounds on Sizes of Finite Bisimulations of Pfaffian Dynamical Systems

Authors: Margarita Korovina and Nicolai Vorobjov


Abstract
In this paper we study a class of dynamical systems defined by Pfaffian maps. It is a sub-class of o-minimal dynamical systems which capture rich continuous dynamics and yet can be studied using finite bisimulations. The existence of finite bisimulations for o-minimal dynamical and hybrid systems has been shown by several authors; see e.g. Brihaye et al (2004), Davoren (1999), Lafferriere et al (2000). The next natural question to investigate is how the sizes of such bisimulations can be bounded. The first step in this direction was done by Korovina et al (2004) where a double exponential upper bound was shown for Pfaffian dynamical and hybrid systems. In the present paper we improve this bound to a single exponential upper bound. Moreover we show that this bound is tight in general, by exhibiting a parameterized class of systems on which the exponential bound is attained. The bounds provide a basis for designing efficient algorithms for computing bisimulations, solving reachability and motion planning problems.

Cite as

Margarita Korovina and Nicolai Vorobjov. Upper and Lower Bounds on Sizes of Finite Bisimulations of Pfaffian Dynamical Systems. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{korovina_et_al:DagSemProc.06021.10,
  author =	{Korovina, Margarita and Vorobjov, Nicolai},
  title =	{{Upper and Lower Bounds on Sizes of Finite Bisimulations of Pfaffian Dynamical Systems}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.10},
  URN =		{urn:nbn:de:0030-drops-7130},
  doi =		{10.4230/DagSemProc.06021.10},
  annote =	{Keywords: Hybrid systems, Pfaffian functions, bisimulation}
}
Document
Worst Cases for the Exponential Function in the IEEE 754r decimal64 Format

Authors: Vincent Lefèvre, Damien Stehlé, and Paul Zimmermann


Abstract
We searched for the worst cases for correct rounding of the exponential function in the IEEE 754r decimal64 format, and computed all the bad cases whose distance from a breakpoint (for all rounding modes) is less than $10^{-15}$,ulp, and we give the worst ones. In particular, the worst case for $|x| geq 3 imes 10^{-11}$ is $exp(9.407822313572878 imes 10^{-2}) = 1.098645682066338,5,0000000000000000,278ldots$. This work can be extended to other elementary functions in the decimal64 format and allows the design of reasonably fast routines that will evaluate these functions with correct rounding, at least in some domains.

Cite as

Vincent Lefèvre, Damien Stehlé, and Paul Zimmermann. Worst Cases for the Exponential Function in the IEEE 754r decimal64 Format. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{lefevre_et_al:DagSemProc.06021.11,
  author =	{Lef\`{e}vre, Vincent and Stehl\'{e}, Damien and Zimmermann, Paul},
  title =	{{Worst Cases for the Exponential Function in the IEEE 754r decimal64 Format}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.11},
  URN =		{urn:nbn:de:0030-drops-7483},
  doi =		{10.4230/DagSemProc.06021.11},
  annote =	{Keywords: Floating-point arithmetic, decimal arithmetic, table maker's dilemma, correct rounding, elementary functions}
}

Filters


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