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

AF：小：代数和分析中几何问题的数值符号技术

• 批准号: 1423228
• 负责人: Chee Yap
• 金额: $ 49.47万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423228&HistoricalAwards=false
• 关键词: AF; Small; Numeric; Symbolic; Techniques

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.

所有精确的数值算法都必须隐式地解决一些“零问题”，即决定在计算过程中出现的各种定义良好的数字是否为零。 无法决定零是在许多应用中普遍存在的数值非鲁棒性的根本原因。PI通过引入“精确分辨率”算法来解决零问题。 直觉上，他们解决了任何给定的参数的问题。在更多的技术细节中，该奖项研究了三类问题的分辨率精确性：（A）计算3D中多面体集合的Voronoi图，或2D中的k-椭圆，其中没有当前的“显式”精确算法。(B)解析和谐波根隔离，其中精确方法由于隐式零点问题而失败。(C)显式化问题，如计算一个好的标量函数的Morse-Smale复形，以及余维2的代数簇的同位素近似（例如，处理分析问题的能力对于理论计算机科学来说是新的。计算科学与工程中的许多问题都是在连续体上定义的，没有精确解;分辨率精确算法为它们提供了实用但理论上合理的算法。更广泛地说，这项工作有助于符号-数值计算的新兴领域。 PI的研究训练了新一代的计算机科学学生使用新的工具来攻击连续问题。