亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2021-12-16 11:49:28楊雪英肖水晶
        關(guān)鍵詞:實(shí)根同態(tài)高維

        楊雪英,肖水晶

        (南昌大學(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)定理,證明詳見(jià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(參見(jiàn)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)這一步驟的方法參見(jià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)。

        猜你喜歡
        實(shí)根同態(tài)高維
        關(guān)于半模同態(tài)的分解*
        拉回和推出的若干注記
        解一元二次方程中的誤點(diǎn)例析
        一種改進(jìn)的GP-CLIQUE自適應(yīng)高維子空間聚類算法
        基于加權(quán)自學(xué)習(xí)散列的高維數(shù)據(jù)最近鄰查詢算法
        一種基于LWE的同態(tài)加密方案
        HES:一種更小公鑰的同態(tài)加密算法
        二次函數(shù)迭代的一個(gè)問(wèn)題的探究
        一般非齊次非線性擴(kuò)散方程的等價(jià)變換和高維不變子空間
        高維Kramers系統(tǒng)離出點(diǎn)的分布問(wèn)題
        91尤物视频在线观看| 国产无套中出学生姝| 婷婷久久香蕉五月综合加勒比| 成人免费毛片内射美女-百度| 久久露脸国产精品WWW| 亚洲福利一区二区不卡| 国产av无码专区亚洲av麻豆| 欧美人与物videos另类| 亚洲自拍另类欧美综合| 日韩十八禁在线观看视频| 国产亚洲一区二区三区综合片| www射我里面在线观看| 国产在线丝袜精品一区免费 | 亚洲av乱码一区二区三区观影 | 国产精品一区二区三区黄片视频| 国产午夜视频一区二区三区 | 婷婷四房色播| 免费无码黄网站在线观看| 日本一区二区三级在线| 久久综合九色综合久99| 中文字幕av在线一二三区| 亚洲精品白浆高清久久| 青青草成人在线播放视频| 欧美牲交a欧美牲交aⅴ免费真| 免费人成毛片乱码| 丝袜美腿久久亚洲一区| 亚洲成人中文字幕在线视频| 九九精品国产亚洲av日韩| 亚洲无码夜夜操| 亚洲av调教捆绑一区二区三区| 国产成人无码av| 国内少妇自拍区免费视频| 精品国产乱码久久免费看| 国产精品一区二区三区专区| 色八a级在线观看| 久久久久久久综合日本| 全亚洲最大的私人影剧院在线看| 国产一精品一av一免费| 在线视频这里只有精品| 黄片亚洲精品在线观看| 欧美激情一区二区三区成人|