本文關(guān)鍵詞：基于稀疏插值的多項式代數(shù)算法及其應(yīng)用

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

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

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

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

2 李寧;三點插值參數(shù)估計法及其在生產(chǎn)中的應(yīng)用[J];物理;1986年01期

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

4 王翔;關(guān)于四次缺插值樣條函數(shù)[J];浙江大學(xué)學(xué)報;1985年02期

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

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

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

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

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

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

中國重要會議論文全文數(shù)據(jù)庫 前3條

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

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

3 左小偉;王杰光;;改進Shepard插值無網(wǎng)格配點法[A];第17屆全國結(jié)構(gòu)工程學(xué)術(shù)會議論文集（第Ⅰ冊）[C];2008年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前4條

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

2 唐敏;基于稀疏插值的多項式代數(shù)算法及其應(yīng)用[D];華東師范大學(xué);2017年

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

4 高文武;擬插值的若干理論及其應(yīng)用[D];復(fù)旦大學(xué);2012年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

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

2 蔣磊;一類擬細分插值基函數(shù)的構(gòu)造探究[D];浙江工商大學(xué);2017年

3 錢昕f，

本文編號：1264881