CAREER: Algorithmic Semi-Algebraic Geometry and Its Applications

职业：算法半代数几何及其应用

• 批准号: 0133597
• 负责人: Saugata Basu
• 金额: $ 33.3万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-06-15 至 2007-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0133597&HistoricalAwards=false
• 关键词: CAREER; Algorithmic; Semi; Algebraic; Geometry

0133597Saugata BasuGeorgia TechCAREER: Algorithmic Semi-algebraic Geometry and its ApplicationsAlgorithmic semi-algebraic geometry lies at the heart of of many problems in several different areas of computer science and mathematics including discrete and computational geometry, robot motion planning, geometric modeling, computer-aided design, geometric theorem proving, mathematical investigations of real algebraic varieties, molecular chemistry, constraint databases etc. A closely related subject area is quantitative real algebraic geometry. Results from quantitative real algebraic geometry are the basic ingredients of better algorithms in semi-algebraic geometry and play an increasingly important role in several other areas of computer science: for instance, in bounding the geometric complexity of arrangements in computational geometry, computational learning theory, proving lower bounds in computational complexity theory, convex optimization problems etc.The first goal of this project is to design optimal algorithms for several important problems of semi-algebraic geometry including the problems of computing the homology groups and stratifications of semi-algebraic sets.Secondly, the methods and techniques of algorithmic real algebraic geometry will be applied to investigate several open problems in discrete and computational geometry and to explore new connections, especially in the area of computational topology. At the same time, several emerging applications of algorithmic semi-algebraic geometry will be investigated, especially in the area of constraint databases.Additionally, practical implementations will be undertaken, in order 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. This will aim at bridging the current gap between the theoretically best algorithms, and the best practical implementations available.The educational component of the project consists of developing an integrated cross-disciplinary curriculum suitable for advanced under-graduate and beginning graduate students in mathematics and computer science. This would require no pre-requisite beyond college-level calculus and linear algebra, so that that the students can quickly absorb the mathematical background necessary for this line of research, and at the same time be in a position to make efficient implementations, which would make themattractive to both industry and academia.

0133597 Saugata BasuGeorgia TechCAREER：数学半代数几何及其应用数学半代数几何是计算机科学和数学的几个不同领域中许多问题的核心，包括离散和计算几何，机器人运动规划，几何建模，计算机辅助设计，几何定理证明，真实的代数簇的数学研究，分子化学，约束数据库等。一个密切相关的主题领域是定量真实的代数几何。从定量真实的代数几何的结果是半代数几何中更好的算法的基本成分，并且在计算机科学的其他几个领域中发挥着越来越重要的作用：例如，在计算几何学、计算学习理论中界定排列的几何复杂性，在计算复杂性理论中证明下界，凸优化问题等。本项目的第一个目标是设计半代数几何中几个重要问题的优化算法，包括计算半代数集的同调群和分层问题。其次，算法真实的代数几何的方法和技术将被应用于研究离散和计算几何中的几个开放问题，并探索新的连接，特别是在计算拓扑学领域。 同时，将研究算法半代数几何的几个新兴应用，特别是在约束数据库领域，并将进行实际实现，以建立一个能够计算给定半代数集的拓扑不变量（如连通分支数，Euler特征，Betti数，全同调群）的系统。这将旨在弥合理论上最好的算法之间的差距，最好的实际实现available.The教育部分的项目包括开发一个综合的跨学科课程，适用于先进的本科生和开始研究生在数学和计算机科学。 这将不需要任何先决条件超越大学水平的微积分和线性代数，使学生可以快速吸收必要的数学背景，这条线的研究，并在同一时间能够作出有效的实施，这将使他们有吸引力的工业界和学术界。