近期，我院魯東副教授最新研究成果發(fā)表在符號計算領(lǐng)域權(quán)威期刊《Journal of Symbolic Computation》上。魯東副教授為該論文第一作者，合作者包括中國科學(xué)院系統(tǒng)所的王定康研究員、湖南師范大學(xué)的肖方慧老師和汕頭大學(xué)的鄭曉鵬老師?！禞ournal of Symbolic Computation》是由歐洲科學(xué)院院士Bruno Buchberger教授于1985年創(chuàng)辦的符號計算領(lǐng)域的權(quán)威期刊，我國著名數(shù)學(xué)家吳文俊院士曾擔(dān)任該期刊的第一屆編委。該雜志涉及的研究領(lǐng)域包括計算代數(shù)、計算幾何（非線性）、符號計算語言和系統(tǒng)的設(shè)計與實(shí)現(xiàn)等。目前該期刊是中國數(shù)學(xué)會推薦的T2期刊。
圖1 論文發(fā)表首頁
科學(xué)與工程領(lǐng)域中的大量理論和實(shí)際問題均可化歸為多項式系統(tǒng)求解問題，比如幾何定理機(jī)器證明、破解著名的AES-128加密體制等。目前，多項式系統(tǒng)的求解方法分為數(shù)值方法、符號方法以及符號—數(shù)值混合方法，不同的方法適用于不同的實(shí)際問題，比如密碼攻擊問題只適合用符號方法進(jìn)行求解?；诜柗椒ㄔ诿艽a分析、幾何建模等領(lǐng)域發(fā)揮的重要作用，本文重點(diǎn)關(guān)注如何設(shè)計高效的多項式系統(tǒng)符號求解方法。
2002年，法國計算機(jī)科學(xué)家J.-C. Faugère教授從如何減少冗余計算的角度出發(fā)，基于簽名技術(shù)提出了著名的F5算法，并成功攻破了HFE密碼系統(tǒng)。然而，F(xiàn)5算法的理論復(fù)雜且算法終止性存在問題。2011年，中國科學(xué)院信息工程研究所王明生研究員與美國克萊姆森大學(xué)S. Gao教授等人提出了基于簽名技術(shù)的GVW算法。相較于F5算法，GVW算法的理論更加簡潔明了，且保證了算法的終止性。在交換代數(shù)中，有時需要考慮不同環(huán)中多項式系統(tǒng)的求解問題，比如代數(shù)簇的奇點(diǎn)消解問題。因此，符號計算領(lǐng)域中的眾多學(xué)者開始研究如何設(shè)計局部環(huán)上的簽名標(biāo)準(zhǔn)基算法，但始終無法解決算法終止性問題。
基于GVW算法的框架，魯東老師與合作者利用推廣的Mora范式算法克服無限集合沒有極小元的困難，給出任意半群序下的簽名標(biāo)準(zhǔn)基算法，首次從理論上證明算法的正確性和終止性。該簽名標(biāo)準(zhǔn)基算法是多項式環(huán)上GVW算法的進(jìn)一步推廣，它適用于所有的項序，包括全局序、局部序和混合序，使得在任何情形下均可使用該算法進(jìn)行多項式系統(tǒng)的高效求解。匿名評審人評價“this work is a leap forward in signature Gr?bner bases”。
圖 2 任意半群序下的簽名標(biāo)準(zhǔn)基算法
該研究受到國家重點(diǎn)研發(fā)計劃（No.: 2020YFA0712300）、國家自然科學(xué)基金（Nos.: 12171469, 12201210, 12001030）、四川省自然科學(xué)基金（No.: 2024NSFSC0418）以及中央高?；究蒲袠I(yè)務(wù)費(fèi)（No.: 2682024ZTPY052）等項目的資助。
原文鏈接:
https://www.sciencedirect.com/science/article/pii/S0747717124000749
