AF: Small: Numeric-Symbolic Techniques for Geometric Problems in Algebra and Analysis

New York University, New York NY

Investigators

Abstract

All exact numerical algorithms must implicitly solve some "Zero Problem", namely decide if various well-defined numbers arising in the course of its computation are actually zero. The inability to decide zero is the root cause of pervasive numerical nonrobustness in many applications. The PI side-steps the Zero Problem by introducing "resolution-exact" algorithms. Intuitively, they solve the problem up to any given epsilon parameter. Recent successes of this approach are seen in the PI's work in motion planning. In more technical detail, this award studies resolution-exactness to three classes of problems: (A) Computing the Voronoi diagrams of polyhedral sets in 3D, or of k-ellipses in 2D where no current "explicit" exact algorithms are known. (B) Analytic and harmonic root isolation, in which exact methods fail because of the implicit Zero Problem. (C) Explicitization Problems such as computing the Morse-Smale complex of a nice scalar function, and isotopic approximation of algebraic varieties of co-dimension 2 (e.g., spatial curves). The ability to treat analytic problems is new for Theoretical Computer Science. Many problems of Computational Science and Engineering are defined on the continua, and have no exact solutions; resolution-exact algorithms provide practical yet theoretically-sound algorithms for them. More broadly, this work contributes to the emerging area of symbolic-numeric computation. The PI's research trains a new generation of Computer Science students using new tools for attacking continua problems.