A Theory of Real Approximations, with Applications

实数近似理论及其应用

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

Exact Geometric Computation (EGC) is one of the most successful approaches to nonrobust numerical computation. The basis of EGC is {\em guaranteed accuracy computation}, a computational mode in which each numerical quantity can be computed to any user-specified accuracy. In the last 10 years, major software libraries and many robust algorithms and applications have been implemented based on EGC principles. What is lacking is a model of computation to capture this mode. The PI introduces a {\em theory of real approximation} which fills this gap. The approach postulates a suitable countable set $\mathbb{F}$ $\mathbb{Z}\ib\mathbb{F}\ib\mathbb{R}$) of {\em representable reals}, with the property that all numerical input and output come from $\mathbb{F}$. Two current theories directly address the specific nature of real computation: the TTE School of Weihrauch and others, and the Algebraic School from Blum, Shub and Smale (BSS). The PI's approach is distinct from both schools, but complements them. The PI further introduces a {\em Numerical Computational Model}, seen as an intermediate model between the Turing model and the BSS model. The development is informed by classical complexity theory, yet directly motivated by current development of EGC software.Research topics include: * The computability and complexity of real approximation. Connections are made to standard complexity theory via such topics as $NP$-completeness, and also to the algebraic theory of Blum, Shub and Smale.* Fundamental questions motivated by the implementation of EGC software: dynamic constructive zero bounds, geometric separation bounds, complexity of approximate evaluation, and precision-sensitive complexity.Some of these questions (e.g., zero bounds) involve a combination of experimental validation with theoretical studies. Implementation is done using the Core Library, the PI's ongoing open-source library project.INTELLECTUAL MERIT.One addresses a topic of long-standing interest, namely, providing a foundation for real computation and its complexity. The PI's approach to real approximation is concise, provably distinct from current approaches, unexpected, yet firmly grounded in computing practice. The new theory is, by design, a theory for EGC. But it can also serve as a foundation for numerical computation, something which Smale and others have called for. BROADER IMPACT. Through the applications of EGC to robustness issues, this work is expected impact many areas of omputational science and engineering. The practical work in this research is distributed freely as part of the Core Library software. This library, with its unique interface model, is widely applicable because any C++program can invoke it to achieve guaranteed accuracy. Guaranteed accuracy computation has applications beyond nonrobustness, from verifying conjectures to testing software. The PI, as in the past, is actively engaged in various outreach efforts to related fields, and to the larger computing community.

精确几何计算（EGC）是非鲁棒数值计算最成功的方法之一。 EGC 的基础是{\em 保证精度计算}，这是一种计算模式，其中每个数值量都可以计算到任何用户指定的精度。 在过去的 10 年里，主要的软件库以及许多强大的算法和应用程序都是基于 EGC 原理实现的。 缺少的是捕捉这种模式的计算模型。 PI 引入了{\em 实数逼近理论}来填补这一空白。 该方法假设一个合适的可数集合 $\mathbb{F}$ $\mathbb{Z}\ib\mathbb{F}\ib\mathbb{R}$) {\em 可表示实数}，其属性是所有数值输入和输出来自$\mathbb{F}$。当前的两种理论直接解决了实际计算的特定性质：Weihrauch 等人的 TTE 学派，以及 Blum、Shub 和 Smale (BSS) 的代数学派。 PI 的方法与这两个学校不同，但却是互补的。 PI 进一步引入了数值计算模型，被视为图灵模型和 BSS 模型之间的中间模型。 该开发受到经典复杂性理论的启发，但直接受到 EGC 软件当前开发的推动。研究主题包括： * 实数近似的可计算性和复杂性。通过 $NP$ 完备性等主题与标准复杂性理论建立联系，还与 Blum、Shub 和 Smale 的代数理论建立联系。* EGC 软件实施引发的基本问题：动态构造零界、几何分离界、近似评估的复杂性和精度敏感的复杂性。其中一些问题（例如零界）涉及实验验证与理论研究的结合。实现是使用核心库完成的，这是 PI 正在进行的开源库项目。智力优点。一个解决了长期感兴趣的主题，即为实际计算及其复杂性提供基础。 PI 的实数近似方法非常简洁，可证明与当前方法不同，出人意料，但又牢固地扎根于计算实践。从设计上来说，新理论是 EGC 的理论。但它也可以作为数值计算的基础，这是 Smale 和其他人所呼吁的。 更广泛的影响。通过 EGC 在鲁棒性问题上的应用，这项工作预计会影响计算科学和工程的许多领域。本研究中的实际工作作为核心库软件的一部分免费分发。 该库以其独特的接口模型而具有广泛的适用性，因为任何C++程序都可以调用它来保证准确性。 有保证的精度计算的应用超出了非鲁棒性，从验证猜想到测试软件。与过去一样，PI 积极参与相关领域和更大的计算社区的各种外展工作。