高維多項(xiàng)式理想的實(shí)根計(jì)算

楊雪英，肖水晶

(南昌大學(xué)理學(xué)院，江西 南昌 330031)

在實(shí)代數(shù)幾何中，多項(xiàng)式理想的實(shí)根扮演著如同根理想在復(fù)代數(shù)幾何中一樣的角色。與多項(xiàng)式理想的根的計(jì)算相比較，計(jì)算多項(xiàng)式理想的實(shí)根要困難得多。近年來(lái)，研究零維多項(xiàng)式理想的實(shí)根計(jì)算文獻(xiàn)較多，但對(duì)高維多項(xiàng)式理想的實(shí)根計(jì)算問(wèn)題的研究相對(duì)較少。一般說(shuō)來(lái)，研究者主要從數(shù)值計(jì)算和符號(hào)計(jì)算兩方面來(lái)研究多項(xiàng)式理想的實(shí)根計(jì)算問(wèn)題。

在符號(hào)計(jì)算方面，Beker和Neuhaus在文獻(xiàn)[1-2]中通過(guò)Gr?bner基[3-4]給出一個(gè)計(jì)算零維理想實(shí)根的算法。由于Gr?bner基的計(jì)算本身就存在比較大的難度，所以該算法實(shí)現(xiàn)起來(lái)比較復(fù)雜。1998年，Neuhaus在文獻(xiàn)[2]中對(duì)該算法進(jìn)行了修改與整理，并給出了高維多項(xiàng)式理想實(shí)根的計(jì)算算法，最后還給出了實(shí)根理想生成元的次數(shù)上界為D2O(n2)，其中D是輸入多項(xiàng)式次數(shù)上界，n為變?cè)獋€(gè)數(shù)。該算法在研究實(shí)代數(shù)簇的孤立點(diǎn)性質(zhì)的基礎(chǔ)上，將高維多元多項(xiàng)式理想轉(zhuǎn)化為零維理想，再通過(guò)Shape-Lemma[5-6]轉(zhuǎn)化為單個(gè)多項(xiàng)式情形。對(duì)于單個(gè)多項(xiàng)式情形，則通過(guò)準(zhǔn)素分解將多項(xiàng)式轉(zhuǎn)化為不可約多項(xiàng)式情形。對(duì)于一個(gè)不可約多項(xiàng)式P∈K[x1,x2,…,xn]，由變號(hào)準(zhǔn)則[2]判斷不可約多項(xiàng)式P是否為實(shí)，從而得出計(jì)算多項(xiàng)式理想實(shí)根的算法。Spang在文獻(xiàn)[7-8]中通過(guò)研究極大理想的性質(zhì)從而避免了[1-2]中算法產(chǎn)生的一些坐標(biāo)變換，提高了運(yùn)算效率并給出計(jì)算零維理想實(shí)根的算法。在文獻(xiàn)[9-10]中，Yang和Zhi從代數(shù)簇光滑情形與一般情形出發(fā)給出了計(jì)算多項(xiàng)式理想實(shí)根的所有極小素理想的生成元的概率算法，算法的復(fù)雜為So(1)(nD)O(nr2r)，其中D是多項(xiàng)式次數(shù)上界，n為變?cè)獋€(gè)數(shù)，r為生成理想的多項(xiàng)式個(gè)數(shù)。進(jìn)一步，Yang和Zhi在文獻(xiàn)[11]中提出了多項(xiàng)式環(huán)中S-根的概念，并給出計(jì)算S-根的所有極小素理想生成元的概率算法。

在數(shù)值計(jì)算方面，Lasserre等在文獻(xiàn)[12]中基于半正定規(guī)劃(SDP)松弛的性質(zhì)，給出了計(jì)算零維多項(xiàng)式理想實(shí)根以及S-根的算法。該算法很好地利用了半正定規(guī)劃以及數(shù)值線性代數(shù)的性質(zhì)，在不需要計(jì)算復(fù)零點(diǎn)的情況下可計(jì)算出所有的實(shí)零點(diǎn)。Lasserre等人在文獻(xiàn)[13]中介紹了一種新算法，在邊界基算法[14]中引入矩量矩陣(moment matrics)的半正定性限制，相對(duì)于文獻(xiàn)[12]中半正定規(guī)劃松弛更容易處理。馬玥等在文獻(xiàn)中基于矩量矩陣去計(jì)算Pommart基[16]，在文獻(xiàn)[12-13]中算法的基礎(chǔ)上推廣到高維多項(xiàng)式理想情形。Brake等人在文獻(xiàn)[17]中基于數(shù)值代數(shù)幾何與平方和規(guī)劃，給出了一個(gè)計(jì)算實(shí)根理想生成元的算法。

本文從符號(hào)計(jì)算的角度出發(fā)，考慮如何有效地計(jì)算K[x1,x2,…,xn]中高維多項(xiàng)式理想I的實(shí)根。與文獻(xiàn)[2]一樣，本文先考慮零維理想的情形，再通過(guò)多項(xiàng)式環(huán)的典范同態(tài)映射:

K[x1，…，xn]→K(x1，…，xs)[xs+1，…，xn]

將高維理想擴(kuò)張為零維理想，從而建立計(jì)算高維多項(xiàng)式理想實(shí)根的方法。

1 預(yù)備知識(shí)

定義1.1(理想的根與根理想)設(shè)I為多項(xiàng)式環(huán)K[x1，x2，…，xn]中一個(gè)理想，I的根定義為

下面為代數(shù)幾何學(xué)中著名的Hilbert零點(diǎn)定理，該定理揭示了代數(shù)簇與根理想之間的對(duì)應(yīng)關(guān)系。

設(shè)I是K[x1，x2，…，xn]中一個(gè)理想，若存在一個(gè)有限多項(xiàng)式集合{g1，g2，…，gs}使得I=〈g1,g2,…,gs〉，即稱I由{g1,g2,…,gs}生成。

引理1.3[19]設(shè)I1，I2是多項(xiàng)式環(huán)K[x1，x2，…，xn]中任意兩個(gè)理想，則以下結(jié)論成立:

定義1.4([1]，Definition2.1或[19]，85頁(yè))(多項(xiàng)式理想的實(shí)根)設(shè)K是一個(gè)實(shí)域，I?K[x1，x2，…，xn]是一個(gè)多項(xiàng)式理想，I的實(shí)根定義為

同樣地，在實(shí)代數(shù)幾何中有著名的實(shí)零點(diǎn)定理，證明詳見文獻(xiàn)[2]。

根據(jù)以上定義和定理我們可以得出如下引理

引理1.6([7]，Lemma1.8)設(shè)I，I1，I2是K[x1，x2，…，xn]中理想，則以下結(jié)論成立:

2 零維多項(xiàng)式理想的實(shí)根計(jì)算

2.1 單變量情形

本節(jié)討論單變量多項(xiàng)式環(huán)K[x]中理想實(shí)根的計(jì)算。由于K[x]是一個(gè)主理想環(huán)，從而首先確定不可約多項(xiàng)式能否生成一個(gè)實(shí)理想。

定理2.1.1設(shè)q是K[x]中不可約多項(xiàng)式，則q生成的理想〈q〉是實(shí)的，當(dāng)且僅當(dāng)q在K的實(shí)閉包中有一個(gè)根。

證明記R為K的實(shí)閉包。設(shè)理想〈q〉是實(shí)的，則K[x]/〈q〉是一個(gè)實(shí)環(huán)。由于q是K[x]中不可約多項(xiàng)式，從而K[x]/〈q〉是K的一個(gè)有限(代數(shù))擴(kuò)張。由實(shí)閉包的唯一性知，K[x]/〈q〉是R的一個(gè)子域。這樣，q在實(shí)閉包R中有一個(gè)根x+〈q〉。

根據(jù)定理2.1.1，對(duì)于g∈K[x]，我們可按如下步驟計(jì)算〈g〉的實(shí)根。

算法2.1.2(計(jì)算K[x]中理想的實(shí)根)

輸入：一個(gè)多項(xiàng)式g∈K[x]。

計(jì)算過(guò)程：

步驟1將多項(xiàng)式g進(jìn)行如下唯一分解：

其中pi(i=1，2，…，r)為K[x]中不可約多項(xiàng)式，ε∈K{0}，m1，m2，…，mr∈N。

步驟2抽出次數(shù)為奇數(shù)的不可約多項(xiàng)式，組成一個(gè)集合T1。

步驟3對(duì)于次數(shù)為偶數(shù)的不可約多項(xiàng)式，依次通過(guò)Sturm定理判斷出多項(xiàng)式是否存在實(shí)根。抽出次數(shù)為偶數(shù)且有實(shí)根的不可約多項(xiàng)式組成一個(gè)集合T2。

步驟4輸出結(jié)論：

這里T=T1∪T2。

2.2 單個(gè)多項(xiàng)式情形

本節(jié)主要討論單個(gè)多項(xiàng)式情形。以下引理為單個(gè)多元多項(xiàng)式所生成的主理想是否為實(shí)提供了重要的判定方法。

引理2.2.1([7]，Lemma3.1或[1]，Lemma4.1)設(shè)多項(xiàng)式P∈K[x1，x2，…，xm，x]，其中P是一個(gè)次數(shù)大于零的不可約多項(xiàng)式，則下列命題是等價(jià)的:

(1) 〈P〉·K(x1，x2，…，xm)[x]是實(shí)的。

(2) 〈P〉·K[x1，x2，…，xm，x]是實(shí)的。

(3)P是不定的，即存在實(shí)數(shù)a，b∈Rm+1滿足P(a)·P(b)<0。

文獻(xiàn)[20，21]中給出了判定一個(gè)多項(xiàng)式是否不定的算法。由引理2.2.1，可以得出如下算法。

算法2.2.2(計(jì)算K(x1，x2，…，xm)[x]中主理想的實(shí)根)

結(jié)構(gòu)：K是一個(gè)完滿域，且對(duì)于任意一個(gè)變?cè)纬傻挠蚨际峭隄M域。

輸入：一個(gè)多項(xiàng)式f∈K(x1，x2，…，xm)[x]。

計(jì)算過(guò)程:

步驟1在K(x1，x2，…，xm)[x]中，將多項(xiàng)式f進(jìn)行如下唯一分解：

其中pi(i=1，2，…，r)為K(x1，x2，…，xm)[x]中不可約多項(xiàng)式，ε∈K{0}，m1，m2，…，mr∈N。

步驟2對(duì)于每個(gè)不可約多項(xiàng)式pi，判斷其不定性。抽出所有不定的不可約多項(xiàng)式組成一個(gè)集合T。

步驟3輸出結(jié)論：

2.3 多元多項(xiàng)式情形

·primdecGTZ，primdecSY.輸入K[x1，x2，…xn]中理想I=〈f1，f2，…，fs〉，輸出I的素分解理想。

由文獻(xiàn)[7]中Remark 4.16以及引理1.6(4)得零維理想實(shí)根的計(jì)算算法RealZero(參見Singular程序包realrad)，具體如下:

算法2.3.1(零維多項(xiàng)式理想的實(shí)根計(jì)算)

結(jié)構(gòu):K是一個(gè)完滿域，且對(duì)于任意一個(gè)變?cè)纬傻挠蚨际峭隄M域。

輸入：K[x1，x2，…xn]中零維多項(xiàng)式理想I，I=〈f1，f2，…，fs〉。

計(jì)算過(guò)程:

步驟1根據(jù)文獻(xiàn)[7]中Remark 4.16，將I=〈f1，f2，…，fs〉簡(jiǎn)化為:

J=〈g1，g2，…，gs〉

步驟2調(diào)用算法primdecGTZ或primdecSY(取決于哪個(gè)算法更快)將J進(jìn)行素分解得到極大理想M1，M2，…，Ms，令Max:={M1，M2，…，Ms}。

步驟3若Max≠?，則選擇一個(gè)Mi∈Max，令Max:=Max{Mi}。

NonPrepared:=GeneralPos(NonPrep)。

3 高維多項(xiàng)式理想的實(shí)根計(jì)算

3.1 理想的擴(kuò)張與收縮

設(shè)K[x1，x2，…，xn]和K(x1，x2，…，xs)[xs+1，xs+2，…，xn]是帶有單位的可交換多項(xiàng)式環(huán)，I是K[x1，x2，…，xn]中一個(gè)理想，{x1，x2，…，xs}表示I在K[x1，x2，…，xn]中的一個(gè)極大無(wú)關(guān)變?cè)M。定義一個(gè)多項(xiàng)式環(huán)的典范同態(tài)映射:

在該環(huán)典范同態(tài)映射中，若有a∈K(x1，x2，…，xs)[xs+1，xs+2，…，xn]，s∈K[x1，x2，…，xs]，則sa∈K[x1，x2，…，xn]。

若不加說(shuō)明，本章所涉及的多項(xiàng)式環(huán)的典范同態(tài)映射都為Φ。以下給出該映射中理想的擴(kuò)張與收縮的定義，該定義是文獻(xiàn)[22]中一般代數(shù)幾何所定義的擴(kuò)張理想與收縮理想在多項(xiàng)式代數(shù)中的特殊化。

定義3.1.1在多項(xiàng)式環(huán)的典范同態(tài)映射Φ中，設(shè)I1是K[x1，x2，…，xn]中一個(gè)理想，則把I1的同態(tài)像Φ(I1)在K(x1，x2，…，xs)[xs+1，xs+2，…，xn]中生成的理想稱作I1在Φ上的擴(kuò)張理想，記作Ie;設(shè)I2是K(x1，x2，…，xs)[xs+1，xs+2，…，xn]中理想，易證Φ-1(I2)為K[x1，x2，…，xn]中理想，此時(shí)稱Φ-1(I2)為I2在Φ上的收縮理想，記作Ic。

根據(jù)理想的擴(kuò)張與收縮的定義，可以得出以下性質(zhì)，并給出簡(jiǎn)要的證明。

引理3.1.2在多項(xiàng)式環(huán)的典范同態(tài)映射Φ中，設(shè)I，I1，I2為K[x1，x2，…，xn]中理想，J，J1，J2為K(x1，x2，…，xs)[xs+1，xs+2，…，xn]中理想，則下列結(jié)論成立:

(1) (I1+I2)e=(I1)e+(I2)e;

(2) (J1+J2)c?(J2)c+(J2)c;

證明(1) 由多項(xiàng)式理想擴(kuò)張的定義知，

其中fi1，fi2∈I1，gi∈K(x1，x2，…，xs)[xs+1，xs+2，…，xn]，fi1，fi2，gi為多項(xiàng)式，i為有限的。

(2) 由理想收縮的定義知，(J1+J2)c=Φ-1(J1+J2)，從而

(J2)c+(J2)c=Φ-1(J1)+Φ-1(J2)。

再由同態(tài)映射性質(zhì)得，(J2)c+(J2)c?(J1+J2)c。

3.2 高維向零維的擴(kuò)張

由文獻(xiàn)[23]引理9.3.6知，在多項(xiàng)式環(huán)的典范同態(tài)中可以通過(guò)理想的擴(kuò)張將高維理想轉(zhuǎn)化為零維理想。

定理3.1.1([22]，Lemma8.13)設(shè)I是K[x1，x2，…，xn]中的一個(gè)真理想，U={x1，x2，…，xs}是I的一個(gè)極大無(wú)關(guān)變?cè)M，則I關(guān)于同態(tài)映射Φ的擴(kuò)張理想Ie在環(huán)K(x1，x2，…，xs)[xs+1，xs+2，…，xn]中是零維理想。

3.3 高維理想的實(shí)根計(jì)算

接下來(lái)我們討論將計(jì)算出的實(shí)根如何收縮回原來(lái)的多項(xiàng)式環(huán)中，即可計(jì)算出高維多項(xiàng)式理想的實(shí)根。為此，先引入以下命題。

命題3.3.1設(shè)I=〈f1，f2，…，ft〉是K[x1，x2，…，xn]中一個(gè)理想，則存在正整數(shù)k使得

I=〈I，Lk〉∩〈I:Lk〉

其中G是I的一個(gè)Gr?bner基，L=lcm{hc(g)|g∈G}，hc(g)∈K[x1，x2，…，xs]是多項(xiàng)式g在環(huán)K(x1，x2，…，xs)[xs+1，xs+2，…，xn]中的首項(xiàng)系數(shù)。

證明由理想的飽和定義知，存在正整數(shù)k使得I:Lk=I:L∞，由文獻(xiàn)[24]中算法22可計(jì)算得到k。顯然I?〈I，Lk〉∩(I:Lk)。

接下來(lái)證明〈I，Lk〉∩(I:Lk)?I。設(shè)f∈〈I，Lk〉∩(I:Lk)，則fLk∈I，且存在g∈I與h∈K[x1，x2，…，xn]使得f=g+Lkh，兩邊同乘Lk得Lkf=Lkg+L2kh。從而有L2kh=Lkf-Lkg∈I，于是h∈I:L2k。由于I:L2k?I:L∞=I:Lk，從而h∈I:Lk，于是Lkh∈I。又因?yàn)間∈I，所以f=g+Lkh∈I。

綜上，存在正整數(shù)k使得I=〈I，Lk〉∩(I:Lk)成立。

由命題3.3.1及[24]中命題3.2.30，可以得出以下推論。

推論3.3.2設(shè)I是K[x1，x2，…，xn]中一個(gè)理想，G為I的一個(gè)Gr?bner基，則存在正整數(shù)k使得

I=〈I，Lk〉∩Iec

其中L=lcm{hc(g)|g∈G}，且hc(g)∈K[x1，x2，…，xs]是g在環(huán)K(x1，x2，…，xs)[xs+1，xs+2，…，xn]中的首項(xiàng)系數(shù)。

證明由[24]中命題3.2.30知，當(dāng)I0=Ie時(shí)，存在正整數(shù)k使得Iec=I:L∞=I:Lk成立。由命題3.3.1知，此時(shí)k使得I=〈I，Lk〉∩(I:Lk)成立，于是I=〈I，Lk〉∩Iec。

基于推論3.3.2，我們可以建立如下算法。

算法3.3.3(計(jì)算L及正整數(shù)k使得I=〈I，Lk〉∩Iec)

結(jié)構(gòu)：K是一個(gè)完滿域，且對(duì)于任意一個(gè)變?cè)纬傻挠蚨际峭隄M域。

輸入：I?K[x1，x2，…，xn]。

輸出：L∈K[x1，x2，…，xs]，及正整數(shù)k使得I=〈I，Lk〉∩Iec。

計(jì)算過(guò)程:

步驟1計(jì)算I在K[x1，x2，…，xn]中的Gr?bner基G=(g1，g2，…，gm)(1≤m≤n)。

步驟1.1對(duì)任意的gi∈G，計(jì)算出gi在K(x1，x2，…，xs)[xs+1，xs+2，…，xn]中的首項(xiàng)系數(shù)hc(gi)。

步驟1.2對(duì)于上述所有的首項(xiàng)系數(shù)，在K(x1，x2，…，xs)[xs+1，xs+2，…，xn]中計(jì)算出最小公倍數(shù)，記作L=lcm{hc(gi)|gi∈G}。

步驟2由理想飽和的定義或文獻(xiàn)[24]中算法22計(jì)算出k。

步驟3輸出L∈K[x1，x2，…，xs]，及正整數(shù)k使得I=〈I，Lk〉∩Iec。

證明由Gr?bner基的有限性知算法具有終止性，正確性由推論3.3.2直接得出。

由推論3.3.2及多項(xiàng)式理想實(shí)根的相關(guān)性質(zhì)，則得出以下定理成立，該定理為本文算法3.3.5中主要思想。

設(shè){f1，f2，…，ft}∈K[x1，x2，…，xn](1≤t≤n)，I=〈f1，f2，…，ft〉，U={x1，x2，…，xs}是I的一個(gè)極大無(wú)關(guān)變?cè)M，且R表示Ie在K(x1，x2，…，xs)[xs+1，xs+2，…，xn]上的實(shí)根。由文獻(xiàn)[24]中算法23計(jì)算出R在K[x1，x2，…，xn]上的收縮理想的基Λ，根據(jù)推論3.3.2，由算法3.3.3計(jì)算出非零元L以及正整數(shù)k使得

I=〈f1，f2，…，ft〉=〈{f1，f2，…，ft}∪{Lk}〉∩〈f1，f2，…，ft〉ec

定理3.3.4設(shè)記號(hào)同上描述，則I=〈f1，f2，…，ft〉的實(shí)根等于所有〈{f1，f2，…，ft}∪{Lk}〉的實(shí)根與〈Λ〉的交集，即

證明若1∈I正確性顯然;若1?I，由推論3.3.2知L，k滿足

〈f1，f2，…，ft〉=〈{f1，f2，…，ft}∪{Lk}〉∩〈f1，f2，…，ft〉ec

則兩邊分別求實(shí)根得

由以上定理可以得出以下算法。

算法3.3.5(高維多項(xiàng)式理想的實(shí)根計(jì)算)

結(jié)構(gòu)：K是一個(gè)完滿域，且對(duì)于任意一個(gè)變?cè)纬傻挠蚨际峭隄M域。

輸入：{f1，f2，…，ft}∈K[x1，x2，…，xn]是I的生成元，即I=〈f1，f2，…，ft〉。

輸出：I的實(shí)根的基ξ。

計(jì)算過(guò)程：

步驟1如果1∈{f1，f2，…，ft}，那么顯然ξ等于1;若1?{f1，f2，…，ft}，則根據(jù)[23]中引理9.3.6中計(jì)算極大無(wú)關(guān)變?cè)M的討論計(jì)算出I的一個(gè)極大無(wú)關(guān)變?cè)MU={x1，x2，…，xs}。

步驟2調(diào)用算法2.3.1，計(jì)算出Ie在K(x1，x2，…，xs)[xs+1，xs+2，…，xn]中的實(shí)根R。

步驟3文獻(xiàn)[24]中算法23(取決于哪種方法更快)計(jì)算出R在K[x1，x2，…，xn]上的收縮理想的基Λ。

步驟4調(diào)用算法3.3.3計(jì)算出非零元L以及正整數(shù)k使得

I=〈f1，f2，…，ft〉=〈{f1，f2，…，ft}∪{Lk}〉∩〈{f1，f2，…，ft}〉ec

步驟5計(jì)算〈{f1，f2，…，ft}∪{L}〉的實(shí)根的基，再把實(shí)根的基與〈Λ〉作交集，得出的交集即為I的實(shí)根的基ξ。

證明終止性:若1∈{f1，f2，…，ft}，終止性顯然;

若1?{f1，f2，…，ft}，根據(jù)U是極大無(wú)關(guān)變?cè)M，則〈f1，f2，…，ft〉∩K[U]={0}則L?I，即〈f1，f2，…，ft〉?〈{f1，f2，…，ft}∪{L}〉。

以上步驟是對(duì)多項(xiàng)式理想的實(shí)根計(jì)算進(jìn)行遞歸調(diào)用，且輸入的有限多項(xiàng)式集生成的理想構(gòu)成嚴(yán)格升鏈，由有限升鏈條件即得終止性。

正確性:由定理3.3.4可得出。

復(fù)雜度分析:記degfi(1≤i≤t)為輸入多項(xiàng)式組{f1，f2，…，ft}中多項(xiàng)式次數(shù)，m為輸入多項(xiàng)式組變?cè)獋€(gè)數(shù)，s為極大變?cè)獋€(gè)數(shù)。算法3.3.5的第1步計(jì)算I的一個(gè)極大無(wú)關(guān)變?cè)M，可實(shí)現(xiàn)這一步驟的方法參見[23]中引理9.3.6，由[23]中引理9.3.6中極大無(wú)關(guān)變?cè)M的討論，可知第1步的復(fù)雜度為O(s2)(0≤s≤n)。

接下來(lái)，由文獻(xiàn)[7]中算法RealZero，計(jì)算零維理想在多項(xiàng)式環(huán)中的實(shí)根的復(fù)雜度為Max(deg(fi))2O(m2)。步驟3中計(jì)算實(shí)根理想的收縮，由[24]中命題3.2.30知，計(jì)算收縮理想的復(fù)雜度是計(jì)算多項(xiàng)式集的Gr?bner基所產(chǎn)生。由計(jì)算Gr?bner基的算法Buchberger知，由[24]中定理2.3.22知對(duì)多項(xiàng)式集進(jìn)行循環(huán)運(yùn)算直至計(jì)算出Gr?bner基G，因此步驟三的復(fù)雜度為O(nt2)。

步驟4中調(diào)用算法3.3.3計(jì)算出非零元L以及正整數(shù)k使得

I=〈f1，f2，…，ft〉=〈{f1，f2，…，ft}∪{Lk}〉∩〈{f1，f2，…，ft}〉ec

由算法3.3.3計(jì)算步驟1與步驟2，知算法3.3.5步驟四的復(fù)雜度不會(huì)超過(guò)Max(deg(fi))2O(m2)。因?yàn)樵撍惴ㄖ嘘P(guān)鍵步驟的復(fù)雜度都不超過(guò)Max(deg(fi))2O(m2)，所以該算法的整體復(fù)雜度為Max(deg(fi))2O(m2)。