高維多項式理想的實根計算

楊雪英，肖水晶

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

在實代數幾何中，多項式理想的實根扮演著如同根理想在復代數幾何中一樣的角色。與多項式理想的根的計算相比較，計算多項式理想的實根要困難得多。近年來，研究零維多項式理想的實根計算文獻較多，但對高維多項式理想的實根計算問題的研究相對較少。一般說來，研究者主要從數值計算和符號計算兩方面來研究多項式理想的實根計算問題。

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

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

本文從符號計算的角度出發，考慮如何有效地計算K[x1,x2,…,xn]中高維多項式理想I的實根。與文獻[2]一樣，本文先考慮零維理想的情形，再通過多項式環的典范同態映射:

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

將高維理想擴張為零維理想，從而建立計算高維多項式理想實根的方法。

1 預備知識

定義1.1(理想的根與根理想)設I為多項式環K[x1，x2，…，xn]中一個理想，I的根定義為

下面為代數幾何學中著名的Hilbert零點定理，該定理揭示了代數簇與根理想之間的對應關系。

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

引理1.3[19]設I1，I2是多項式環K[x1，x2，…，xn]中任意兩個理想，則以下結論成立:

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

同樣地，在實代數幾何中有著名的實零點定理，證明詳見文獻[2]。

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

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

2 零維多項式理想的實根計算

2.1 單變量情形

本節討論單變量多項式環K[x]中理想實根的計算。由于K[x]是一個主理想環，從而首先確定不可約多項式能否生成一個實理想。

定理2.1.1設q是K[x]中不可約多項式，則q生成的理想〈q〉是實的，當且僅當q在K的實閉包中有一個根。

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

根據定理2.1.1，對于g∈K[x]，我們可按如下步驟計算〈g〉的實根。

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

輸入：一個多項式g∈K[x]。

計算過程：

步驟1將多項式g進行如下唯一分解：

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

步驟2抽出次數為奇數的不可約多項式，組成一個集合T1。

步驟3對于次數為偶數的不可約多項式，依次通過Sturm定理判斷出多項式是否存在實根。抽出次數為偶數且有實根的不可約多項式組成一個集合T2。

步驟4輸出結論：

這里T=T1∪T2。

2.2 單個多項式情形

本節主要討論單個多項式情形。以下引理為單個多元多項式所生成的主理想是否為實提供了重要的判定方法。

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

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

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

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

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

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

結構：K是一個完滿域，且對于任意一個變元集形成的域都是完滿域。

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

計算過程:

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

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

步驟2對于每個不可約多項式pi，判斷其不定性。抽出所有不定的不可約多項式組成一個集合T。

步驟3輸出結論：

2.3 多元多項式情形

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

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

算法2.3.1(零維多項式理想的實根計算)

結構:K是一個完滿域，且對于任意一個變元集形成的域都是完滿域。

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

計算過程:

步驟1根據文獻[7]中Remark 4.16，將I=〈f1，f2，…，fs〉簡化為:

J=〈g1，g2，…，gs〉

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

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

NonPrepared:=GeneralPos(NonPrep)。

3 高維多項式理想的實根計算

3.1 理想的擴張與收縮

設K[x1，x2，…，xn]和K(x1，x2，…，xs)[xs+1，xs+2，…，xn]是帶有單位的可交換多項式環，I是K[x1，x2，…，xn]中一個理想，{x1，x2，…，xs}表示I在K[x1，x2，…，xn]中的一個極大無關變元組。定義一個多項式環的典范同態映射:

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

若不加說明，本章所涉及的多項式環的典范同態映射都為Φ。以下給出該映射中理想的擴張與收縮的定義，該定義是文獻[22]中一般代數幾何所定義的擴張理想與收縮理想在多項式代數中的特殊化。

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

根據理想的擴張與收縮的定義，可以得出以下性質，并給出簡要的證明。

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

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

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

證明(1) 由多項式理想擴張的定義知，

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

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

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

再由同態映射性質得，(J2)c+(J2)c?(J1+J2)c。

3.2 高維向零維的擴張

由文獻[23]引理9.3.6知，在多項式環的典范同態中可以通過理想的擴張將高維理想轉化為零維理想。

定理3.1.1([22]，Lemma8.13)設I是K[x1，x2，…，xn]中的一個真理想，U={x1，x2，…，xs}是I的一個極大無關變元組，則I關于同態映射Φ的擴張理想Ie在環K(x1，x2，…，xs)[xs+1，xs+2，…，xn]中是零維理想。

3.3 高維理想的實根計算

接下來我們討論將計算出的實根如何收縮回原來的多項式環中，即可計算出高維多項式理想的實根。為此，先引入以下命題。

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

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

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

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

接下來證明〈I，Lk〉∩(I:Lk)?I。設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。又因為g∈I，所以f=g+Lkh∈I。

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

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

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

I=〈I，Lk〉∩Iec

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

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

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

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

結構：K是一個完滿域，且對于任意一個變元集形成的域都是完滿域。

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

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

計算過程:

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

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

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

步驟2由理想飽和的定義或文獻[24]中算法22計算出k。

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

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

由推論3.3.2及多項式理想實根的相關性質，則得出以下定理成立，該定理為本文算法3.3.5中主要思想。

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

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

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

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

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

則兩邊分別求實根得

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

算法3.3.5(高維多項式理想的實根計算)

結構：K是一個完滿域，且對于任意一個變元集形成的域都是完滿域。

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

輸出：I的實根的基ξ。

計算過程：

步驟1如果1∈{f1，f2，…，ft}，那么顯然ξ等于1;若1?{f1，f2，…，ft}，則根據[23]中引理9.3.6中計算極大無關變元組的討論計算出I的一個極大無關變元組U={x1，x2，…，xs}。

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

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

步驟4調用算法3.3.3計算出非零元L以及正整數k使得

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

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

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

若1?{f1，f2，…，ft}，根據U是極大無關變元組，則〈f1，f2，…，ft〉∩K[U]={0}則L?I，即〈f1，f2，…，ft〉?〈{f1，f2，…，ft}∪{L}〉。

以上步驟是對多項式理想的實根計算進行遞歸調用，且輸入的有限多項式集生成的理想構成嚴格升鏈，由有限升鏈條件即得終止性。

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

復雜度分析:記degfi(1≤i≤t)為輸入多項式組{f1，f2，…，ft}中多項式次數，m為輸入多項式組變元個數，s為極大變元個數。算法3.3.5的第1步計算I的一個極大無關變元組，可實現這一步驟的方法參見[23]中引理9.3.6，由[23]中引理9.3.6中極大無關變元組的討論，可知第1步的復雜度為O(s2)(0≤s≤n)。

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

步驟4中調用算法3.3.3計算出非零元L以及正整數k使得

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

由算法3.3.3計算步驟1與步驟2，知算法3.3.5步驟四的復雜度不會超過Max(deg(fi))2O(m2)。因為該算法中關鍵步驟的復雜度都不超過Max(deg(fi))2O(m2)，所以該算法的整體復雜度為Max(deg(fi))2O(m2)。