《結構化多項式系統的三角化求解方法研究》是依託北京航空航天大學，由牟晨琪擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：結構化多項式系統的三角化求解方法研究
- 依託單位：北京航空航天大學
- 項目負責人：牟晨琪
- 項目類別：青年科學基金項目
項目摘要,結題摘要,
項目摘要
許多科學和工程領域中的實際問題均可由多項式系統描述，而這些多項式系統通常會顯示出稀疏性等特定結構。本項目研究求解結構化多項式系統的三角列方法，包括其理論、算法、實施與套用。這既是符號計算領域中的重要理論問題，也在密碼學和生物學等若干領域中具有廣闊的套用前景。首先，本項目擬利用線性代數和圖論中的方法和工具來設計針對稀疏多項式系統的高效三角化求解方法，並通過最佳化和再實現現有程式、選用最優的數據結構和進行並行計算的方式對所設計的算法進行高效的程式實現。其次，本項目擬分析和歸納密碼學、編碼理論和生物學等領域的實際問題中具有普遍性的典型結構化多項式系統，在此基礎上設計專用算法並將其用於解決相應的實際問題。. 本項目的研究特色包括首次系統地研究利用多項式系統的特定結構對三角列方法進行最佳化、將線性代數工具引入三角列方法研究以及歸納實際問題中具有普遍性的多項式系統結構等。
結題摘要
多項式系統求解是計算代數幾何領域的一個核心研究問題，而三角列方法是對多項式系統進行符號求解的主流工具之一。在三角列方法在生物學與密碼學等領域的實際套用中，具有特定結構的多項式系統時常出現，且其規模超過一般三角分解算法的求解能力。因此，研究面向具有特定結構的多項式組的三角列方法並設計專用的三角分解算法是提高結構化多項式系統求解效率的關鍵途徑，具有重要的理論與實際意義。本項目的主要研究內容是面向結構化多項式系統的三角分解的理論與程式實現及其在來源於生物學等實際問題中的結構化多項式系統求解中的套用。圍繞著項目的研究目標，遵循項目的研究計畫，本項目開展了結構化多項式系統三角分解方面的理論研究、算法設計、程式實現與套用等方面的工作，主要取得了如下研究成果： （1）利用多項式的關聯圖給出了多項式系統關於變元的稀疏度描述，研究了針對多項式組弦圖結構的三角分解算法的內在結構，設計了面向變元稀疏的多項式組的特定三角分解算法。（2）在研究字典序Groebner基的內在結構及其與三角列的聯繫的基礎上，提出了包含字典序Groebner基與特徵三角列的特徵對的概念，設計與實現了將任意多項式組分解為特徵對的特徵分解算法。（3）研究了Groebner基換序算法中乘法矩陣的稀疏性，並利用這種稀疏性設計了將分次逆字典序Groebner基換序至字典序的稀疏FGLM算法。（4）更新、擴展與最佳化了三角分解軟體包Epsilon，添加了有限域上三角分解的算法與特徵分解算法，並將該軟體包升級至1.0版本。（5）研究了符號計算方法在生物學與系統控制理論中的套用，例如，利用符號計算方法分析了余維數為2的高維離散生物系統的穩定性。本項目已在《Journal of Symbolic Computation》、《Applied Mathematics and Computation》、《Neurocomputing》等國際期刊與CASC 2017、ISSAC 2017等國內外學術會議上發表學術論文8篇，其中SCI論文5篇、EI論文2篇。在本項目的支持下，負責人作為程式委員會成員參與組織國際國內學術會議共4次，參加國內外學術會議共6次並做學術報告，協助培養博士生3名、碩士生6名。
