Design and Implementation of Algorithms in Semi-Algebraic Geometry

半代数几何算法的设计与实现

• 批准号: 9901947
• 负责人: Saugata Basu
• 金额: $ 7.79万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-06-01 至 2000-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9901947&HistoricalAwards=false
• 关键词: Design; Implementation; Algorithms; Semi; Algebraic

Algorithmic semi-algebraic geometry has attracted a lot of attention in recent years due to its applications in a range of areas such as robot motion planning, geometric modeling, computer-aided design, geometric theorem proving, mathematical investigations of real algebraic varieties, discrete and computational geometry, and molecular chemistry. This research project is concerned with several central algorithmic problems in semi-algebraic geometry.The theoretical areas to be investigated consist of various algorithmic problems in semi-algebraic geometry, their connections with several important problems in discrete and computational geometry, as well as new applications of algorithmic semi-algebraic geometry to such areas as constraint databases and control theory. The practical goal is to build a system able to compute topological invariants (such as the number of connected components, the Euler characteristic, the Betti numbers, the full homology groups) of given semi-algebraic sets. Polynomial system solving is a basic step in the algorithms for computing higher topological invariants. Powerful multivariate polynomial system solvers have recently become available. These specialized systems are more efficient than what is available in standard computer algebra packages. However, there has not been any effort to compute more geometric properties, like the number of connected components, descriptions of each connected component, the homology groups etc. The algorithms for solving these problems are considerably more complicated than those for just testing emptiness of a semi-algebraic set. Routines will be adopted from existing state-of-the-art polynomial system solvers as building blocks towards developing a software package able to answer questions about connectivity and higher homologies of semi-algebraic sets.

近年来，算法半代数几何因其在机器人运动规划、几何建模、计算机辅助设计、几何定理证明、实代数簇的数学研究、离散和计算几何以及分子化学等领域的应用而受到广泛关注。 本研究项目涉及半代数几何中的几个核心算法问题。研究的理论领域包括半代数几何中的各种算法问题、它们与离散几何和计算几何中的几个重要问题的联系，以及算法半代数几何在约束数据库和控制理论等领域的新应用。实际目标是建立一个能够计算给定半代数集的拓扑不变量（例如连通分量数、欧拉特性、贝蒂数、全同调群）的系统。多项式系统求解是计算更高拓扑不变量的算法的基本步骤。强大的多元多项式系统求解器最近已上市。这些专用系统比标准计算机代数包中提供的系统更有效。 然而，还没有做出任何努力来计算更多的几何性质，例如连通分量的数量、每个连通分量的描述、同调群等。解决这些问题的算法比仅仅测试半代数集的空性的算法要复杂得多。将采用现有最先进的多项式系统求解器中的例程作为开发软件包的构建块，该软件包能够回答有关半代数集的连通性和更高同调性的问题。