Computational Algebraic Geometry

点击翻译按钮获取中文摘要

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.