基於數值方法的有理數域上準確多元多項式因式分解

《基於數值方法的有理數域上準確多元多項式因式分解》是依託電子科技大學,由馮勇擔任醒目負責人的面上項目。

基本介紹

• 中文名：基於數值方法的有理數域上準確多元多項式因式分解
• 依託單位：電子科技大學
• 項目類別：面上項目
• 項目負責人：馮勇

項目摘要

多項式的因式分解屬於代數計算中的核心部分。目前有理數域上的多項式準確因式分解主要採用符號計算的方法。符號計算的長處是計算結果準確和計算過程穩定，但不足之處是計算複雜度高，在實際套用中效率不高，只能解決中小規模問題。此外,由於目前流行的程式語言的編譯器都未提供符號計算的基本操作，故實現起來也比較複雜。本項目將系統地研究採用完全數值近似方法來準確分解有理數域上的多元多項式。特點為：要分解的多項式是準確的，分解出的因子也是準確的，而中間過程全部採用數值近似方法。這是一條全新的研究途徑，與符號方法相比，研究成果在目前的程式語言環境中易於實現。更重要的是，本項目還將對稀疏多項式的全數值分解方法進行深入研究，充分利用其稀疏特性，從而得到更高效的分解方法。我們近年的工作說明了這種構想是可能實現的，並有望取得突破。

結題摘要

多項式的因式分解是代數計算中的核心內容之一，它在方程化簡求解中起著重要作用。人們總是採用符號計算方法來獲得準確因式分解，採用數值計算來獲得近似因式分解。多項式的準確因式分解由於採用符號計算使得其分解的規模較小，在編程實現方面需要計算機代數系統作為支撐，然而，目前流行的程式語言標準都不含計算機代數系統，這使得因式分解不易於在工程計算中實現。數值計算的大規模、高效性以及易於在流行的程式語言環境中實現的優勢促使我們從事採用數值方法獲得準確因式分解方面的研究。在本項目的資助下，我們首先研究了從近似值獲得準確值的基礎算法，提出了增量的PSLQ算法，採用增量的PSLQ算法恢復準確的代數數時，比傳統的算法在計算複雜度方面降低了一個數量級；與同倫算法相結合，我們提出了全數值的準確因式分解算法，該算法在非稀疏的多項式分解方面，當因式分解的規模較小時，與目前的符號因式分解效率相當，當分解的規模較大時，全數值的因式分解算法優勢明顯；針對稀疏多項式因式分解的情形，我們將多項式的結構信息納入分解算法中，以Tateacki Sasaki算法為基礎，採用零誤差計算方法解決了初始因子的組合這一核心問題，同時改進了稀疏Hensel lifting算法，從而設計出了高效的稀疏多項式因式分解算法，我們算法與目前最新的算法相比，無論在分解的效率和規模方面都要好上成百上千倍。在此基礎上，我們從幾何角度研究分解問題，解決了數值實代數幾何計算的3個基本問題，我們提出的技術能夠成功地找到新的具有良好數值性態的witness point，該成果被國際期刊 Theoretical Computer Science接收。我們進一步研究數值因式分解的本質，給出了多元多項式數值因式分解的定義，並證明了其唯一性，該結果被數學領域SCI一區刊物 Foundation of Computational Mathematics接收。我們將以上成果套用到微分代數方程的化解和約簡上，申請了2項國家專利和獲得了一項國家軟體著作權。本項目發表論文15篇，出版專著2部，獲得中國科普作家協會金獎1項。在人才培養方面，參加該項目組的5名博士研究生和1名碩士研究生已全部畢業；項目組的成員都在國際國內重要學術會議和期刊任職。在該項目的資助下，項目組成員參加了國內國外各種學術會議，圓滿完成了本項目的研究內容，實現了本項目的研究目標。