ITR: A New Computational Paradigm: Robustness as a Resource

数值鲁棒性和几何一致性问题在计算科学的许多领域都是众所周知的。问题是不精确的计算机运算导致不正确和不一致的几何结论（例如，点在三角形的内部还是外部）。虽然计算机变得越来越快，但软件并没有变得更强大。事实上，趋势是越来越非稳健性。我们提出了一种新的计算范式来扭转这一趋势。稳健性通常被视为一个要么全有要么全无的命题。我们的新范例包括将鲁棒性视为一种计算资源，可以与速度等其他资源进行权衡。每个程序定义了一个特定的鲁棒性-速度权衡曲线；我们希望能在这条曲线上任意一点运行程序。该提案将开发技术，使所有程序员都能有效且容易地获得这种能力。因此，任何程序员都可以编写可以健壮地运行的普通C/ c++代码。这种范式的含义是广泛的，并将鲁棒性研究的成果带入主流计算。我们建议(1)开展基础研究以支持这种新的计算范式，(2)创建实现这种范式的技术和软件工具，以及(3)探索快速且通常鲁棒的算法在算法算法设计中的应用。对于(1)，我们将重点关注效率问题，如新的根界，增量计算，保证初等函数的绝对精度。对于(2)，我们期望显著扩展ourCore库的功能、效率和可用性，并包括符号扰动等功能。最后，以(3)为例讨论了几何结构检验的一般问题及其在新的高效几何算法中的应用。我们建议将我们的鲁棒性技术和软件应用于两个重要的应用中，其中非鲁棒性问题是众所周知的：*网格生成：我们将构建第一个完全鲁棒的网格生成器，该生成器将部署在一个主要的低求解器系统Cart3d中。*几何建模：我们将建立一个强大的几何建模器，这将是第一个这样的系统，是精确敏感的。这项提议涉及与德国马克斯-普朗克计算机科学研究所Mehlhorn教授的算法和复杂性小组的国际合作。我们的国内合作者是来自nasa研究中心的Michael Aftosmis（网格生成）和来自at研究实验室的Shankar Krishnan（几何建模）。

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).