Computational Algebraic Geometry

在理论计算机科学中，符号操作的一个新兴子领域是计算代数几何。研究者们已经开始使用算法设计和复杂性理论的技术来研究这一领域的各种问题。该项目将对已知算法进行复杂性分析，尝试设计更有效的算法，并研究下界。由于该领域的许多问题具有固有的高复杂性，因此并行性和随机化的使用变得非常重要。要研究的具体问题包括Grobner基理论、Wu算法和实代数变种的细胞分解算法（如Collins算法）。此外，将探讨机器人和计算几何的应用。该项目如果成功，将有助于找到比目前更复杂的几何计算任务更快的算法。应用包括机器人，计算机图形学，计算机辅助设计。

An emerging subarea of symbolic manipulation of interest in theoretical computer science is computational algebraic geometry. The investigators have begun to use the techniques of algorithmic design and complexity theory to study a variety of problems in this area. The project will perform complexity analysis of known algorithms, try to design more efficient algorithms and also investigate lower bounds. Since many of the problems in this area have inherently high complexity, the use of parallelism and randomization becomes important. Specific problems to be investigated include the theory of Grobner bases, Wu's algorithm and cell-decomposition algorithms (such as Collins') for real algebraic varieties. In addition, applications to robotics and omputational geometry will be explored. The project, if successful, will assist in finding faster algorithms for much more complex computational tasks in geometry than are currently possible. Applications include robotics, computer graphics, computer- aided design.