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.

0133597Saugata Basu佐治亚理工学院职业：算法半代数几何及其应用算法半代数几何是计算机科学和数学几个不同领域中许多问题的核心，包括离散和计算几何、机器人运动规划、几何建模、计算机辅助设计、几何定理证明、实代数簇的数学研究、分子化学、约束数据库等。一个密切相关的学科领域是定量实数代数几何。定量实代数几何的结果是半代数几何中更好算法的基本成分，并且在计算机科学的其他几个领域中发挥着越来越重要的作用：例如，在限制计算几何排列的几何复杂性、计算学习理论、证明计算复杂性理论、凸优化问题等的下界。该项目的首要目标是为半代数几何的几个重要问题设计优化算法，包括计算同调群和半代数分层问题其次，算法实代数几何的方法和技术将应用于研究离散几何和计算几何中的几个开放问题，并探索新的联系，特别是在计算拓扑领域。 同时，将研究算法半代数几何的几个新兴应用，特别是在约束数据库领域。此外，还将进行实际实现，以构建能够计算拓扑不变量（例如数给定半代数集的连通分量、欧拉特征、贝蒂数、全同调群）。此举旨在缩小目前理论上最佳算法与最佳实际实现之间的差距。该项目的教育部分包括开发适合数学和计算机领域高年级本科生和初级研究生的综合跨学科课程科学。 除了大学水平的微积分和线性代数之外，这不需要任何先决条件，这样学生就可以快速吸收这一研究领域所需的数学背景，同时能够进行有效的实施，这将使该问题对工业界和学术界都有吸引力。