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.中绝大多数算法的研究计划，该项目开发了一种新的非稳态分析技术，称为持续摊销。 它能够量化输入实例作为积分的复杂性，并将问题降低以在积分上提供明确的界限。 现在，为1维情况生产这种自适应界限的第一个示例的成功现在扩展到更高的维度。 为了绑定这些积分，人们需要另一种称为代数摊销的摊销形式。 这通过同时界定单个边界的乘积来概括通常的零界限。 这些进步是基于主要研究者在先前的NSF项目上的几何计算方面的工作。 该项目还通过使用开源核心图书馆软件实现其算法来验证其算法。