AF: Small: Analysis Algorithms: Continuous and Algebraic Amortization

AF：小：分析算法：连续和代数摊销

• 批准号: 0917093
• 负责人: Chee Yap
• 金额: $ 49.58万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0917093&HistoricalAwards=false
• 关键词: AF; Small; Analysis; Algorithms; Continuous

Adaptive numerical algorithms are widely used to solve continuous problems in Computational Science and Engineering (CS & E). Unlike discrete combinatorial algorithms which predominate in Theoretical Computer Science, such algorithms for the continua are typically numerical in nature, iterative in form, and have adaptive complexity. The complexity analysis of such algorithms is a major challenge for theoretical computer science. In particular, it is necessary to properly account for the adaptivity that are inherent in such algorithms. Until now, all complexity analysis that accounts for adaptivity (for example, in linear programming) must invoke some probabilistic assumptions. The broader impact of this project lies in the push to extend the scope of theoretical algorithms into the realm of continuous computation. The project is seen as part of a research program to develop a computational model and complexity theory for real computation, one that can account for the vast majority of algorithms in CS & E.This project develops a new non-probabilistic analysis technique called continuous amortization. It is able to quantify the complexity of an input instance as an integral, and reduce the problem to providing explicit bounds on the integral. The success in producing the first example of such adaptive bounds for the 1-dimensional case is now extended to higher dimensions. In order to bound these integrals, one needs another form of amortization called algebraic amortization. This generalizes the usual zero bounds by simultaneously bounding a product of individual bounds. These advances build upon the principal investigator's work in previous NSF projects on Exact Geometric Computation. The project also validates its algorithms by implementing them using the open-source Core Library software.

自适应数值算法广泛用于解决计算科学与工程（CS＆E）中的连续问题。 与理论计算机科学中占主导地位的离散组合算法不同，此类连续体算法本质上通常是数值的、迭代形式的，并且具有自适应复杂性。 此类算法的复杂性分析是理论计算机科学的重大挑战。 特别是，有必要正确考虑此类算法固有的适应性。 到目前为止，所有考虑适应性的复杂性分析（例如，在线性规划中）都必须调用一些概率假设。 该项目更广泛的影响在于推动理论算法的范围扩展到连续计算领域。 该项目被视为开发用于实际计算的计算模型和复杂性理论的研究计划的一部分，该理论可以解释 CS & E 中的绝大多数算法。该项目开发了一种称为连续摊销的新非概率分析技术。 它能够将输入实例的复杂性量化为积分，并将问题简化为提供积分的显式界限。 为一维情况生成此类自适应边界的第一个示例的成功现在已扩展到更高的维度。 为了限制这些积分，需要另一种形式的摊销，称为代数摊销。 这通过同时限制各个界限的乘积来概括通常的零界限。 这些进展建立在首席研究员之前在 NSF 精确几何计算项目中的工作基础上。 该项目还通过使用开源核心库软件实施算法来验证其算法。