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.
