A Theory of Real Approximations, with 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.