F4 (algoritmo)

El algoritmo F4 fue propuesto por Jean-Charles Faugeré en 1999 como un nuevo algoritmo eficiente de cálculo de la base de Gröbner [1] . Este algoritmo calcula la base de Gröbner de un ideal en un anillo polinomial utilizando una serie de procedimientos estándar de álgebra lineal: reducciones de matrices. Es uno de los más rápidos hasta la fecha.

Algoritmo

Definiciones

La pareja crítica es miembro ${\ estilo de visualización (f_ {i}, f_ {j})}$

$T\cdot T\cdot K[x_{1},...,x_{n}]\cdot T\cdot K[x_{1},...,x_{n}],Par(f_ {i},f_{j}):=(HOK_{ij},t_{i},f_{i},t_{j},f_{j})$

tal que

$HOK(Par(f_{i},f_{j}))=HOK_{ij}=LT(t_{i}f_{i})=LT(t_{j}f_{j})=HOK( f_{i},f_{j})$

Definimos el grado de un par crítico como . $p_{i,j}=Par(f_{i},f_{j}),grado(p_{i,j})$ $grados(HOK_{i,j})$

Definimos los siguientes operadores: y $Izquierda(p_{i,j}):=t_{i}\cdot f_{i}$ $Derecha(p_{i,j}):=t_{j}\cdot f_{j}$

Pseudocódigo del algoritmo F4 (versión simplificada)

Entrada: ${\begin{cases}F{\text{ subconjunto finito }}K[X_{1},...,X_{n}]\\Sel{\text{ function }}List(Pares)\rightarrow Lista(Pares)\\{\text{tales que }}Sel(I)\neq \varnothing {\text{ if }}I\neq \varnothing \end{cases}}$

Salida: subconjunto finito $K[X_{1},...,X_{n}]$

$G:=F,{\tilde {F}}_{0}+:=F:=0{\text{ y }}P:=\{Par(f,g)|(f,g) \in G^{2}{\text{ c }}f\neq g\}$

mientras lo haces $P\neq \varnada$

${\ estilo de visualización d: = d + 1}$

$P_{d}:=Sel(p)$

${\displaystyle P:=P\barra invertida P_{d))$

$L_{d}:=Izquierda(P_{d})\cup Derecha(P_{d})$

${\tilde {F}}_{d}^{+}:=Reducción(L_{d},G)$

para hacer $h\in {\tilde {F}}_{d}^{+}$

${\displaystyle P:=P\cup \{Par(h,g)|g\in G\}G:=G\cup \{h\))$

devolver $GRAMO$

Algoritmo de reducción

Ahora podemos extender la definición de módulo de reducción de polinomios

subconjunto , hasta la reducción del subconjunto por $K[X_{1},...,X_{n}]$ $K[X_{1},...,X_{n}]$

módulo otro subconjunto : $K[X_{1},...,X_{n}]$

Entrada: L, G subconjuntos finitos $K[X_{1},...,X_{n}]$

Salida: subconjuntos finitos (puede estar vacío) $K[X_{1},...,X_{n}]$

$F:={\text{Preprocesamiento simbólico}}(L,G)$

${\tilde {F}}:={\text{Reducción de Gauss }}F{\text{ relativo}}<$

${\tilde {F}}^{+}:=\{f\in {\tilde {F}}|LT(f)\not \in LT(F)\}$

devolver ${\displaystyle {\tilde {F^{+))))$

No se utiliza ninguna operación aritmética: se trata de un preprocesamiento simbólico.

Algoritmo de preprocesamiento simbólico

Entrada: L, G subconjuntos finitos $K[X_{1},...,X_{n}]$

Salida: subconjuntos finitos $K[X_{1},...,X_{n}]$

${\ estilo de visualización F: = L}$

$Listo:=LT(F)$

mientras lo haces $T(F)\neq Listo$

$m\in T(F)\backslash Listo$

$Listo:=Listo\cup \{m\}$

si se lanza desde arriba módulo entonces $metro$ $GRAMO$

existe $g\in G{\text{ AND }}m^{'}\in T:m=m^{'}\cdot LT(g)$

${\displaystyle F:=F\cup \{m^{'}\cdot g\))$

devolver $F$

Lema

Para todos los polinomios tenemos ${\ Displaystyle p \ en L_ {d}}$ $p{\xrightarrow[{}]{G\taza {\tilde {F}}+}}0$

Teorema (sin demostración)

El algoritmo calcula la base de Gröbner G en $F_{4}$ $K[X_{1},...,X_{n}]$

tal que $F\subseteq G{\text{ I }}Id(G)=Id(F).$

Comentario

Si # es para todos , entonces el algoritmo se reduce al algoritmo de Buchberger . En este caso, la función Sel es la estrategia de selección equivalente al algoritmo de Buchberger. $Sel(I)=1$ $I\neq \varnada$ $F_{4}$

Función de selección

Entrada : lista de pares críticos $PAGS$

Salida : lista de pares críticos

$d:=min\{grados(lcm(p))\}$

$P_{d}:=\{p\in P|grado(lcm(p))=d\}$

devolver $P_d$

Llamamos a esta estrategia la estrategia normal para . $F_{4}$

Por tanto, si los polinomios de entrada son uniformes, llegamos a la potencia y d es la base de Gröbner.

En el siguiente paso, elegimos todos los pares críticos necesarios para calcular la base de Gröbner elevada a d+1.

Optimización del algoritmo F4

Hay varias formas de optimizar el algoritmo:

inclusión de la prueba de Buchberger (o prueba F5);

reutilización de todas las filas en las matrices dadas.

Algoritmo de criterios de Buchberger - implementación:

$(G_{nuevo},p_{nuevo}):=Actualizar(G_{antiguo},P_{antiguo},h)$

Entrada: ${\begin{cases}{\text{subconjunto final de }}G_{antiguo}{\text{ en }}K[X_{1},...,X_{n}]\\{\text { subconjunto finito }}P_{old}{\text{ de pares críticos en }}K[X_{1},...,X_{n}]\\0\neq h\in K[x_{1}, .. .,X_{n}]\end{casos}}$

Salida: subconjunto final de la lista actualizada de pares críticos $K[X_{1},...,X_{n}]$

Pseudocódigo del algoritmo F4 (con criterio)

Entrada: ${\begin{cases}F\subset K[X_{1},...,X_{n}]\\Sel{\text{ function }}Lista(Pares)\rightarrow Lista(Pares)\end {casos}}$

Salida: subconjunto finito de . $K[X_{1},...,X_{n}]$

$G:=\varnada {\text{ Y }}P:=\varnada {\text{Y }}d:=0$

mientras lo haces $F\neq \varnada$

$f:=primero(F);F:F\barra invertida \{f\}$

${\ estilo de visualización (G, P): = Actualizar (G, P, f)}$

mientras lo haces $P\neq \varnada$

${\ estilo de visualización d: = d + 1}$

${\displaystyle P_{d}:=Sel(P);P:=P\barra invertida P_{d))$

$L_{d}:=Izquierda(P_{d})\cup Derecha(P_{d})$

$({\tilde {F}}_{d}^{+},F_{d}):=Reducción(L_{d},G,(F_{i})_{d=1,.. .,(d-1)})$

por $P\neq {\tilde {F}}_{d}^{+}$

${\displaystyle P:=P\cup \{Par(h,g)|g\in G\))$

${\ estilo de visualización (G, P): = Actualizar (G, P, h)}$

devolver $GRAMO$

F4 y sus diferencias con el Algoritmo de Buchberger

Sea un conjunto finito de polinomios . Sobre la base de este conjunto, se construye una gran matriz dispersa, cuyas filas corresponden a polinomios de , y las columnas corresponden a monomios. La matriz contiene los coeficientes de polinomios en los monomios correspondientes. Las columnas de la matriz se ordenan según el orden monomio seleccionado (el monomio más alto corresponde a la primera columna). La reducción de tal matriz a una forma escalonada permite encontrar la base del tramo lineal de polinomios en el espacio de polinomios. $F$ $F$ $F$

Supongamos que en el algoritmo clásico de Buchberger se requiere realizar un paso de reducción del polinomio con respecto a , y al mismo tiempo se debe multiplicar por un monomio . En el algoritmo F4, y se colocará especialmente en la matriz . Se afirma que es posible preparar por adelantado un conjunto de todos los posibles reductores de multiplicación que pueden ser necesarios y colocarlos por adelantado en una matriz. [2] $F$ $gramo$ $gramo$ $METRO$ $F$ $METRO$ $gramo$

Generalizamos el algoritmo F4 [3] :

necesitamos reducir el polinomio con respecto al conjunto . Para esto nosotros $F$ $F$

(1) agregar a la matriz; $F$

(2) construimos el soporte del polinomio (el conjunto de monomios); ${\ matemáticas {M}}$ $F$

(3) si está vacío, finalizar el procedimiento; ${\ matemáticas {M}}$

(4) elegir el monomio máximo en (y descartarlo de ); $METRO$ ${\ matemáticas {M}}$ ${\ matemáticas {M}}$

(5) si no es divisible por ninguno de los elementos monomio más altos , vaya al paso (3); $METRO$ $F$

(6) en caso contrario elegimos el reductor ∈ (y el factor adicional ): entonces ; $r$ $F$ ${\ estilo de visualización t}$ $METRO$ ${\ estilo de visualización = LM}$ ${\ estilo de visualización tr}$

(7) agregar a la matriz; ${\ estilo de visualización tr}$

(8) agregue monomios del polinomio (excepto el más alto ) al conjunto ; ${\ estilo de visualización tr}$ $METRO$ ${\ matemáticas {M}}$

(9) vaya al paso (3).

Este procedimiento para rellenar una matriz con reductores multiplicados se denomina preprocesamiento simbólico . Además, en lugar de S-polinomios, puede colocar sus partes izquierda y derecha en la matriz (al reducir una fila por otra, obtiene automáticamente un S-polinomio).

Finalmente, la tercera diferencia con el algoritmo de Buchberger es que en el algoritmo F4 se permite colocar partes de varios S-polinomios elegidos de acuerdo con alguna estrategia en una matriz. Entonces, si se selecciona un polinomio S en cada paso, se repite el algoritmo clásico de Buchberger .

El otro extremo es cuando el conjunto de todos los S-polinomios disponibles se reduce en el siguiente paso. Esto tampoco es muy eficiente debido al gran tamaño de las matrices. El autor del algoritmo J.-Sh. Faugère propuso una estrategia normal para elegir S-polinomios para la reducción [4] , según la cual se eligen S-polinomios con el menor grado de lados izquierdo y derecho. Da buenos resultados empíricos para ordenar DegRevLex y su elección es natural para ideales homogéneos.

Se pueden hacer varias mejoras naturales al algoritmo. Como en el algoritmo clásico para calcular la base de Gröbner , los criterios de Buchberger se pueden utilizar para filtrar polinomios S obviamente innecesarios.

Implementaciones

Algoritmo F4 implementado

en FGb, implementación propia de Faugère [4] , que incluye interfaces para usarlo desde C / C++ o Maple ;
en el sistema de álgebra computacional Maple como método opcional = fgb de la función Groebner [gbasis] ;
en el sistema de álgebra computacional Magma , en el sistema de álgebra computacional SageMath.

Ejemplo

Tarea: Calcular la base de Gröbner para polinomios Primero , asignamos $\{f_{1}=abcd-1;f_{2}=abc+abd+acd+bcd;f_{3}=ab+bc+ad+cd;f_{4}=a+b+c +d\}$ $G={f_{4)),$ $P_{1}={Par(f_{3},f_{4})},$ ${\displaystyle L_{1}=\{(1,f_{3}),(b,f_{4})\))$

1) Preprocesamiento de símbolos $(L_{1},G,\varnada):$

$F_{1}=\{{f_{3},bf_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc,bd,cd\ }$

$abdominales$ Estoy listo ahora.

2) Preprocesamiento de símbolos $(L_{1},G,\varnada):$

$F_{1}=\{{f_{3},bf_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc,bd,cd\ }$

${\anuncio de estilo de visualización}$ desde arriba se reduce a . $f_{4}\en G$

3) Preprocesamiento de símbolos $(L_{1},G,\varnada):$

$F_{1}=\{{f_{3},bf_{4},df_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc ,bd,cd,d^{2}\}$

$segundo^{2}$ no se reduce a . $GRAMO$

cuatro) $F_{1}=\{{f_{3},bf_{4},df_{4}}\}.$

Representación matricial de la resultante : $F_{1}$

$A_{1}=M(F_{1})={\begin{pmatrix}\{&ab&b^{2}&bc&ad&bd&cd&d^{2}\}\\(df_{4})&0&0&0&1&1&1&1\\(f_{ 3})&1&0&1&1&0&1&0\\(bf_{4})&1&1&1&0&1&0&0\end{matrix}}$

Reducción gaussiana de la matriz resultante : $A_{1}$

${\tilde {A_{1}}}={\begin{pmatrix}\{&ab&b^{2}&bc&ad&bd&cd&d^{2}\}\\(df_{4})&0&0&0&1&1&1&1\\(f_{3} )&1&0&1&0&-1&0&-1\\(bf_{4})&0&1&0&0&2&0&1\end{matrix}}$

De esta matriz obtenemos:

${\tilde {F_{1}}}=[f_{5}=ad+bd+cd+d^{2},f_{6}=ab+bc-bd-d^{2},f_ {7}=b^{2}+2bd+d^{2}]$

Y desde entonces $ab,ad\in LT(F_{1})$

${\tilde {F_{1+))}=[f_{7}]$ y entonces $G=\{f_{4},f_{7}\}.$

Para el siguiente paso, debemos considerar $P_{2}=\{Par(f_{2},f_{4})\}$

De aquí $L_{2}=\{(1,f_{2}),(bc,f_{4})\}{\text{u}}{\mathcal {F}}=\{F_{1} \}.$

En el preprocesamiento simbólico, puede intentar simplificar utilizando los cálculos anteriores: $1\cdot f_{2}{\text{y}}bc\cdot f_{4}$

Por ejemplo, 1) Preprocesamiento de símbolos $LT(bcf_{4})=abc=LT(cf_{6}){\text{ y en lugar de }}bc\cdot f_{4}{\text{ puedes usar }}c\cdot f_ {6}$

$F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^ {2}\}$

2) Preprocesamiento de símbolos

$F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^ {2}\}$

3) Preprocesamiento de símbolos

$F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^ {2}\}$ $abd{\text{ se reduce a }}bcf_{4}{\text{ y también a }}bf_{5}$

Describamos la simplificación

Propósito: reemplazar cualquier producto con el producto , donde es la cadena previamente calculada, y divide el monomio $m\cdot f$ $(uf)\cdot f'$ ${\ estilo de visualización (t, f')}$ ${\ estilo de visualización uf}$ $metro$

En la primera versión del algoritmo: algunas filas de la matriz nunca se usan (filas en la matriz ). ${\tilde {F}}_{d}\barra invertida {\tilde {F}}_{d}^{+}$

Nueva versión del algoritmo: guardamos estas cadenas

$m\cdot f\in Filas(F)\rightarrow m^{'}\cdot f^{'}{\text{ c }}m\geq m^{'}$

$m\cdot f\in Filas(F)\rightarrow X_{k}\cdot f^{'}$

SIMPLIFY intenta reemplazar el producto con el producto , donde $m\cdot f$ $(ut)\cdot f^{'}$

${\ estilo de visualización (t, f ^ {'})}$ cadena ya calculada en reducción gaussiana, y ut divide el monomio m; Si hemos encontrado el mejor producto, llamamos recursivamente a la función SIMPLIFY:

Entrada: ${\begin{cases}t\in T{\text{monomio))\\t\in K[X_{1},...,X_{n}]{\text{polinomio))\\ F=(F_{i})_{d=1,...,(d-1)},{\text{ Donde }}F_{k}\in K[X_{1},...,X_ {n}]\end{casos}}$

Salida: El resultado es equivalente a ${\ estilo de visualización m^{'}*f^{'}}$ ${\ estilo de visualización t*f}$

para hacer $u\in {\text{lista de divisores}}t$

si $\exists j(1\leq j<d):(u\cdot f)\in F_{j}{\text{entonces))$

${\tilde {F}}_{j}{\text{Reducción gaussiana}}F_{j}{\text{ Relativa}}<$

$\existe!p\in {\tilde {F}}_{j}:LT(p)=LT(u*f)$

si $u\neq t{\text{entonces}}$

devolver $Simplificar({\frac {t}{u}},p,F)$

de lo contrario volver ${\ estilo de visualización 1 * p}$

devolver ${\ estilo de visualización t*f}$

Algoritmo PREPROCESAMIENTO SIMBÓLICO

Entrada: ${\begin{casos}L,G{\text{subconjuntos finitos}}K[X_{1},...,X_{n}]\\F=(F_{i})_{d= 1,...,(d-1)},{\text{ Donde }}F_{k}\\{\text{subconjunto final}}K[X_{1},...,X_{n}] \end{casos}}$

Salida: subconjunto finito de . $K[X_{1},...,X_{n}]$

${\ estilo de visualización F: = L}$

$Listo:=LT(F)$

mientras lo haces $T(F)\neq Listo$

$m\in T(F)\backslash Listo$

si se lanza desde arriba módulo entonces $metro$ $GRAMO$

existe $g\in G{\text{ AND }}m^{'}\in T:m=m^{'}\cdot LT(g)$

$F:=F\cup \{Simplificar(m^{'},g,F)\}$

devolver $F$

Ahora volvamos al ejemplo.

4) Preprocesamiento de símbolos

$F_{2}=\{{f_{2},cf_{6},bf_{5}}\},T(F_{2})=\{abc,bc^{2},abd,acd ,bcd,cd^{2},b^{2}d,bd^{2}\}$

Y así....

5) Preprocesamiento de símbolos

$F_{2}=[cf_{5},df_{7},bf_{5},f_{2},cf_{6}]$

$A_{2}=M(F_{2})={\begin{bmatrix}0&0&0&0&1&1&1&0&1&0&0\\0&0&0&1&0&0&0&2&0&1&0\\0&0&1&1&0&1&0&1&0&0&0\\1&0&1&0&1&1&0&0&0&0&0\\1&1&0&0&0&-1&0&0&-1&0&0\end{bmatrix}}$

Después de la reducción de Gauss:

${\tilde {A_{2))}={\tilde {M(F_{2))}={\begin{bmatrix}0&0&0&0&1&1&1&0&1&0\\0&0&0&1&0&0&0&0&2&0&1\\0&0&1&0&0&1&0&-1&0&-1\\1&0&0&0&0&-1& - 1&1&-1&1\\0&1&0&0&0&0&1&-1&0&-1\end{bmatriz}}$

${\tilde {F_{2}}}={\begin{bmatrix}f_{9}=acd+bcd+c^{2}d+cd^{2},\\f_{10}=b ^{2}d+2bd^{2}+d^{3},\\f_{11}=abd+bcd-bd^{2}-d^{3},\\f_{12}=abc- bcd-c^{2}d+bd^{2}-cd^{2}+d^{3},\\f_{13}=bc^{2}+c^{2}d-bd^{ 2}-d^{3}\end{bmatriz}}$

y ${\displaystyle G=\{f_{4},f_{7},f_{13}\))$

En el siguiente paso tenemos:

$L_{3}=\{(1,f_{1}),(bcd,f_{4}),(c^{2},f_{7}),(b,f_{13})\ }$

y llame recursivamente a la simplificación:

$Simplificar(bcd,f_{4})=Simplificar(cd,f_{6})=Simplificar(d,f_{12})=(d,f_{12})$

En el siguiente paso tenemos:

$L_{3}=\{(1,f_{1}),(bcd,f_{4}),(c^{2},f_{7}),(b,f_{13})\ }$ y $F_{3}=[f_{1},df_{12},c^{2}f_{7},bf_{13},df_{13},df_{10}]$

Después de algunos cálculos, resulta que el rango es 5. ${\ estilo de visualización M (F_ {3})}$

Esto significa que hay una anulación inútil.

En el siguiente paso tenemos:

$L_{3}=\{(1,f_{1}),(bcd,f_{4}),(c^{2},f_{7}),(b,f_{13})\ }$ y $F_{3}=[f_{1},df_{12},c^{2}f_{7},bf_{13}]$

Preprocesamiento de símbolos

$F_{3}=[f_{1},df_{12},c^{2}f_{5},bf_{13},df_{13},df_{10}]$

${\tilde {F_{3}}}={\begin{bmatrix}f_{15}=c^{2}b^{2}-c^{2}d^{2}+2bd^{ 3}+2d^{4},\\f_{16}=abcd-1,\\f_{17}=-bcd^{2}-c^{2}d^{2}-bd^{3} -d^{4}+1,\\f_{18}=c^{2}bd+c^{2}d^{2}-bd^{3}-d^{4},\\f_{ 19}=b^{2}d^{2}+2bd^{3}+d^{4}\end{bmatriz}}$

Enlaces

https://en.wikipedia.org/wiki/Magma_(computer_algebra_system)

Notas

↑ Jean-Charles Faugère. Un nuevo algoritmo eficiente para calcular bases de Gr¨obner (f4). Diario de Álgebra Pura y Aplicada. — 1999.
↑ Estudio de bases de Gröbner // msu. Archivado desde el original el 11 de julio de 2019.
↑ [ http://www.broune.com/papers/f4.pdf EL ALGORITMO F4 QUE ACELERA LOS CÁLCULOS EN BASE DE GROBNER USANDO ÁLGEBRA LINEAL] // BJARKE HAMMERSHOLT ROUNE. Archivado desde el original el 30 de diciembre de 2019.
↑ 1 2 ¿ La propia implementación de Faugère ? . Consultado el 1 de diciembre de 2020. Archivado desde el original el 15 de junio de 2021. (indefinido)

Literatura

J.-C. Faug'ere. Un nuevo algoritmo eficiente para calcular bases de Gr¨obner sin reducción a cero (F5).
J.-C. Faug'ere Un Nuevo Algoritmo Eficiente para Calcular Bases de Gr¨obner (F4). Revista de álgebra pura y aplicada, 139 (1999), 61–88.
Cox D., Little J., O'Shea D., Ideales, Variedades y Algoritmos. Una introducción a la geometría algebraica computacional y al álgebra conmutativa, Nueva York, NY: Springer, 1998]