F5 (algoritmus)

A Gröbner-bázis kiszámítására szolgáló F5 algoritmust J.-Ch. Foger 2002-ben. Ebben a cikkben megvizsgáljuk a mátrix változatát, amely homogén polinomokra működik . Ennek az algoritmusnak a fő eljárása kiszámítja a Gröbner d-bázist, vagyis a Gröbner-bázis azon részhalmazát, amelyre vonatkozóan egy legfeljebb d fokú ideálból származó összes polinom nullára redukálódik.

Az F5 algoritmusban minden eredményül kapott polinomhoz egy aláírás (egy monom és egy generátorszám párja) van társítva, amely a polinom eredetére vonatkozó információkat kódol. A fő gondolat az, hogy lehetőség szerint ne vegyük be a mátrixokba azokat a sorokat, amelyek nyilvánvalóan lineárisan függenek a többitől (vagyis nullára redukálódnak).

Ehhez a redukciókat azokra korlátozzuk, amelyek nem változtatják meg az elemek aláírását, és a következő feldolgozás alatt álló polinomok közül csak azokat veszik figyelembe, amelyek aláírási monomija nem osztható a bázis már megtalált elemeinek egyik legmagasabb monomijával sem. .

F5 Mátrix Algoritmus Pszeudokód

Bemenet: homogén polinomok maximális fokú hatványokkal . ${\displaystyle f_{1},\dots ,f_{m))$ $d_{1}\leqslant \dots \leqslant d_{m};$ $D$

Kimenet: a -ból származó redukált Gröbner-bázisnál nem magasabb fokszámú elemek . $D$ ${\displaystyle f_{1},\dots ,f_{i))$ $i={\overline {1,m))$

Algoritmus:

i -re 1 -től n - ig Gᵢ : = 0 ; vége // inicializálja az (f, …, fᵢ) Gröbner-bázisait. d1 esetén d - től D - ig do ℳ _ { d , 0 } := 0 , ℳ̅ _ { d , 0 } := 0 i 1 - től m do _ ha d < dᵢ akkor ℳ _ { d , i } := ℳ _ { d , i - 1 } különben ha d = dᵢ akkor ℳ _ { d , i } := adjuk hozzá az új fᵢ sort a ℳ̅ _ { dᵢ , i - 1 } sorhoz ( i , 1 ) indexszel más ℳ _ { d , i } := ℳ̅ _ { d , i - 1 } Crit := LT ( ℳ̅ _ { d - dᵢ , i - 1 }) az f sorokban ( ℳ _ { d - 1 , i } ) \ Rows ( ℳ _ { d - 1 , i - 1 } ) do ( i , u ) := index ( f ) , ahol u = x_ { j₁ } , … , x_ { jd - dᵢ - 1 } , és 1 ≤ j₁ ≤ … ≤ j_ { d - dᵢ - 1 } ≤ n j esetén j_ { d - dᵢ - 1 } -től n do _ ha uxⱼ ∉ Crit akkor adjuk hozzá az új xⱼf sort ( i , uxⱼ ) indexel ℳ _ { d , i } _ vége ha véget ért véget ért vége ha Számítsa ki a ℳ̅ _ { d , i } értéket Gauss eliminációval ℳ _ { d , i } értékből Adja hozzá a Gᵢ -hez a ℳ̅ _ { d , i } összes sorát , amely nem csökkenthető LT - vel ( Gᵢ ) véget ért véget ért return [ Gᵢ | i = 1 , … , m ]

A 14. sorban lévő for ciklus egy mátrixot épít fel, amely tartalmazza a c összes polinomját (kivéve azokat, amelyek triviálisan nullázzák). A redundáns számítások elkerülése érdekében az előző mátrix soraiból épülnek fel, azaz minden sort megszoroznak az összes változóval. A c indexű sor több sorból is előfordulhat -ben , felépíthetjük a , c -vel indexelt sorból , és megszorozzuk a -ben előforduló legnagyobb változóval . Ez biztosítja, hogy minden sor pontosan az előző mátrix egy sorából kerüljön átvételre. ${\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$

Példa az F5 algoritmusra

Tekintsünk egy homogén rendszert inverz lexográfiai sorrendben a mátrixalgoritmus szerint . $\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}\\\ vége{esetek}}

A Gröbner-bázis kiszámításához definiáljuk , és , és figyelembe vesszük az és a kritikus párokat . Az algoritmushoz hasonlóan a power-2 mátrixrészt használjuk, hogy összehozzuk ezt a három kritikus párt: ${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{ igazítva}}\vége{igazított}}&{\begin{igazított}\\\balra({\begin{aligned}\\\\\\\end{igazított}}\jobbra.\end{igazított}}{\ kezdő{mátrix}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{mátrix)){\begin{igazított}\be\{balra }\\\\\\\end{igazított}}\jobbra)\end{igazított}}\end{tömb}}

és miután a mátrixot háromszög alakúra hoztuk: $A_{2}$

{\begin{array}{ll}{\begin{aligned}\\B_{2}={\begin{aligned}f_{3}\\{\aláhúzás {f_{2))}\\f_ {1}\end{aligned}}\end{aligned}}&{\begin{aligned}\\\left({\begin{aligned}\\\\\\\end{aligned}}\right.\end {aligned}}{\begin{mátrix}x^{2}&xy&y^{2}&xz&yz&z^{2}\\1&{\aláhúzás {18}}&19&8&5&7\\0&1&3&2&4&-1\\0&{\aláhúzás {0} }&1&-11&-3&-5\end{mátrix}}{\begin{igazított}\\\balra.{\begin{aligned}\\\\\\\end{aligned}}\right)\end{igazított }}\end{tömb}}

és két "új" polinom jelenik meg: és , amelyek az és a kritikus párok csökkentésének eredménye . Vegye figyelembe, hogy a polinom aláírása , amely megfelel a sor bal oldalán található címkének ( a mátrixban aláhúzva ). $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))$ ${\megjelenítési stílus B_{2))$

Azt is vegye figyelembe, hogy az aláhúzott 18-at nem csökkenti , mivel az aláírás kisebb, mint . Míg az aláhúzott 0 csökken, mivel . Ez bizonyítja, hogy az algoritmus redukciója egyirányú csökkentés. ${\displaystyle f_{4))$ ${\displaystyle f_{3))$ ${\displaystyle e_{3))$ $e_{{2}}$ ${\displaystyle e_{1}\succ e_{2))$ $\mathbb {F} _{5}$

A következő lépés az új kritikus párok figyelembevétele: és . Kiválasztjuk a párokat fokozat szerint, és felállítunk egy 3. fokú mátrixot, hogy együtt dolgozhassunk a következő kritikus párokkal . Csak a részeket kell figyelembe vennünk , az írható részekkel , ill. $[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))$ ${\displaystyle F_{4))$ $F_{5}$

Az algoritmushoz hasonlóan a részek azok a sorok, amelyeket csökkenteni kell a mátrixban, és ki kell választanunk azokat a részeket is, amelyeket a sorok kicsinyítésére használunk. Mivel ezek részek , részeket kell hozzáadnunk a mátrixhoz , hogy kiküszöböljük őket. $\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}$

Most van egy mátrixunk 3-as fokozattal (aláírással rendezve): $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{mátrix}}{\begin{aligned}\\\bal.{\begin{aligned}\\\\\\\\\\\\\\\\\\end{aligned} }\jobbra)\end{igazított}}\end{tömb}}

és háromszög alakúra redukálás után:

{\begin{array}{ll}{\begin{aligned}\\B_{3}={\begin{aligned}yf_{3}(ye_{3})\\yf_{4}(ye_{ 2})\\{\aláhúzás {xf_{4}}}(xe_{2})\\zf_{3}(ze_{3})\\zf_{4}(ze_{2})\\zf_{5 }(ze_{1})\\{\aláhúzás {yf_{5}}}(ye_{1})\\{\aláhúzás {xf_{5}}}(xe_{1})\end{aligned}}\ vége igazítva}}{\begin{mátrix}x^{2}y&xy^{2}&y^{3}&x^{2}z&xyz&y^{2}z&xz^{2}&yz^{2}&z^{3} \ 1 1}}&{\underline {18}}&15\\0&0&0&1&18&19&8&5&7\\0&0&0&0&1&3&2&4&22\\0&0&0&0&0&1&12&20&18\\0&0&0&0&0&0&\mathbf {1} &11&13\\0&0&0&0&0&0&0&\mathbf {1} &18\end{ \begin{aligned}\\\ \\\\\\\\\\\\\vége{igazított}}\jobbra)\vége{igazított}}\end{tömb}}

és polinom , és a 3. fokozatú kritikus párok redukciójának eredményei. Vegyük észre, hogy bár , a jelölt polinom nem -redukálható -ra . Így még mindig "új" polinom. $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))$

Most már sokkal világosabb az írott kritérium jelentése. A mátrix összeállításakor zárójelben felsoroljuk az egyes sorok (polinomok) aláírásait. Az azonos szignatúrájú címkézett polinomok a mátrix ugyanabban a sorában jelennek meg, így elég csak a legfrissebb eredményekkel foglalkozni (ezért gondoljuk át a címkézett polinomok létrehozásának sorrendjét). Az egyoldalú redukció is nyilvánvaló a mátrixban . Nézzük a vonalat . Az aláhúzott 0, 0 a és a vonalakon csökken , míg az aláhúzott 8,1,18 a és a vonalakon nincs kizárva . ennek az az oka, hogy az algoritmus redukciója egyirányú csökkentés. Pontosabban a karakterlánc-aláírások és a this and , amelyek mindketten kisebbek a karakterláncnál . $A_{3}$ ${\megjelenítési stílus 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))$ $xe_{2}$ $xf_{4}(xe_{2})$

Így a karakterláncok és képesek csökkenteni a karakterláncot . Azonban van olyan karakterlánc , és nem vágja el a karakterláncokat . Vegye figyelembe, hogy mivel csak a és sorokat kell tárolni, a többi sor nem lesz teljesen redukálva a mátrixban . $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})$ ${\megjelenítési stílus B_{3))$

Tudnunk kell azonban, hogy míg az algoritmus két új kritériuma szinte minden haszontalan számítást elvethet, az egyirányú redukció alacsonyabb mátrix eliminációs hatékonyságot eredményez, mint a . $\mathbb {F} _{5}$ ${\displaystyle \mathbb {F} _{4))$

Irodalom

J.-C. Faug`ere. Egy új hatékony algoritmus a Grobner-bázisok nullára redukálása nélkül történő kiszámításához (F5).

M. Bardet, J.-C. Faug`ere, B. Salvy: Az F5 Grobner-alapú algoritmus összetettségéről.

C. Eder, J.-C. Faug`ere. Felmérés az aláírás-alapú Grobner-alapú számításokról.

Stegers, T., 2005. Faug'ere F5 Algorithm Revisited. Diploma-Mathematiker szakdolgozat