多项式系统求解中奇异点问题的理论与算法研究

A main challenge in polynomial systems solving is to identify and tackle singular points, which naturally occur in CAGD (computer aided geometric design) and polynomial optimization. This project aims to contribute to this problem by developing new theories and new algorithms on singular points in polynomial systems solving. Project subjects include: improvements of the deflation method and the critical points method, the Euclidean distance degree of positive-dimensional systems, complexity analysis and automatic threshold control in algorithms and etc. Project goals are twofold: the first goal is to analyze and solve some theoretic problems related to singular points in polynomial systems solving; the second goal is to develop and implement efficient and robust algorithms used to refine and certify singular solutions of zero-dimensional systems and to solve positive-dimensional systems. Polynomial systems naturally arise in many areas from science and engineering. Furthermore, singular solutions to these systems are often of particular interest to researchers. The new theory established will provide a more explicit description of singular points in polynomial systems solving, and the new algorithms developed will allow a broad range of scientists and engineers, who encounter polynomial systems to compute their singular solutions which are beyond the reach of current solving techniques.

奇异点问题是多项式系统求解中最具挑战性的问题之一，在计算机辅助几何设计和多项式优化等许多相关领域中有着广泛的应用。本项目将针对这一问题开展理论与算法研究，所涉及的内容包括：改进的收缩方法、改进的临界点方法、正维系统的欧氏距离次数、算法的复杂度分析和阈值的自动控制等。本项目将致力于分析与解决多项式系统求解中与奇异点相关的若干理论问题，设计并实现高效、鲁棒的零维系统奇异解的精化与验证算法和求解正维系统的符号数值混合算法。科学与工程计算中出现的很多数学问题都可以归结为多项式系统求解问题，奇异点的识别与处理是其中的重点和难点。本项目的研究不仅对多项式系统求解中的奇异点问题，对其他研究领域中的相关问题（如计算隐式曲线曲面的拓扑和实半代数集的凸包等）的发展也有着重要的意义。

多项式系统孤立解的零点隔离和可信验证是计算数学中的重要问题。Smale（菲尔兹奖得主）等人提出的阿尔法理论成功解决了非奇异解的零点隔离和可信验证问题。随后，Dedieu和Shub又成功解决了简单二重根的零点隔离与可信验证问题。本项目立项时国内外尚无关于更一般孤立奇异解的理论结果。本项目遵照研究计划，研究了多项式系统求解中的奇异解问题，特别是孤立奇异解的零点隔离和可信验证问题，以及代数系统求解方法在计算机视觉中的应用。具体来说，本项目完成了三方面的工作：首先，我们将关于非奇异解和简单二重根的零点隔离与可信验证的结果推广至任意重数的简单重根情形，并给出了相应符号数值算法的实现；其次，我们将上述结果进一步推广至收缩方法单次终止情形，并给出了其重数的下界和相应符号数值算法的实现；最后，我们将参数系统符号求解应用于图像拼接问题，取得了不错的实验结果。总体来说，本项目基本完成了研究目标。