本文關鍵詞：基于稀疏插值的多項式代數算法及其應用

  更多相關文章： 隱函數插值 稀疏有理函數插值 稀疏多元多項式插值 結式消元 最大公因式 組合幾何優(yōu)化

【摘要】：多項式代數是一種基礎、典型的非線性代數,可以用來描述和處理各種非線性科學問題.多項式代數的經典內容在于建立存在性理論和方法,而非對具體代數與幾何對象進行構造性研究.因為后者需要涉及大量復雜的多項式運算,常常會超出傳統(tǒng)的紙上推演的可行范圍.多項式代數的研究向構造性和算法化轉變始于上個世紀60年代,從那時起,符號與代數計算的方法和軟件快速發(fā)展,在計算機上進行大規(guī)模多項式運算變得現實可行.雖然用符號方法處理代數問題可以得到精確的完備解,但往往計算量大、表達式龐雜,導致存儲空間增加,計算速度降低,因而遠遠達不到實際應用的需求.提出更高效的多項式代數算法,并用以有效解決各種理論和實際問題成了近年來多項式代數研究領域的主攻方向.稀疏插值是一種降低代數算法時間復雜度的有效方法,在結式計算、信號處理、壓縮感知、不確定性量化等領域都有廣泛應用.本文基于稀疏插值技術,研究了兩個典型的多項式代數問題:結式消元和最大公因式(GCD)計算,提出了基于隱函數插值的結式消元法和基于稀疏多元多項式插值的最大公因式計算方法,并將基于隱函數插值的結式消元法應用于一類復雜的組合幾何優(yōu)化問題的求解.本文的主要研究內容如下:●研究了隱函數插值問題,設計并實現了隱函數插值算法.給出了隱函數插值的定義和描述,將隱函數插值問題轉化為若干個多元有理函數插值問題,結合單變元有理函數插值和稀疏多元多項式插值恢復多元有理函數.針對單變元有理函數插值,采用了高概率算法結合提前終止技術的Cauchy插值法;針對稀疏多元多項式插值,采用了具有確定性多項式時間復雜度的Ben-Or/Tiwari算法.對于有理函數在零點無定義或退化情形,給出了有理函數分子或分母的常數項是否為零的一般性判別方法,并進行了相應的概率分析.●提出了基于隱函數插值的結式消元法,解決了純符號或數值計算無法處理的一類復雜的非線性多元多項式方程組的求解問題.首先基于兩個多元多項式的Sylvester結式,依次消去變元,并消去多余因子,通過給定某些變元的初始數值,結合消元過程構造單變元隱函數的黑盒,將結式消元問題轉化為隱函數插值問題,使用隱函數插值算法恢復多項式系統(tǒng)的結式.●將基于隱函數插值的結式消元法應用于一類復雜的組合幾何優(yōu)化問題的求解.包括橢圓上三點構成的三角形的最大周長問題、Morley三等分定理、三角形三邊上點構成的三角形最小周長問題.實驗表明針對復雜的多項式系統(tǒng)求解問題,基于隱函數插值的結式消元法比純符號消元更加有效.●研究了多元多項式最大公因式計算的稀疏插值算法.通過引入齊次變元,構造輔助多項式和轉換輔助多項式,正規(guī)化目標GCD.首先利用關于齊次變元的單變元GCD計算獲得目標GCD的稀疏結構,然后基于改進的Zippel算法或Ben-Or/Tiwari算法的稀疏多元多項式插值技術重建齊次變元的系數多項式,即月標GCD的各個齊次多項式.我們給出的插值算法不需要因式分解,對目標GCD的形式也不做任何限制.算法的復雜度與目標GCD的稀疏性及選擇的稀疏多元多項式插值算法相關.●為進一步降低隱函數插值法、基于隱函數插值的結式消元法及多元多項式最大公因式計算的稀疏插值算法的時間復雜度,應用了概率和隨機技術、模算術和有理向量恢復算法等.
【學位授予單位】：華東師范大學
【學位級別】：博士
【學位授予年份】：2017
【分類號】：O174.14

【相似文獻】

中國期刊全文數據庫 前10條

1 何月順;在有序表中搜索插值點[J];華東地質學院學報;1999年04期

2 李寧;三點插值參數估計法及其在生產中的應用[J];物理;1986年01期

3 徐慶榮;;曲線插值中步長的確定[J];武漢測繪學院學報;1983年01期

4 王翔;關于四次缺插值樣條函數[J];浙江大學學報;1985年02期

5 郭竹瑞,葉懋冬,黃達人;高次樣條循環(huán)插值的收斂階[J];數學年刊A輯(中文版);1985年02期

6 藺青沖 ,袁志范 ,葉文洪;一類對稱插值樣條和嚴格凸插值樣條[J];信陽師范學院學報(自然科學版);1991年04期

7 沈燮昌;復平面上Hermite插值多項式的同時逼近階[J];河南大學學報(自然科學版);1991年02期

8 汪嘉業(yè),張彩明;散亂空間數據點的插值[J];高校應用數學學報A輯(中文版);1987年04期

9 邱鈞,孫洪泉,韓偉;二元正態(tài)分布函數(Coons曲面法)插值研究[J];工程圖學學報;2002年03期

10 賈榮慶;Kergin插值算子的擴張[J];科學通報;1986年11期

中國重要會議論文全文數據庫 前3條

1 韓靖;韓旭里;;曲線插值的一種具有還圓性的細分方法[A];第五屆全國幾何設計與計算學術會議論文集[C];2011年

2 鄧四清;王平;謝進;;一類有理四次插值樣條曲線的形狀控制[A];第三屆和諧人機環(huán)境聯合學術會議（HHME2007）論文集[C];2007年

3 左小偉;王杰光;;改進Shepard插值無網格配點法[A];第17屆全國結構工程學術會議論文集（第Ⅰ冊）[C];2008年

中國博士學位論文全文數據庫 前4條

1 汪成峰;基于自適應關節(jié)權重和插值小波的體感動作評價方法研究[D];中國農業(yè)大學;2016年

2 唐敏;基于稀疏插值的多項式代數算法及其應用[D];華東師范大學;2017年

3 CAMARA AMARA;曲線曲面插值模型的研究[D];中南大學;2007年

4 高文武;擬插值的若干理論及其應用[D];復旦大學;2012年

中國碩士學位論文全文數據庫 前10條

1 趙菲;基于Peterson模型的京津冀地區(qū)AOD時空插值研究[D];河北師范大學;2016年

2 蔣磊;一類擬細分插值基函數的構造探究[D];浙江工商大學;2017年

3 錢昕f，

本文編號：1264881