ITR: A New Computational Paradigm: Robustness as a Resource

ITR：新的计算范式：作为资源的鲁棒性

• 批准号: 0082056
• 负责人: Chee Yap
• 金额: $ 48.99万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0082056&HistoricalAwards=false
• 关键词: ITR; New; Computational; Paradigm; Robustness

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

数值鲁棒性和几何一致性的问题是众所周知的计算科学领域。问题在于，不精确的计算机算术会导致不正确且不一致的几何结论（例如，在三角形内部或外部是空位）。尽管计算机越来越快，但软件并没有变得更加强大。实际上，趋势是朝着更加精心固定的趋势。 Wepropos的新计算范式扭转了这一趋势。自然性通常被视为一个全或全无的命题。我们的新范式主义者将鲁棒性视为一种计算资源，将与其他资源（例如速度）进行交易。每个程序都定义了一定的稳健性速度曲线；我们希望能够在此曲线的任何时候运行该程序。该建议将开发该技术，以使所有程序员都可以轻松访问此功能。结果，任何程序员都可以生产一个可以稳健运行的普通C/C ++代码。 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.对于（1），我们将专注于效率问题，例如新的根界，增量计算，确保基本功能的绝对精度。对于（2），我们期望显着扩展我们的科目库的功率，效率和可用性，并包括符号扰动等功能。 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这是一个强大的几何建模器，将首先是精确敏感的系统。该提案涉及与德国Max-Planck计算机科学研究所的Mehlhorn'salgorithms and Compliveity Group的国际合作。我们的国内合作者是Nasaames研究中心（网眼生成）的Michael Aftosmis，AT＆Tresearch Laboratories（几何建模）的Shankar Krishnan。