ITR: A New Computational Paradigm: Robustness as a Resource

点击翻译按钮获取中文摘要

The problem of numerical robustness and geometric consistency is well knownin many areas of computational science. The issue is that inexact computer arith-metic leads to incorrect and inconsistent geometric conclusions (for example, is apoint inside or outside a triangle). While computers are getting faster, softwareis not getting more robust. Indeed, the trend is towards more nonrobustness. Wepropose a new computational paradigm to reverse this trend.Robustness is often seen as an all-or-nothing proposition. Our new paradigmconsists in viewing robustness as a computational resource, to be traded off againstother resources such as speed. Each program defines a certain robustness-speedtrade-off curve; we want to be able to run the program at any point along thiscurve. This proposal will develop the technology to make this capability effcientand easily accessible to all programmers. As a result, any programmer can producenearly ordinary C/C++ code which can be run robustly. The implications of thisparadigm are wide ranging, and will bring the fruits of robustness research intomainstream computing.We propose to (1) conduct basic research to support this new computingparadigm, (2) to create the technology and software tools to achieve this paradigm,and (3) to explore the applications of fast and usually robust algorithms in algo-rithm design. For (1), we will focus on effciency issues such as novel root bounds,incremental computation, guaranteed absolute precision for elementary functions.For (2), we expect to significantly extend the power, efficiency and usability of ourCore Library and include capabilities such as symbolic perturbation. Finally anexample of (3) concerns the general problem of checking of geometric structures andtheir applications in new efficient geometric algorithms.We propose to apply our robustness techniques and software to two significantapplications in which nonrobustness problems are well-known:* Mesh Generation: we will construct the first fully robust mesh generator whichwill be deployed in a major ow solver system, Cart3d.* Geometric Modeling: we will build a robust geometric modeler which will bethe first such system that is precision-sensitive.This proposal involves international collaboration with Professor Mehlhorn'sAlgorithms and Complexity Group at the Max-Planck Institute of Computer Sci-ence in Germany. Our domestic collaborator are Michael Aftosmis from NASAAmes Research Center (on mesh generation) and Shankar Krishnan from AT&TResearch Laboratories (on geometric modeling).