F5 (algoritm)

Algoritmul F5 pentru calcularea bazei Gröbner a fost propus de J.-Ch. Foger în 2002. În această lucrare, vom lua în considerare versiunea sa matriceală, care funcționează pentru polinoame omogene . Procedura principală a acestui algoritm calculează baza Gröbner d, adică submulțimea bazei Gröbner în raport cu care toate polinoamele de la un ideal de grad de cel mult d sunt reduse la zero.

În algoritmul F5, fiecare polinom rezultat este asociat cu o semnătură (o pereche de monom și un număr generator) care codifică informații despre originea acestui polinom. Ideea principală este de a nu include, dacă este posibil, în matrice acele rânduri care vor fi evident dependente liniar de restul (adică vor fi reduse la zero.)

Pentru a face acest lucru, reducerile sunt limitate la cele care nu modifică semnătura elementelor, iar printre următoarele polinoame care se procesează, sunt considerate doar cele a căror monom de semnătură nu este divizibil cu niciunul dintre cel mai înalt monom al elementelor deja găsite ale bazei. .

Pseudocod al algoritmului matriceal F5

Intrare: polinoame omogene cu puteri gradul maxim . $f_{1},\dots,f_{m)$ $d_{1}\leqslant \dots \leqslant d_{m};$ $D$

Ieșire: elemente de grad nu mai mari decât baza Gröbner redusă din pentru . $D$ $f_{1},\dots,f_{i)$ $i={\overline {1,m))$

Algoritm:

pentru i de la 1 la n do Gᵢ := 0 ; sfârșit pentru // inițializează bazele Gröbner Gᵢ din (f, …, fᵢ). pentru d₁ de la d la D do ℳ _ { d , 0 } := 0 , ℳ̅ _ { d , 0 } := 0 pentru i de la 1 la m fac dacă d < dᵢ atunci ℳ _ { d , i } := ℳ _ { d , i - 1 } altfel dacă d = dᵢ atunci ℳ _ { d , i } : = adăugați noul rând fᵢ la ℳ̅ _ { dᵢ , i - 1 } cu index ( i , 1 ) altfel ℳ _ { d , i } := ℳ̅ _ { d , i - 1 } Crit := LT ( ℳ̅ _ { d - dᵢ , i - 1 }) pentru f în Rânduri ( ℳ _ { d - 1 , i }) \ Rânduri ( ℳ _ { d - 1 , i - 1 }) nu ( i , u ) := index ( f ) , cu u = x_ { j₁ } , … , x_ { jd - dᵢ - 1 } , și 1 ≤ j₁ ≤ … ≤ j_ { d - dᵢ - 1 } ≤ n pentru j de la j_ { d - dᵢ - 1 } la n do dacă uxⱼ ∉ Crit atunci adăugați noul rând xⱼf cu indicele ( i , uxⱼ ) în ℳ _ { d , i } _ sfârşitul dacă sfârşitul pentru sfârşitul pentru sfârşitul dacă Calculați ℳ̅ _ { d , i } prin eliminarea gaussiană din ℳ _ { d , i } Adăugați la Gᵢ toate rândurile de ℳ̅ _ { d , i } nereductibile cu LT ( Gᵢ ) _ sfârşitul pentru sfârşitul pentru întoarcere [ Gᵢ | i = 1 , … , m ]

Bucla for de pe linia 14 construiește o matrice care conține toate polinoamele din c (cu excepția celor care anulează trivial). Pentru a evita calculele redundante, acestea sunt construite din rândurile matricei anterioare , adică toate rândurile sunt înmulțite cu toate variabilele. Rândul de la indexul c poate apărea din mai multe rânduri în , îl putem construi din rândul indexat la , c și îl putem înmulți cu , cea mai mare variabilă care apare în . Acest lucru asigură că fiecare rând este luat de exact un rând al matricei anterioare. $M_{d,i)$ $x_{1}^{\alpha _{1}}\dots x_{n}^{\alpha _{n}}f_{i}$ $\alpha _{1}+\dots +\alpha _{n}=d-d_{i)$ $M_{d-1,i)$ $(i,x_{1}^{\alpha _{1))\dots x_{j}^{\alpha _{j)))$ $\alpha _{j}\neq 0$ $M_{d-1,i)$ $(i,u)$ $M_{d-1,i)$ $u=x_{1}^{\alpha _{1}}\dots x_{j}^{\alpha _{j-1}}$ $x_{j}$ $u$

Un exemplu de algoritm F5

Se consideră un sistem omogen în ordine lexografică inversă gradată prin algoritmul matricei . $\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}\\\ sfârșit{cazuri}}

Pentru a calcula baza Gröbner , definim , și , și luăm în considerare perechile critice și . Ca și în algoritm , folosim partea matricei putere-2 pentru a aduce împreună aceste trei perechi critice: ${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})$ $\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{ aliniat}}\end{aliniat}}&{\begin{aliniat}\\\left({\begin{aliniat}\\\\\\\end{aliniat}}\right.\end{aliniat}}{\ începe{matrice}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{matrice)){\begin{aligned}{\\\begin{aligned} }\\\\\\\end{aliniat}}\right)\end{aliniat}}\end{aliniat}}

și după aducerea matricei într-o formă triunghiulară: $A_{2}$

{\begin{array}{ll}{\begin{aligned}\\B_{2}={\begin{aligned}f_{3}\\{\underline {f_{2)}}\\f_ {1}\end{aliniat}}\end{aliniat}}&{\begin{aliniat}\\\left({\begin{aliniat}\\\\\\\end{aliniat}}\right.\end {aliniat}}{\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{matrice}}{\begin{aliniat}\\\left.{\begin{aliniat}\\\\\\\end{aliniat}}\right)\end{aliniat }}\end{matrice}}}

si apar doua polinoame „noi”: si , care sunt rezultatul scaderii perechilor critice si . Rețineți că semnătura polinomului este , care corespunde etichetei din stânga acestui rând (subliniată în matrice ). $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}]$ $f_{4)$ $e_{{2}}$ $f_{2)$ $B_{2)$

De asemenea, rețineți că 18 subliniat nu este redus cu , deoarece semnătura este , care este mai mică de . În timp ce 0 subliniat este decrementat din . Acest lucru demonstrează că reducerea algoritmului este o reducere unidirecțională. $f_{4)$ $f_{3)$ $e_{3)$ $e_{{2}}$ $e_{1}\succ e_{2)$ $\mathbb {F} _{5}$

Următorul pas este să luăm în considerare noi perechi critice: și . Selectăm perechi după grad și construim o matrice de gradul 3 pentru a lucra împreună cu următoarele perechi critice . Trebuie să luăm în considerare doar părți , cu părți care sunt inscriptibile și respectiv. $[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))$ $yf_{2},yf_{1)$ $F_{4}$ $F_{5}$

Ca și algoritmul , părțile sunt acele rânduri care urmează să fie reduse în Matrix și, de asemenea, trebuie să selectăm părțile care sunt utilizate pentru a reduce acele rânduri. Deoarece sunt părți , trebuie să adăugăm părți la matrice pentru a le elimina. $\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}$

Avem acum o matrice cu gradul 3 (ordonată după semnătură): $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}\\\left.{\begin{aligned}\\\\\\\\\\\\\\\\\end{aligned} }\right)\end{aliniat}}\end{matrice}}

iar după reducerea la o formă triunghiulară:

{\begin{array}{ll}{\begin{aligned}\\B_{3}={\begin{aligned}yf_{3}(ye_{3})\\yf_{4}(ye_{ 2})\\{\subline {xf_{4}}}(xe_{2})\\zf_{3}(ze_{3})\\zf_{4}(ze_{2})\\zf_{5 }(ze_{1})\\{\underline {yf_{5}}}(ye_{1})\\{\underline {xf_{5}}}(xe_{1})\end{aligned}}\ end{aliniat}}&{\begin{aliniat}\\\left({\begin{aliniat}\\\\\\\\\\\\\\\\end{aliniat}}\right.\end { aliniat}}{\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} &{\underline {0}}&{\underline {0}}&{\underline {8}}&{\underline {1}}&{\underline {0}}&{\underline {0}}&{\underline {8}}&{\underline {1}}}&{\underline {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}\\\ \\\\\\\\\\\\\end{aliniat}}\right)\end{aliniat}}\end{aliniat}}

și polinom și sunt rezultatele reducerii perechilor critice cu gradul 3. Rețineți că, deși , polinomul etichetat nu este -reductibil la . Astfel, este încă un polinom „nou”. $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})$ $F_{6)$ $\mathbb {F} _{5}$ $F_{5}$ $f_{6)$

Acum sensul criteriului scris este mult mai clar. La construirea matricei , enumerăm semnăturile fiecărui rând (polinom) în paranteze. Polinoamele etichetate cu aceleași semnături vor apărea în același rând al matricei, așa că este suficient să ne ocupăm de ultimele rezultate (de aceea ne gândim la ordinea în care sunt create polinoamele etichetate). De asemenea, reducerea unilaterală este evidentă în matrice . Să ne uităm la linie . 0, 0 subliniat scad pe linii și respectiv, în timp ce 8,1,18 subliniat nu sunt excluse pe linii și . motivul este că reducerea algoritmului este o reducere unidirecțională. Mai precis, semnăturile șirului și this și , care sunt ambele mai mici decât șirul . $A_{3}$ $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})$ $ze_{3)$ $ze_{2)$ $xe_{2)$ $xf_{4}(xe_{2})$

Astfel, șirurile și sunt capabile să reducă șirul . Cu toate acestea, avem atât șiruri și nu tăiem șiruri . Rețineți că, deoarece numai rândurile și trebuie stocate, celelalte rânduri nu sunt complet reduse în matrice . $zf_{3}(ze_{3})$ $zf_{4}(ze_{2})$ $xf_{4}(xe_{2})$ $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})$ $B_{3}$

Cu toate acestea, trebuie să realizăm că, în timp ce cele două noi criterii ale algoritmului pot elimina aproape toate calculele inutile, reducerea unidirecțională are ca rezultat o eficiență mai mică de eliminare a matricei decât . $\mathbb {F} _{5}$ $\mathbb {F} _{4)$

Literatură

J.-C. Faug`ere.Un nou algoritm eficient pentru calcularea bazelor Grobner fără reducere la zero (F5).

M. Bardet, J.-C. Faug`ere, B. Salvy, Despre complexitatea algoritmului F5 Grobner.

C. Eder, J.-C. Faug`ere. Un sondaj asupra calculelor bazate pe semnătură Grobner.

Stegers, T., 2005. Algoritmul F5 al lui Faug'ere revizuit. Teză pentru gradul de Diplom-Mathematiker