RESOURCES FOR ROBUST COMPUTATION


Numerical nonrobustness causes all kinds of failures. But can you produce an example with an infinite loop? This and other forms of manifestation are discussed in Anatomy of Algorithmic Failures. It is intended to provide classroom examples. Source code available.
Robust Geometric Algorithms and their Implementation, Guest Editorial Forward from a Special Issue of Computational Geometry: Theory and Applications (CGTA 33:1, 2006).
Resource Page for ``Survey/Tutorial on Exact Geometric Computing'' Lectures at Workshop on Geometric Computing, University of Hong Kong, June 27--29, 2001.
General Forums on Nonrobustness Issues
-- DIMACS Workshop on Implementation of Geometric Algorithms Dec 4-6, 2002
-- SIAM Minisymposium: Robust Geometric Computation (2001)
-- MSRI Workshop on Foundations of CAD (1999)
-- SIAM Workshop on Integration of CAD and CFD (1999)
-- Emerging Challenges in Computational Topology Report (1999)
--Computational Geometry Task Force Report (1996)
-- SIGGRAPH'98 Panel on Robust Geometry. Position Statements from panelists.
--ACM Strategic Directions Report (1996)
--Tom Peters's presentation on Non-robustness Issues in CAGD [here is a local copy] This work is part of the NSF/DARPA CARGO Program (2001-4) in which non-robustness and topological consistency issues are addressed.
Non-robustness in the News
-- Patriot Missile Defense Saga, from US General Accounting Office (local copy)
-- Ariane 5 Saga, from European Space Agency
-- Software Bugs Cost US economy $59.5 billion/year. The report focused on the financial sector, and the automotive and aircraft manufacturing industries. In the latter 2 industries, the cost is estimated at $1.8 billion/year. Report was prepared by Research Triangle Institute for NIST.
-- Disasters attributable to numerical errors, from Doug Arnold (including the North Sea oil rig collapse)
Projects and Groups
--K. Mehlhorn at Max-Planck Institute of Computer Science is involved in various robustness projects (LEDA, CGAL, EXACUS).
--PRISME Project at INRIA, Sophia-Antipolia, directed by J.-D. Boissonnat.
-- Superrobust Computation Project of K. Sugihara at Tokyo University
-- Arenaire Project of J.-M. Muller.
-- iRRAM Project of N. Mueller is a C++ package for error-free real arithmetic based on the concept of a real RAM.
-- Professor Cuyt's Group on Computer Arithmetic and Numerical Techniques.
-- Evaluation of Special Functions from Dan Lozier at NIST: includes a function evaluator service.
Software
-- GMP Home. New in GMP 3.1 (FFT Based Multiplication!)
--MPFR homepage The MPFR library is a C library for multiprecision floating-point computations with exact rounding. It is based on the GMP multiprecision library and will replace the MPF class starting with version 3.1 of GMP. Here are some timings .
-- Intel's Open source for Numerics
-- Arithmetic Explorer
Robust Meshing and Triangulation
-- GNU Triangulated Surface (GTS) Library: Open Source free software for 3D surfaces triangular meshes. Version 0.4.0 (Jan 2001).
FEATURES: based on the GTK+ GUI Toolkit, 2D dynamic constrained Delaunay triangulation, robust predicates of Shewchuk, Boolean set operations, multiresolution models, dynamic view-independent LOD, some view-dependent LOD, Kd-trees, collision detection.
[ Bibliography   |   Reference Manual   |   ]
Computing transcendental functions.
-- The Table Maker's Dilemma
-- Elementary Functions, Algorithms and Implementation, book by Jean-Michel Muller from Birkhauser, Boston (1997).
Organizations and Web Resources
-- CCA Net (Computability and Complexity in Analysis)
-- Interval Computation
-- Real Algebraic and Analytic Geometry (RAAG)
-- Foundations of Computational Mathematics
Software Resources
Source Forge: free Open Source developer services (CVS, mailists, forums, site hosting, etc). Thousands of projects in every field.
Conferences
-- IEEE Symposium on Computer Arithmetic. Call for Papers for 15th Symposium on Computer Arithmetic (Nov 1, 2000).
-- 4th Conference on Real Numbers and Computers
-- 4th Workshop on Computability and Complexity in Analysis Sep 17-20, 2000, Swansea, Wales.
Bibliography Collection
-- Constructivity, Computability and Complexity in Analysis, a collection of over 500 entries.
-- Numerical techniques from Rational Approximation Theory and Computer Arithmetic, a collection of over 2500 entries.

[ CS Research Groups ] [ CS Department ] [ Courant Institute ] [ NYU]
Comments?
exact@cs.nyu.edu.