F5 (algoritmo)

El algoritmo F5 para calcular la base de Gröbner fue propuesto por J.-Ch. Foger en 2002. En este artículo, consideraremos su versión matricial, que funciona para polinomios homogéneos . El procedimiento principal de este algoritmo calcula la base d de Gröbner, es decir, el subconjunto de la base de Gröbner con respecto al cual todos los polinomios de un ideal de grado como máximo d se reducen a cero.

En el algoritmo F5, cada polinomio resultante está asociado con una firma (un par de un monomio y un número generador) que codifica información sobre el origen de este polinomio. La idea principal es no incluir, si es posible, en las matrices aquellas filas que obviamente serán linealmente dependientes con el resto (es decir, se reducirán a cero).

Para ello, se limitan las reducciones a aquellos que no modifican la firma de los elementos, y entre los siguientes polinomios en proceso, se consideran únicamente aquellos cuyo monomio de firma no es divisible por ninguno de los monomios más altos de los elementos ya encontrados de la base. .

Pseudocódigo del algoritmo de matriz F5

Entrada: polinomios homogéneos con potencias de máximo grado . ${\displaystyle f_{1},\puntos,f_{m))$ $d_{1}\leqslant \puntos \leqslant d_{m};$ $D$

Salida: elementos de grado no superior a la base de Gröbner reducida de para . ${\ estilo de visualización D}$ ${\displaystyle f_{1},\puntos,f_{i))$ $i={\overline {1,m))$

Algoritmo:

para i de 1 an do Gᵢ : = 0 ; end for // inicializa las Bases de Gröbner Gᵢ de (f, …, fᵢ). para d₁ de d a D hacer ℳ _ { re , 0 } := 0 , ℳ̅ _ { re , 0 } := 0 para i de 1 a m do si d < dᵢ entonces ℳ _ { d , i } := ℳ _ { d , i - 1 } de lo contrario si d = dᵢ entonces ℳ _ { d , i } := agregue la nueva fila fᵢ a ℳ̅ _ { dᵢ , i - 1 } con índice ( i , 1 ) más ℳ _ { re , yo } := ℳ̅ _ { re , yo - 1 } Crítico := LT ( ℳ̅ _ { d - dᵢ , i - 1 }) para f en Filas ( ℳ _ { d - 1 , i }) \ Filas ( ℳ _ { d - 1 , i - 1 }) hacer ( yo , u ) := índice ( f ) , con u = x_ { j₁ } , ... , x_ { jd - dᵢ - 1 } , y 1 ≤ j₁ ≤ … ≤ j_ { re - dᵢ - 1 } ≤ norte para j de j_ { d - dᵢ - 1 } a n do si uxⱼ ∉ Crit entonces agregue la nueva fila xⱼf con índice ( i , uxⱼ ) en ℳ _ { d , i } terminar si fin para fin para terminar si Calcule ℳ̅ _ { d , i } por eliminación gaussiana de ℳ _ { d , i } Agregue a Gᵢ todas las filas de ℳ̅ _ { d , i } no reducibles por LT ( Gᵢ ) fin para fin para volver [ Gᵢ | yo = 1 , ... , metro ]

El ciclo for en la línea 14 construye una matriz que contiene todos los polinomios en c (excepto aquellos que anulan trivialmente). Para evitar cálculos redundantes, se construyen a partir de las filas de la matriz anterior , es decir, todas las filas se multiplican por todas las variables. La fila en el índice c puede ocurrir a partir de múltiples filas en , podemos construirla a partir de la fila indexada en c , y multiplicarla por , la variable más grande que ocurre en . Esto asegura que cada fila se tome exactamente de una fila de la matriz anterior. ${\ Displaystyle M_ {d, yo}}$ $x_{1}^{\alpha _{1}}\dots x_{n}^{\alpha _{n}}f_{i}$ ${\ estilo de visualización \ alfa _ {1} + \ puntos + \ alfa _ {n} = d-d_ {i}}$ ${\ Displaystyle M_ {d-1, yo}}$ $(i,x_{1}^{\alpha _{1))\dots x_{j}^{\alpha _{j)))$ ${\ estilo de visualización \ alfa _ {j} \ neq 0}$ ${\ Displaystyle M_ {d-1, yo}}$ ${\ estilo de visualización (i, u)}$ ${\ Displaystyle M_ {d-1, yo}}$ $u=x_{1}^{\alpha _{1}}\dots x_{j}^{\alpha _{j-1}}$ $x_{j}$ $tu$

Un ejemplo del algoritmo F5

Considere un sistema homogéneo con orden lexográfico inverso graduado por el algoritmo matricial . ${\ estilo de visualización \ mathbb {F} _ {23} [x, y, z]}$ $(x\succ y\succ z)$ ${\ estilo de visualización F5}$

{\begin{casos}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}\\\ fin {casos}}

Para calcular la base de Gröbner , definimos , y , y consideramos los pares críticos y . Al igual que en el algoritmo , usamos la parte de la matriz power-2 para unir estos tres pares críticos: ${\ estilo de visualización {f_{1},f_{2},f_{3))}$ ${\ estilo de visualización F_ {1} = (e_ {1}, f_ {1})}$ ${\ estilo de visualización F_ {2} = (e_ {2}, f_ {2})}$ ${\ estilo de visualización F_ {3} = (e_ {3}, f_ {3})}$ ${\ estilo de visualización [F_{1},F_{2}]=(1,f_{1},1,f_{2}),[F_{1},F_{3}]=(1,f_{1} ,1,f_{3})}$ ${\ estilo de visualización [F_{2},F_{3}]=(1,f_{2},1,f_{3})}$ ${\ estilo de visualización \ mathbb {F} _ {4}}$ ${\ estilo de visualización 1xf_{1},1xf_{2},1xf_{3))$

{\begin{matriz}{ll}{\begin{alineado}\\A_{2}={\begin{alineado}f_{3}\\f_{2}\\f_{1}\end{ alineado}}\end{alineado}}&{\begin{alineado}\\\left({\begin{alineado}\\\\\\\end{alineado}}\right.\end{alineado}}{\ begin{matriz}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{matriz)){\begin{alineado}\\\left.{\begin{alineado }\\\\\\\end{alineado}}\right)\end{alineado}}\end{matriz}}

y después de llevar la matriz a una forma triangular: ${\ estilo de visualización A_ {2}}$

{\begin{matriz}{ll}{\begin{alineado}\\B_{2}={\begin{alineado}f_{3}\\{\subrayado {f_{2))}\\f_ {1}\end{alineado}}\end{alineado}}&{\begin{alineado}\\\left({\begin{alineado}\\\\\\\end{alineado}}\right.\end {alineado}}{\begin{matriz}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{matriz}}{\begin{alineado}\\\left.{\begin{alineado}\\\\\\\end{alineado}}\right)\end{alineado }}\end{matriz}}}

y aparecen dos polinomios "nuevos": y , que son el resultado de rebajar los pares críticos y . Tenga en cuenta que la firma del polinomio es , que corresponde a la etiqueta a la izquierda de esta fila (subrayada en la matriz ). $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}))$ ${\ estilo de visualización [F_{1},F_{2}],[F_{1},F_{3}]}$ ${\ estilo de visualización [F_{2},F_{3}]}$ ${\ Displaystyle f_ {4}}$ $e_{{2}}$ ${\ Displaystyle f_ {2}}$ ${\ Displaystyle B_ {2}}$

También tenga en cuenta que el 18 subrayado no se reduce por , ya que la firma es , que es menor que . Mientras que el 0 subrayado se decrementa desde . Esto prueba que la reducción en el algoritmo es una reducción unidireccional. ${\ Displaystyle f_ {4}}$ ${\ Displaystyle f_ {3}}$ $e_{3}$ $e_{{2}}$ ${\displaystyle e_{1}\succ e_{2))$ ${\ estilo de visualización \ mathbb {F} _ {5}}$

El siguiente paso es considerar nuevos pares críticos: y . Seleccionamos pares por grado y construimos una matriz de grado 3 para trabajar juntos con los próximos pares críticos . Solo necesitamos considerar partes , con partes que se pueden escribir y respectivamente. ${\ estilo de visualización [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})}$ ${\ estilo de visualización [F_{5},F_{3}]=(x^{2},f_{5},y^{2},f_{3})}$ ${\ estilo de visualización A_ {3}}$ ${\ estilo de visualización [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))$ ${\ estilo de visualización F_ {4}}$ ${\ estilo de visualización F_ {5}}$

Al igual que el algoritmo , las partes son aquellas filas que se van a reducir en Matrix y también debemos seleccionar las partes que se usan para reducir esas filas. Como son partes , debemos agregar partes a la matriz para eliminarlas. ${\ estilo de visualización \ 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))$ ${\ estilo de visualización A_ {3}}$

Ahora tenemos una matriz con grado 3 (ordenada por firma): ${\ estilo de visualización A_ {3}}$

{\begin{array}{ll}{\begin{alineado}\\A_{3}={\begin{alineado}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{alineado}}\end{alineado}}&{\begin{alineado}\\\left({ \begin{alineado}\\\\\\\\\\\\\\\\end{alineado}}\right.\end{alineado}}{\begin{matriz}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{matriz}}{\begin{alineado}\\\left.{\begin{alineado}\\\\\\\\\\\\\\\\end{alineado} }\right)\end{alineado}}\end{matriz}}

y después de la reducción a una forma triangular:

{\begin{array}{ll}{\begin{alineado}\\B_{3}={\begin{alineado}yf_{3}(ye_{3})\\yf_{4}(ye_{ 2})\\{\subrayado {xf_{4}}}(xe_{2})\\zf_{3}(ze_{3})\\zf_{4}(ze_{2})\\zf_{5 }(ze_{1})\\{\subrayado {yf_{5}}}(ye_{1})\\{\subrayado {xf_{5}}}(xe_{1})\end{alineado}}\ end{alineado}}&{\begin{alineado}\\\left({\begin{alineado}\\\\\\\\\\\\\\\\end{alineado}}\right.\end { alineado}}{\begin{matriz}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} &{\subrayado {0}}&{\subrayado {0}}&{\subrayado {8}}&{\subrayado {1}}&{\subrayado { 1}}&{\subrayado {18}}&15\\0&0&0&0&1&18&19&8&5&7\\0&0&0&0&1&3&2&4&22\\0&0&0&0&0&0&1&12&20&18\\0&0&0&0&0&0&\mathbf {1} &11&13\\0&0&0\end \0&0&bf\end \0&08&01} &matemáticas \\\\\\\\\\\\\end{alineado}}\right)\end{alineado}}\end{matriz}}

y polinomio y son los resultados de la reducción de pares críticos con grado 3. Nótese que aunque , el polinomio etiquetado no es -reducible a . Por lo tanto, sigue siendo un polinomio "nuevo". $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}}$ ${\ estilo de visualización \ mathbb {F} _ {5}}$ ${\ estilo de visualización F_ {5}}$ ${\ Displaystyle f_ {6}}$

Ahora el significado del criterio escrito es mucho más claro. Al construir la matriz , enumeramos las firmas de cada fila (polinomio) entre paréntesis. Los polinomios etiquetados con las mismas firmas aparecerán en la misma fila de la matriz, por lo que basta con tratar con los resultados más recientes (es por eso que pensamos en el orden en que se crean los polinomios etiquetados). También la reducción unilateral es evidente en la matriz . Miremos la línea . Los 0, 0 subrayados disminuyen en las líneas y respectivamente, mientras que los 8,1,18 subrayados no se excluyen en las líneas y . la razón es que la reducción en el algoritmo es una reducción unidireccional. Más específicamente, las firmas de cadena y this y , que son menores que la cadena . ${\ estilo de visualización A_ {3}}$ ${\ Displaystyle B_ {3}}$ $xf_{4}(xe_{2})$ $zf_{3}(ze_{3})$ $zf_{4}(ze_{2})$ $zf_{5}(ze_{1}),yf_{5}(vosotros_{1})$ $xf_{5}(xe_{1})$ ${\ estilo de visualización \ mathbb {F} _ {5}}$ $zf_{3}(ze_{3})$ $zf_{4}(ze_{2})$ ${\displaystyle ze_{3))$ ${\displaystyle ze_{2))$ ${\ Displaystyle xe_ {2}}$ $xf_{4}(xe_{2})$

Así, las cadenas y son capaces de reducir la cadena . Sin embargo, tenemos tan cuerdas y no cortamos cuerdas . Tenga en cuenta que dado que solo las filas y deben almacenarse, las otras filas no se reducen por completo en la matriz . $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}(vosotros_{1})$ $xf_{5}(xe_{1})$ $xf_{4}(xe_{2})$ $xf_{4}(xe_{2}),yf_{5}(vosotros_{1})$ $xf_{5}(xe_{1})$ ${\ Displaystyle B_ {3}}$

Sin embargo, debemos darnos cuenta de que, si bien los dos nuevos criterios del algoritmo pueden descartar casi todos los cálculos inútiles, la reducción unidireccional da como resultado una eficiencia de eliminación de matriz más baja que la de . ${\ estilo de visualización \ mathbb {F} _ {5}}$ ${\ estilo de visualización \ mathbb {F} _ {4}}$

Literatura

J.-C. Faug`ere. Un nuevo algoritmo eficiente para calcular bases de Grobner sin reducción a cero (F5).

M. Bardet, J.-C. Faug`ere, B. Salvy.Sobre la complejidad del algoritmo de base F5 Grobner.

C. Eder, J.-C. Faug`ere. Una encuesta sobre cálculos de base de Grobner basados en firmas.

Stegers, T., 2005. Revisión del algoritmo F5 de Faug'ere. Tesis para el grado de Diplom-Mathematiker