AF: Small: Analysis Algorithms: Continuous and Algebraic Amortization

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

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.