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.该项目开发了一种新的非概率分析技术，称为连续摊销。 它能够将输入实例的复杂性量化为积分，并将问题简化为提供积分的显式边界。 在生产的第一个例子，这种自适应界限的1维情况下，现在扩展到更高的维度。 为了约束这些积分，需要另一种形式的摊销，称为代数摊销。 这推广了通常的零界限，同时界定了个别界限的产品。 这些进展建立在首席研究员的工作，在以前的NSF项目的精确几何计算。 该项目还通过使用开源核心库软件实现其算法来验证其算法。