基于数值方法的有理数域上准确多元多项式因式分解

多项式的因式分解属于代数计算中的核心部分。目前有理数域上的多项式准确因式分解主要采用符号计算的方法。符号计算的长处是计算结果准确和计算过程稳定，但不足之处是计算复杂度高，在实际应用中效率不高，只能解决中小规模问题。此外,由于目前流行的编程语言的编译器都未提供符号计算的基本操作，故实现起来也比较复杂。本项目将系统地研究采用完全数值近似方法来准确分解有理数域上的多元多项式。特点为：要分解的多项式是准确的，分解出的因子也是准确的，而中间过程全部采用数值近似方法。这是一条全新的研究途径，与符号方法相比，研究成果在目前的编程语言环境中易于实现。更重要的是，本项目还将对稀疏多项式的全数值分解方法进行深入研究，充分利用其稀疏特性，从而得到更高效的分解方法。我们近年的工作说明了这种设想是可能实现的，并有望取得突破。

多项式的因式分解是代数计算中的核心内容之一，它在方程化简求解中起着重要作用。人们总是采用符号计算方法来获得准确因式分解，采用数值计算来获得近似因式分解。多项式的准确因式分解由于采用符号计算使得其分解的规模较小，在编程实现方面需要计算机代数系统作为支撑，然而，目前流行的编程语言标准都不含计算机代数系统，这使得因式分解不易于在工程计算中实现。数值计算的大规模、高效性以及易于在流行的编程语言环境中实现的优势促使我们从事采用数值方法获得准确因式分解方面的研究。在本项目的资助下，我们首先研究了从近似值获得准确值的基础算法，提出了增量的PSLQ算法，采用增量的PSLQ算法恢复准确的代数数时，比传统的算法在计算复杂度方面降低了一个数量级；与同伦算法相结合，我们提出了全数值的准确因式分解算法，该算法在非稀疏的多项式分解方面，当因式分解的规模较小时，与目前的符号因式分解效率相当，当分解的规模较大时，全数值的因式分解算法优势明显；针对稀疏多项式因式分解的情形，我们将多项式的结构信息纳入分解算法中，以Tateacki Sasaki算法为基础，采用零误差计算方法解决了初始因子的组合这一核心问题，同时改进了稀疏Hensel lifting算法，从而设计出了高效的稀疏多项式因式分解算法，我们算法与目前最新的算法相比，无论在分解的效率和规模方面都要好上成百上千倍。在此基础上，我们从几何角度研究分解问题，解决了数值实代数几何计算的3个基本问题，我们提出的技术能够成功地找到新的具有良好数值性态的witness point，该成果被国际期刊 Theoretical Computer Science接收。我们进一步研究数值因式分解的本质，给出了多元多项式数值因式分解的定义，并证明了其唯一性，该结果被数学领域SCI一区刊物 Foundation of Computational Mathematics接收。我们将以上成果应用到微分代数方程的化解和约简上，申请了2项国家专利和获得了一项国家软件著作权。本项目发表论文15篇，出版专著2部，获得中国科普作家协会金奖1项。在人才培养方面，参加该项目组的5名博士研究生和1名硕士研究生已全部毕业；项目组的成员都在国际国内重要学术会议和期刊任职。在该项目的资助下，项目组成员参加了国内国外各种学术会议，圆满完成了本项目的研究内容，实现了本项目的研究目标。