F5 (algoritme)

F5-algoritmen til beregning af Gröbner-grundlaget blev foreslået af J.-Ch. Foger i 2002. I dette papir vil vi overveje dens matrixversion, som fungerer for homogene polynomier . Hovedproceduren for denne algoritme beregner Gröbner d-grundlaget, det vil sige delmængden af Gröbner-grundlaget, med hensyn til hvilket alle polynomier fra et ideal af grad d reduceres til nul.

I F5-algoritmen er hvert resulterende polynomium forbundet med en signatur (et par af et monomial og et generatornummer), der koder information om oprindelsen af dette polynomium. Hovedideen er ikke at inkludere, hvis det er muligt, i matricerne de rækker, der åbenlyst vil være lineært afhængige med resten (det vil sige, de vil blive reduceret til nul).

For at gøre dette er reduktioner begrænset til dem, der ikke ændrer signaturen af elementerne, og blandt de næste polynomier, der behandles, betragtes kun dem, hvis signaturmonomial ikke er deleligt med nogen af de højeste monomer af allerede fundne elementer i basisen. .

F5 Matrix Algoritme Pseudokode

Input: homogene polynomier med potenser maksimal grad . ${\displaystyle f_{1},\dots ,f_{m))$ $d_{1}\leqslant \dots \leqslant d_{m};$ $D$

Output: elementer af grad, der ikke er højere end det reducerede Gröbner-grundlag fra for . $D$ ${\displaystyle f_{1},\dots ,f_{i))$ $i={\overline {1,m))$

Algoritme:

for i fra 1 til n gør Gᵢ := 0 ; ende for // initialiser Gröbner-baserne Gᵢ af (f, …, fᵢ). for d₁ fra d til D do ℳ _ { d , 0 } := 0 , ℳ̅ _ { d , 0 } := 0 for jeg fra 1 til m gør hvis d < dᵢ så ℳ _ { d , i } := ℳ _ { d , i - 1 } ellers hvis d = dᵢ så ℳ _ { d , i } := føj den nye række fᵢ til ℳ̅ _ { dᵢ , i - 1 } med indeks ( i , 1 ) andet ℳ _ { d , i } := ℳ̅ _ { d , i - 1 } Crit := LT ( ℳ̅ _ { d - dᵢ , i - 1 }) for f i rækker ( ℳ _ { d - 1 , i }) \ rækker ( ℳ _ { d - 1 , i - 1 }) gør ( i , u ) := indeks ( f ) , med u = x_ { j₁ } , … , x_ { jd - dᵢ - 1 } , og 1 ≤ j₁ ≤ … ≤ j_ { d - dᵢ - 1 } ≤ n for j fra j_ { d - dᵢ - 1 } til n do hvis uxⱼ ∉ Crit så tilføj den nye række xⱼf med indeks ( i , uxⱼ ) i ℳ _ { d , i } ende hvis ende for ende for ende hvis Beregn ℳ̅ _ { d , i } ved gaussisk eliminering fra ℳ _ { d , i } Tilføj til Gᵢ alle rækker af ℳ̅ _ { d , i } , der ikke kan reduceres med LT ( Gᵢ ) ende for ende for returner [ Gᵢ | i = 1 , … , m ]

For - løkken på linje 14 bygger en matrix, der indeholder alle polynomier i c (undtagen dem, der trivielt annullerer). For at undgå overflødige beregninger bygges de ud fra rækkerne i den foregående matrix , dvs. alle rækker ganges med alle variable. Rækken ved indeks c kan opstå fra flere rækker i , vi kan bygge den ud fra rækken indekseret ved , c , og gange den med , den største variabel der forekommer i . Dette sikrer, at hver række tages fra nøjagtig én række i den foregående matrix. ${\displaystyle M_{d,i))$ $x_{1}^{\alpha _{1}}\dots x_{n}^{\alpha _{n}}f_{i}$ ${\displaystyle \alpha _{1}+\dots +\alpha _{n}=d-d_{i))$ ${\displaystyle M_{d-1,i))$ $(i,x_{1}^{\alpha _{1))\dots x_{j}^{\alpha _{j)))$ $\alpha _{j}\neq 0$ ${\displaystyle M_{d-1,i))$ $(i,u)$ ${\displaystyle M_{d-1,i))$ $u=x_{1}^{\alpha _{1}}\dots x_{j}^{\alpha _{j-1}}$ $x_{j}$ $u$

Et eksempel på F5-algoritmen

Overvej et homogent system med graderet invers leksiografisk rækkefølge efter matrixalgoritmen . $\mathbb {F} _{23}[x,y,z]$ $(x\succ y\succ z)$ $F5$

{\begin{cases}f_{3}=x^{2}+18xy+19y^{2}+8xz+5yz+7z^{2}\\f_{2}=3x^{2}+ 7xy+22xz+11yz+22z^{2}+8y^{2}\\f_{1}=6x^{2}+12xy+4y^{2}+14xz+9yz+7z^{2}\\\ slut{cases}}

For at beregne Gröbner-grundlaget definerer vi , og , og betragter de kritiske par og . Som i algoritmen bruger vi power-2 matrix-delen til at bringe disse tre kritiske par sammen: ${f_{1},f_{2},f_{3))$ $F_{1}=(e_{1},f_{1})$ $F_{2}=(e_{2},f_{2})$ $F_{3}=(e_{3},f_{3})$ $[F_{1},F_{2}]=(1,f_{1},1,f_{2}),[F_{1},F_{3}]=(1,f_{1} ,1,f_{3})$ $[F_{2},F_{3}]=(1,f_{2},1,f_{3})$ ${\displaystyle \mathbb {F} _{4))$ ${\displaystyle 1xf_{1},1xf_{2},1xf_{3))$

{\begin{array}{ll}{\begin{aligned}\\A_{2}={\begin{aligned}f_{3}\\f_{2}\\f_{1}\end{ aligned}}\end{aligned}}&{\begin{aligned}\\\left({\begin{aligned}\\\\\\\end{aligned}}\right.\end{aligned}}{\ start{matrix}x^{2}&xy&y^{2}&xz&yz&z^{2}\\1&18&19&8&5&7\\3&7&8&22&11&22\\6&12&4&14&9&7\end{matrix)){\begin{aligned}\\be\{begin. }\\\\\\\end{aligned}}\right)\end{aligned}}\end{array}}

og efter at have bragt matricen til en trekantet form: $A_{2}$

{\begin{array}{ll}{\begin{aligned}\\B_{2}={\begin{aligned}f_{3}\\{\underline {f_{2))}\\f_ {1}\end{aligned}}\end{aligned}}&{\begin{aligned}\\\left({\begin{aligned}\\\\\\\end{aligned}}\right.\end {aligned}}{\begin{matrix}x^{2}&xy&y^{2}&xz&yz&z^{2}\\1&{\underline {18}}&19&8&5&7\\0&1&3&2&4&-1\\0&{\underline {0} }&1&-11&-3&-5\end{matrix}}{\begin{aligned}\\\venstre.{\begin{aligned}\\\\\\\end{aligned}}\right)\end{aligned }}\end{array}}

og to "nye" polynomier vises: og , som er resultatet af at sænke de kritiske par og . Bemærk at signaturen for polynomiet er , hvilket svarer til etiketten til venstre for denne række (understreget i matrixen ). $f_{4}=xy+4yz+2xz+3y^{2}-z^{2}\ (F_{4}=(e_{2},f_{4}))$ $f_{5}=y_{2}-11xz-3yz-5z^{2}\ (F_{5}=(e_{3},f_{5}))$ $[F_{1},F_{2}],[F_{1},F_{3}]$ $[F_{2},F_{3}]$ ${\displaystyle f_{4))$ $e_{{2}}$ ${\displaystyle f_{2))$ ${\displaystyle B_{2))$

Bemærk også, at de understregede 18 ikke er reduceret med , da signaturen er , hvilket er mindre end . Mens det understregede 0 er formindsket siden . Dette beviser, at reduktionen i algoritmen er en envejsreduktion. ${\displaystyle f_{4))$ ${\displaystyle f_{3))$ ${\displaystyle e_{3))$ $e_{{2}}$ ${\displaystyle e_{1}\succ e_{2))$ $\mathbb {F} _{5}$

Det næste skridt er at overveje nye kritiske par: og . Vi udvælger par efter grad og bygger en matrix af grad 3 for at arbejde med de næste kritiske par sammen. Vi skal kun overveje dele , med dele der er skrivbare og hhv. $[F_{1},F_{4}]=(y,f_{1},x,f_{4}),[F_{4},F_{2}]=(x,f_{4} ,y,f_{2}),[F_{4},F_{3}]=(x,f_{4},y,f_{3}),[F_{5},F_{4}]=( x,f_{5},y,f_{4}),[F_{5},F_{1}]=(x^{2},f_{5},y^{2},f_{1}) ,[F_{5},F_{2}]=(x^{2},f_{5},y^{2},f_{2})$ $[F_{5},F_{3}]=(x^{2},f_{5},y^{2},f_{3})$ $A_{3}$ $[F_{1},F_{4}]=(y,f_{1},x,f_{4}),[F_{4},F_{2}]=(x,f_{4} ,y,f_{2}),[F_{4},F_{3}]=(x,f_{4},y,f_{3}),[F_{5},F_{4}]=( x,f_{5},y,f_{4})$ ${\displaystyle yf_{3},yf_{4},xf_{4},xf_{5))$ ${\displaystyle yf_{2},yf_{1))$ $F_{4}$ $F_{5}$

Ligesom algoritmen er delene de rækker, der skal reduceres i matrixen, og vi skal også vælge de dele, der bruges til at reducere disse rækker. Da de er dele , skal vi tilføje dele til matrixen for at eliminere dem. $\mathbb {F} _{5}$ ${\displaystyle yf_{3},yf_{4},xf_{4},xf_{5))$ $y^{3},x^{2}z,xyz,y^{2}z$ ${\displaystyle yf_{3},yf_{4},xf_{4},xf_{5))$ ${\displaystyle yf_{5},xf_{3},zf_{4},zf_{5))$ $A_{3}$

Vi har nu en matrix med grad 3 (ordnet efter signatur): $A_{3}$

{\begin{array}{ll}{\begin{aligned}\\A_{3}={\begin{aligned}zf_{3}(ze_{3})\\yf_{3}(ye_{ 3})\\zf_{4}(ze_{2})\\yf_{4}(ye_{2})\\xf_{4}(xe_{2})\\zf_{5}(ze_{1} )\\yf_{5}(ye_{1})\\xf_{5}(xe_{1})\end{aligned}}\end{aligned}}&{\begin{aligned}\\\left({ \begin{aligned}\\\\\\\\\\\\\\\\end{aligned}}\right.\end{aligned}}{\begin{matrix}x^{2}y&xy^{ 2 }&y^{3}&x^{2}z&xyz&y^{2}z&xz^{2}&yz^{2}&z^{3}\\0&0&0&1&18&19&8&5&7\\1&18&19&0&8&5&0&7&0\\0&0&0&0&1&3&2&4&22\\0&1&3&0&2&4&0&22&0\\1&3&0&2&4&0&22&0&0\\0&0&0&0&0&1&12&20&18 \ \0&0&1&0&12&20&0&18&0\\0&1&0&12&20&0&18&0&0\end{matrix}}{\begin{aligned}\\\venstre.{\begin{aligned}\\\\\\\\\\\\\\\\\\end{aligned} }\right)\end{aligned}}\end{array}}

og efter reduktion til en trekantet form:

{\begin{array}{ll}{\begin{aligned}\\B_{3}={\begin{aligned}yf_{3}(ye_{3})\\yf_{4}(ye_{ 2})\\{\understreget {xf_{4}}}(xe_{2})\\zf_{3}(ze_{3})\\zf_{4}(ze_{2})\\zf_{5 }(ze_{1})\\{\understreget {yf_{5}}}(ye_{1})\\{\understreget {xf_{5}}}(xe_{1})\end{aligned}}\ end{aligned}}&{\begin{aligned}\\\left({\begin{aligned}\\\\\\\\\\\\\\\\\\end{aligned}}\right.\end { justeret}}{\begin{matrix}x^{2}y&xy^{2}&y^{3}&x^{2}z&xyz&y^{2}z&xz^{2}&yz^{2}&z^{3} \ \1&18&19&0&8&5&0&7&0\\0&1&3&0&2&4&0&22&0\\0&0&\mathbf {1} &{\understreg {0}}&{\understreg {0}}&{\understreg {8}}&{\understreg {1}}&{\understreg { 1}}&{\understreget {18}}&15\\0&0&0&1&18&19&8&5&7\\0&0&0&0&0&1&3&2&4&22\\0&0&0&0&0&1&12&20&18\\0&0&0&0&0&0&0&0&1}\th\th\0{0} \\\\\\\\\\\\\end{aligned}}\right)\end{aligned}}\end{array}}

og polynomium og er resultaterne af reduktion af kritiske par med grad 3. Bemærk, at selvom det mærkede polynomium ikke er -reducerbart til . Er således stadig et "nyt" polynomium. $f_{6}=y^{3}+8y^{2}+xz^{2}+18yz^{2}+15z^{3}(F_{6}=(xe_{2},f_ {6})),f_{7}=xz^{2}+11yz^{2}+13z^{2}(F_{3}=(ye_{1},f_{7}))$ $f_{8}=yz^{2}+18z^{3}(F_{8}=(xe_{1},f_{8})$ $lpp(f_{6})=y^{3}=ylpp(f_{5})$ ${\displaystyle F_{6))$ $\mathbb {F} _{5}$ $F_{5}$ ${\displaystyle f_{6))$

Nu er betydningen af det skrevne kriterium meget klarere. Når vi konstruerer matrixen , angiver vi signaturerne for hver række (polynomium) i parentes. Mærkede polynomier med de samme signaturer vil optræde i samme række af matricen, så det er nok at forholde sig til de seneste resultater (hvorfor vi tænker på rækkefølgen, hvori mærkede polynomier oprettes). Også ensidig reduktion er tydelig i matrixen . Lad os se på linjen . De understregede 0, 0 fald på henholdsvis linjerne og , mens de understregede 8,1,18 ikke er udelukket på linjerne og . årsagen er, at reduktionen i algoritmen er en envejsreduktion. Mere specifikt strengsignaturerne og denne og , som begge er mindre end strengen . $A_{3}$ ${\displaystyle B_{3))$ $xf_{4}(xe_{2})$ $zf_{3}(ze_{3})$ $zf_{4}(ze_{2})$ $zf_{5}(ze_{1}),yf_{5}(ye_{1})$ $xf_{5}(xe_{1})$ $\mathbb {F} _{5}$ $zf_{3}(ze_{3})$ $zf_{4}(ze_{2})$ ${\displaystyle ze_{3))$ ${\displaystyle ze_{2))$ ${\displaystyle xe_{2))$ $xf_{4}(xe_{2})$

Således er strengene og i stand til at reducere strengen . Vi har dog så strenge og klipper ikke snore . Bemærk, at da kun rækkerne og skal gemmes, er de øvrige rækker ikke helt reduceret i matrixen . $zf_{3}(ze_{3})$ $zf_{4}(ze_{2})$ $xf_{4}(xe_{2})$ ${\displaystyle ze_{1},ye_{1},xe_{1}\succ xe_{2))$ $zf_{5}(ze_{1}),yf_{5}(ye_{1})$ $xf_{5}(xe_{1})$ $xf_{4}(xe_{2})$ $xf_{4}(xe_{2}),yf_{5}(ye_{1})$ $xf_{5}(xe_{1})$ ${\displaystyle B_{3))$

Men vi må indse, at mens algoritmens to nye kriterier kan kassere næsten alle ubrugelige beregninger, resulterer envejsreduktionen i en lavere matrixelimineringseffektivitet end . $\mathbb {F} _{5}$ ${\displaystyle \mathbb {F} _{4))$

Litteratur

J.-C. Faug`ere.En ny effektiv algoritme til beregning af Grobner-baser uden reduktion til nul (F5).

M. Bardet, J.-C. Faug'ere, B. Salvy. Om kompleksiteten af F5 Grobner-basisalgoritmen.

C. Eder, J.-C. Faug'ere. En undersøgelse om signaturbaserede Grobner-basisberegninger.

Stegers, T., 2005. Faug'ere's F5 Algorithm Revisited. Speciale til graden Diplom-matematiker