计算特征列的高效算法研究

Algorithms for computing characteristic sets are primary tools of solving polynomial equations via symbolic computation, which have been well applied in various fields, such as computational algebraic geometry, robot control, computer vision, computer aided geometry design, and verification of large scale integrated circuits. Thus, from theoretical and practical viewpoints, it is important to improve the efficiency of current algorithms for computing characteristic sets and simplify their outputs. In this project, we mainly focus on designing efficient algorithms for computing characteristic sets of polynomial systems over real number and finite fields, developing a related software package with Maple, and using it to solve practical problems in science and engineering.. In detail, basing on preliminary work, we will generalize the concept of characteristic set and design a more flexible algorithmic scheme for computing characteristic sets. More kinds of efficient polynomial reductions would be proposed, such as reductions based on Bézout resultant, Dixon resultant, Macaulay resultant and techniques in linear algebra. In addition, we will perform sufficient computation experiments and then finely redesign the strategy of choosing reductions, which have a major influence on the efficiency of our algorithms.

特征列算法是通过符号计算求解多项式方程组的主要工具，已广泛应用于计算代数几何、机器人控制、计算机视觉、计算机辅助几何设计、大型集成电路验证等领域。提高现有特征列算法的计算效率并简化其计算结果具有重要的理论和实际意义。在本项目中，我们将集中研究实数域上和有限域上多项式系统的特征列计算的高效算法，开发相关Maple软件包，并将其用于解决实际的科学和工程问题。. 具体地说，在前期工作的基础上，我们将继续推广特征列的概念并设计更灵活的特征列计算框架。引入更多种类的高效多项式约化，如使用Bézout结式、Dixon结式以及Macaulay结式等经典的消元工具来约化多项式，并尝试使用线性代数技术。另外，我们将对约化的选择策略进行充分的实验以及更细致的设计，该策略对于算法效率具有重要影响。

本项目原定的研究计划为: 设计多项式系统的三角分解 (如特征列分解) 的高效算法, 开发相关 Maple 软件包, 并将其用于解决实际的科学和工程问题. 经过深入研究, 项目团队以域的 Descartes 积上多项式的伪无平方分解算法为基础给出了计算正则系统零点重数的高效算法, 此算法还能用于分析零点的重数结构. 此外, 我们还将多项式系统的三角分解算法应用于经济和控制领域, 解决了一些实际问题: 包括半代数模型的多均衡检测以及多项式动态系统的时间最优控制等...项目进行期间, 项目负责人发表 SCI 索引论文两篇.