Design, Analysis & Applications of Algorithms for Solving Systems of Polynomial Equations & Related Problems

本项目将探索符号代数计算中的几个基本算法问题，并研究它们在几何建模中的应用。该项目的总体目标是设计、分析和测试用于求解多项式方程组和相关问题的高效算法，并测试其对几何建模问题的适用性。要研究的具体问题领域是：分析求解多项式方程组的算法，如Wu-Ritt特征集算法和Lazard三角集算法；开发这些算法和其他算法的变体，以有效地处理特别感兴趣的多项式方程组；设计了基于Grobner基的高效新算法和用于多项式理想运算的新的基转换算法；研究了一般Dixon结式的性质和计算它的算法；并探索了这些技术在解决几何建模中的算法问题中的应用。各种算法的设计和分析将伴随着在现有计算机代数系统上进行试验和试行实现。实验的目的将是纳入分析提出的可能的改进建议，并揭示分析中可能遗漏的现象。还计划对一些特殊用途的算法进行微调实现。

This project will explore several basic algorithmic questions in symbolic algebraic computation and investigate their applications to geometric modeling. The overall goal of the project is to design, analyze and test efficient algorithms for solving systems of polynomial equations and related problems, and to test their applicability to geometric modeling problems. The specific problem areas to be studied are: analysis of algorithms for solving system of polynomial equations such as the Wu-Ritt characteristic set algorithm and Lazard's triangular set algorithm; developing variations of these and other algorithms to efficiently handle systems of polynomial equation of special interest; designing efficient new algorithms based on Grobner bases and a new basis conversion algorithm for manipulation of polynomial ideals; investigation of the properties of the general Dixon resultant and algorithms for computing it; and exploration of the use of these techniques in solving algorithmic problems in geometric modeling. The design and analysis of the various algorithms will be accompanied by experimentation with trial implementations on existing computer algebra systems. The aim of the experimentation will be to incorporate possible improvements suggested by the analysis and to uncover phenomena that might possibly be missed out in the analysis. Fine tuned implementations of a few special purpose algorithms are also planned.