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保证的准确性计算}，一种计算模式，可以将每个数值计算为任何用户指定的精度。 在过去的十年中，基于EGC原则实施了主要的软件库以及许多强大的算法和应用程序。 缺少的是捕获此模式的计算模型。 PI引入了填补此空白的真实近似理论}。 该方法假设合适的可数集$ \ mathbb {f} $ $ \ MATHBB {z} \ ib \ ib \ Mathbb {f} \ ib \ ib \ ib \ Mathbb {r} $ {\ em em emandable reals}，具有所有数字输入和输出的属性，这些属性来自$ \ m m iathbb = f} $ {f}。两种当前的理论直接介绍了真实计算的特定性质：Weihrauch和其他人的TTE学校，以及Blum，Shub和Smale（BSS）的代数学校。 PI的方法与两所学校都不同，但对它们进行了补充。 PI进一步引入了{\ em数值计算模型}，被视为Turing模型和BSS模型之间的中间模型。 该开发是通过经典复杂性理论告知的，但直接是由EGC软件的当前开发进行的。研究主题包括： *实际近似的可计算性和复杂性。通过$ np $ competitions等主题以及Blum，Shub和Smale的代数理论等主题与标准复杂性理论建立联系。通过理论研究验证。使用核心库，PI正在进行的开源库项目进行实施。IntellectualFe上。一个讨论了一个长期以来的兴趣主题，即为真实计算及其复杂性提供了基础。 PI的真实近似方法是简洁的，证明与当前的方法不同，但在计算实践中坚定地扎根。根据设计，新理论是EGC的理论。但是它也可以作为数值计算的基础，这是Smale和其他人要求的。 更广泛的影响。通过EGC在鲁棒性问题上的应用，这项工作有望影响到计算科学和工程的许多领域。这项研究中的实际工作是作为核心图书馆软件的一部分自由分发的。 该库具有其独特的接口模型，非常适用，因为任何C ++程序都可以调用它以实现保证的准确性。 从验证猜想到测试软件，保证的准确性计算的应用超出了非保险性。与过去一样，PI积极从事各种宣传工作，并向相关领域和更大的计算社区。