確定性稀疏多元多項(xiàng)式插值算法的分析與實(shí)現(xiàn)

張永燊 韋鵬 呂少梅 王筱婷

摘? 要：文章介紹了經(jīng)典多元多項(xiàng)式插值算法及Ben-Or/Tiwari算法，在Matlab及Maple環(huán)境下實(shí)現(xiàn)了相應(yīng)算法，給出了測試用例，對兩種算法的CPU運(yùn)行時(shí)間進(jìn)行了比較，并將Ben-Or/Tiwari算法在有限域和非有限域下進(jìn)行了實(shí)現(xiàn)。通過實(shí)驗(yàn)充分證明Ben-Or/Tiwari算法可以解決較大規(guī)模的多項(xiàng)式插值問題，而且在有限域下該算法更為有效。

關(guān)鍵詞：稀疏多元多項(xiàng)式;多元多項(xiàng)式插值;Ben-Or/Tiwari算法;有限域;非有限域

中圖分類號：TP301.6，O241.3 文獻(xiàn)標(biāo)識碼：A? 文章編號：2096-4706（2020）17-0096-03

Abstract：This paper introduces the classic multivariate polynomial interpolation algorithm and the Ben-Or/Tiwari algorithm. The corresponding algorithm is implemented in the Matlab and Maple environment，and test cases are given. The CPU running time of the two algorithms is compared，and the Ben-Or/Tiwari algorithm is implemented in finite and non-finite fields. The experiment fully proves that the Ben-Or/Tiwari algorithm can solve large-scale polynomial interpolation. Problem，and the algorithm is more effective in a finite field.

Keywords：sparse multivariate polynomial;multivariate polynomial interpolation;Ben-Or/Tiwari algorithm;finite field;non-finite field

0? 引? 言

科學(xué)研究和實(shí)際應(yīng)用領(lǐng)域中有許多來源于復(fù)雜系統(tǒng)的輸入輸出或算法構(gòu)造的函數(shù)，它們往往容易求值卻不易獲得精確的數(shù)學(xué)表達(dá)式。這種數(shù)學(xué)表達(dá)式一般可以表達(dá)為這樣的形式：令p是一個(gè)素?cái)?shù)，f∈Zp（x1，x2，…，xn）是一個(gè)包含t（t>0）個(gè)非零項(xiàng)，用黑盒B：→?p表示的多元多項(xiàng)式。稀疏插值是重建此類黑盒函數(shù)的有效策略，特別是在計(jì)算機(jī)代數(shù)中，存在基于稀疏多元多項(xiàng)式插值的眾多有效算法。

稀疏插值被廣泛應(yīng)用在數(shù)學(xué)和數(shù)值領(lǐng)域[1，2]及科學(xué)和工程領(lǐng)域[3]，如指數(shù)分析、廣義特征值問題、符號計(jì)算、信號處理等。將多元多項(xiàng)式表示為t個(gè)互不相同的單項(xiàng)式求和的形式，該多元多項(xiàng)式稱為t稀疏多元多項(xiàng)式。稀疏插值的目標(biāo)是通過較少的賦值次數(shù)（黑盒插值點(diǎn)），采用較低的時(shí)間復(fù)雜度，恢復(fù)多元多項(xiàng)式。

衡量插值算法的實(shí)用性，往往關(guān)注于算法的時(shí)間效率與空間效率，即：是否可通過較短的CPU運(yùn)行時(shí)間對黑盒多項(xiàng)式進(jìn)行恢復(fù);算法是否對所需插值點(diǎn)要求嚴(yán)格以及所需插值點(diǎn)數(shù)量是否較少;在有限域及非有限域上，算法是否具有局限性等。與傳統(tǒng)稠密多元多項(xiàng)式插值算法（如牛頓插值法）不同，針對多元多項(xiàng)式稀疏性的特點(diǎn)，稀疏多元多項(xiàng)式插值算法在解決此類問題時(shí)，往往更為實(shí)用。

1979年Zippel[4，5]提出了第一個(gè)用于求解GCD問題的概率性稀疏多元多項(xiàng)式插值算法，它是第一個(gè)具有多項(xiàng)式時(shí)間復(fù)雜度的算法。Zippel算法是許多主流的計(jì)算機(jī)代數(shù)系統(tǒng)中計(jì)算整系數(shù)多元多項(xiàng)式GCD的主要方法。1988年，Ben-Or和Tiwari提出了一個(gè)確定性稀疏插值算法[6]，多項(xiàng)式系數(shù)可為整數(shù)，有理數(shù)，實(shí)數(shù)或是復(fù)數(shù)。

本文為國家級大學(xué)生創(chuàng)新訓(xùn)練計(jì)劃項(xiàng)目相關(guān)課題，作者旨在研究Ben-Or/Tiwari算法與經(jīng)典多項(xiàng)式插值算法的區(qū)別，主要讀者對象為對插值問題有一定學(xué)習(xí)和了解的讀者。本文在第1節(jié)和第2節(jié)中對經(jīng)典的多元多項(xiàng)式插值算法（直接法）和Ben-Or/Tiwari算法進(jìn)行了介紹，第3節(jié)給出了直接法和Ben-Or/Tiwari算法的算法運(yùn)行時(shí)間進(jìn)行了對比，并且設(shè)計(jì)相應(yīng)數(shù)值實(shí)驗(yàn)，分別在有限域和非有限域下對確定性稀疏多元多項(xiàng)式插值算法——Ben-Or/Tiwari算法進(jìn)行了實(shí)現(xiàn)，進(jìn)行了相應(yīng)的對比分析。

1? 稠密多元多項(xiàng)式插值算法

2.1? 非有限域下Ben-Or/Tiwari算法

結(jié)合上述Ben-Or/Tiwari算法的詳細(xì)過程，可將非有限域下Ben-Or/Tiwari算法細(xì)致分為八個(gè)步驟：

2.2? 有限域下Ben-Or/Tiwari算法

在2.1算法的基礎(chǔ)上，對函數(shù)求值、求λ、構(gòu)造函數(shù)求根和對根進(jìn)行范德蒙行列式排列的時(shí)候，進(jìn)行取模運(yùn)算，降低矩陣元素的數(shù)值大小。

3? 數(shù)值實(shí)驗(yàn)

對直接法和Ben-Or/Tiwari算法及其拓展與優(yōu)化進(jìn)行兩兩性能比較。直接法的編程環(huán)境為Matlab 2015，Ben-Or/Tiwari算法的編程環(huán)境為Maple 2018。注意兩個(gè)程序都是順序執(zhí)行，在確定變元X1，X2，…，Xn的次數(shù)時(shí)未并行化。本章給出了3組測試集的性能比較結(jié)果，使用的多項(xiàng)式都是隨機(jī)生成的，比較的對象為CPU運(yùn)行時(shí)間。黑盒中的多元多項(xiàng)式系數(shù)取自?p，其中p=100。

3.1? 測試集#1

本組測試集為2個(gè)變元3次多元多項(xiàng)式，項(xiàng)數(shù)t=3，次數(shù)從3變化到4。將直接法與有限域上的Ben-Or/Tiwari算法性能與時(shí)間做比較。

本組問題集包含2個(gè)變元的3次多元多項(xiàng)式，多項(xiàng)式的通項(xiàng)為冪級數(shù)排列，其中最多項(xiàng)數(shù)為dn=16。取項(xiàng)數(shù)t=4，所以令多元多項(xiàng)式P=x13-3x12x2+3x1x22-x23。通過Matlab求解可得到表1系數(shù)對應(yīng)表，原多元多項(xiàng)式的系數(shù)矩陣剛好匹配。其中ai，i=0，1，2，…，15為各待求多項(xiàng)式的系數(shù)，共有dn=16項(xiàng)。

記錄每個(gè)多項(xiàng)式在兩種算法下的運(yùn)行時(shí)間（s），如表2所示。表頭第1列d表示最高項(xiàng)的次數(shù);第2列t表示項(xiàng)數(shù)。

從表2可以看出，Ben-Or/Tiwari算法比直接法耗時(shí)更短，且隨著次數(shù)的增加，兩種算法的執(zhí)行時(shí)間也隨之增加，但Ben-Or/Tiwari算法對次數(shù)變化不敏感。

3.2? 測試集#2

本組測試集通過物理學(xué)上的控制單一變量法，分別固定了多元多項(xiàng)式的次數(shù)、變元、項(xiàng)數(shù)，然后對其他的變量進(jìn)行有規(guī)律的窮舉，得到不同域上的算法時(shí)間復(fù)雜度。

通過表3可以看出，在固定次數(shù)的基礎(chǔ)上改變它的變元個(gè)數(shù)及項(xiàng)數(shù)，兩種數(shù)域下的時(shí)間復(fù)雜度都會(huì)提升，而有限域比非有限域的提升速度較慢，所以有限域在一定程度上較非有限域受到的影響更小。

通過表4可以看出，在固定變元的基礎(chǔ)上改變多元多項(xiàng)式的另外兩個(gè)變量時(shí)，仍是有限域與非有限域的時(shí)間復(fù)雜度均有提升，但有限域?qū)ψ兞康母淖兏幻舾小?/p>

通過表5可以看出，在固定項(xiàng)數(shù)的基礎(chǔ)上改變多元多項(xiàng)式的另外兩個(gè)變量時(shí)，與表3和表4的有限域與非有限域的時(shí)間復(fù)雜度均有提升有差別，此時(shí)有限域的時(shí)間復(fù)雜度保持不變，而非有限域的時(shí)間復(fù)雜度先上升后下降最后保持不變，造成這樣結(jié)果的原因是：在有限域的算法上對矩陣上的元素都進(jìn)行了取模運(yùn)算，保證了取模后的元素都在一定范圍內(nèi)，而非有限域上的元素是沒有限制的，因此在求解矩陣的運(yùn)算時(shí)，耗費(fèi)的時(shí)間大。所以當(dāng)變元的次數(shù)、變元的個(gè)數(shù)已以遞增的形式變化時(shí)，非有限域上的算法運(yùn)算度以指數(shù)級增大。

4? 結(jié)? 論

本文介紹了經(jīng)典的多元多項(xiàng)式插值算法（直接法），并給出了有限域上、非有限域上求解稀疏多元多項(xiàng)式插值算法。其中直接法可以解決小變元、小次數(shù)的多元多項(xiàng)式的插值，但是當(dāng)其變元次數(shù)、個(gè)數(shù)增加時(shí)，時(shí)間效率低，速度慢。非有限域、有限域上的稀疏多元多項(xiàng)式插值算法Ben-Or/Tiwari算法，根據(jù)黑盒賦值恢復(fù)目標(biāo)多項(xiàng)式，實(shí)現(xiàn)對多變元多項(xiàng)式的插值。在有限域上可以進(jìn)行各種代數(shù)運(yùn)算，有助于提高運(yùn)算速度。最后使用有理數(shù)恢復(fù)算法即可復(fù)原目標(biāo)多項(xiàng)式，在非有限域上可以把使用范圍擴(kuò)大，但是相對于有限域上的Ben-Or/Tiwari算法，其運(yùn)算速度次之，相對于直接法，其運(yùn)算速度比較快。數(shù)值實(shí)驗(yàn)中，通過變元次數(shù)、項(xiàng)數(shù)和個(gè)數(shù)的變化來測試本文算法的時(shí)間性能。結(jié)果表明，在一定條件有限域和非有限域下的Ben-Or/Tiwari算法都能在較短時(shí)間內(nèi)求解較小規(guī)模的黑盒多元多項(xiàng)式插值問題，并具有內(nèi)在的可并行性。相比于直接法而言，Ben-Or/Tiwari算法具有較低的時(shí)間復(fù)雜度和空間復(fù)雜度，且實(shí)驗(yàn)證明了有限域下，Ben-Or/Tiwari算法更為有效。

參考文獻(xiàn)：

[1] PLONKA G，WANNENWETSCH K，CUYT A，et al. Deterministic Sparse FFT for M-Sparse Vectors [J].Numerical Algorithms，2018，78（1）：133-159.

[2] 唐敏，鄧國強(qiáng).有限域上稀疏多元多項(xiàng)式插值算法 [J].計(jì)算機(jī)科學(xué)與探索，2019，13（2）：350-360.

[3] ISTRATOV A A，VYVENKO O F. Exponential Analysis in Physical Phenomena [J].Review of Scientific Instruments，1999，70（2）：1233-1257.

[4] ZIPPEL R. Interpolating Polynomials From Their Values [J].Journal of Symbolic Computation，1990，9（3）：375-403.

[5] ZIPPEL R. Probabilistic Algorithms for Sparse Polynomials [C]// Eurosam79，An International Symposium on Symbolic and Algebraic Manipulation.Heidelberg：Springer，1979：216-226.

[6] BEN-OR M，TIWARI P. A deterministic algorithm for sparse multivariate polynomial interpolation [C]//STOC88：Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing.New York：Association for Computing Machinery，1988：301-309.

作者簡介：張永燊（1996—），男，漢族，河北成安人，碩士研究生，研究方向：稀疏插值。