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 通过引入“精确分辨率”算法来回避零问题。 直观地说，他们可以解决任何给定 epsilon 参数的问题。这种方法最近的成功体现在 PI 在运动规划方面的工作。在更多的技术细节中，该奖项研究了三类问题的分辨率精确性：(A) 计算 3D 多面体集或 k 椭圆的 Voronoi 图在 2D 中，当前没有已知的“显式”精确算法。(B) 解析和调和根隔离，其中精确方法由于隐式零问题而失败。 (C) 显式化问题，例如计算良好标量函数的 Morse-Smale 复形，以及同维 2 的代数簇（例如空间曲线）的同位素逼近。处理分析问题的能力对于理论计算机科学来说是新的。计算科学与工程中的许多问题都是在连续体上定义的，没有精确的解；精确分辨率算法为它们提供了实用且理论上合理的算法。更广泛地说，这项工作为符号数值计算的新兴领域做出了贡献。 PI 的研究培训新一代计算机科学学生使用新工具来解决连续问题。