多項式系統求解中奇異點問題的理論與算法研究

《多項式系統求解中奇異點問題的理論與算法研究》是依託天津大學，由李楠擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：多項式系統求解中奇異點問題的理論與算法研究
• 項目類別：青年科學基金項目
• 項目負責人：李楠
• 依託單位：天津大學

項目摘要

奇異點問題是多項式系統求解中最具挑戰性的問題之一，在計算機輔助幾何設計和多項式最佳化等許多相關領域中有著廣泛的套用。本項目將針對這一問題開展理論與算法研究，所涉及的內容包括：改進的收縮方法、改進的臨界點方法、正維系統的歐氏距離次數、算法的複雜度分析和閾值的自動控制等。本項目將致力於分析與解決多項式系統求解中與奇異點相關的若干理論問題，設計並實現高效、魯棒的零維系統奇異解的精化與驗證算法和求解正維系統的符號數值混合算法。科學與工程計算中出現的很多數學問題都可以歸結為多項式系統求解問題，奇異點的識別與處理是其中的重點和難點。本項目的研究不僅對多項式系統求解中的奇異點問題，對其他研究領域中的相關問題（如計算隱式曲線曲面的拓撲和實半代數集的凸包等）的發展也有著重要的意義。

結題摘要

多項式系統孤立解的零點隔離和可信驗證是計算數學中的重要問題。Smale（菲爾茲獎得主）等人提出的阿爾法理論成功解決了非奇異解的零點隔離和可信驗證問題。隨後，Dedieu和Shub又成功解決了簡單二重根的零點隔離與可信驗證問題。本項目立項時國內外尚無關於更一般孤立奇異解的理論結果。本項目遵照研究計畫，研究了多項式系統求解中的奇異解問題，特別是孤立奇異解的零點隔離和可信驗證問題，以及代數系統求解方法在計算機視覺中的套用。具體來說，本項目完成了三方面的工作：首先，我們將關於非奇異解和簡單二重根的零點隔離與可信驗證的結果推廣至任意重數的簡單重根情形，並給出了相應符號數值算法的實現；其次，我們將上述結果進一步推廣至收縮方法單次終止情形，並給出了其重數的下界和相應符號數值算法的實現；最後，我們將參數系統符號求解套用於圖像拼接問題，取得了不錯的實驗結果。總體來說，本項目基本完成了研究目標。