Algoritmo de Buchberger

Algoritmo para calcular bases de Gröbner

En la teoría de polinomios multivariados , el algoritmo de Buchberger es un método para transformar un conjunto dado de polinomios en una base de Gröbner , que es otro conjunto de polinomios que tienen los mismos ceros comunes y son más convenientes para extraer información sobre estos ceros comunes. Fue introducido por Bruno Buchberger simultáneamente con la definición de bases de Gröbner.

El algoritmo euclidiano para el cálculo del máximo común divisor de polinomios y la eliminación gaussiana de sistemas lineales son casos especiales del algoritmo de Buchberger cuando el número de variables o los grados de los polinomios son respectivamente iguales a uno.

Para otros algoritmos de base de Gröbner, consulte Base de Gröbner § Algoritmos e implementaciones .

Algoritmo

Una versión básica de este algoritmo para encontrar una base para un ideal I de un anillo polinomial R procede de la siguiente manera:

Entrada Un conjunto de polinomios F que genera I

Salida A Base de Gröbner G para I

1. G  := F
2. Para cada f _i , f _j en G , denotamos por g _i el término principal de f _i con respecto al ordenamiento monomial dado , y por a _ij el mínimo común múltiplo de g _i y g _j .
3. Elija dos polinomios en G y sea S _ij = ⁠un _ij/ yo_​⁠ yo − ⁠_​un _ij/ sol_​⁠ f _j (Tenga en cuenta que los términos principales aquí se cancelarán por construcción) .
4. Reducir S _ij con el algoritmo de división multivariante en relación con el conjunto G hasta que el resultado no sea más reducible. Si el resultado no es cero, añadirlo a G .
5. Repita los pasos 2 a 4 hasta considerar todos los pares posibles, incluidos aquellos que involucran los nuevos polinomios agregados en el paso 4.
6. Salida G

El polinomio S _ij se conoce comúnmente como polinomio S , donde S se refiere a la resta (Buchberger) o a la sicigia (otros). El par de polinomios con el que está asociado se conoce comúnmente como par crítico .

Existen numerosas formas de mejorar este algoritmo más allá de lo que se ha indicado anteriormente. Por ejemplo, se podrían reducir todos los nuevos elementos de _F entre sí antes de añadirlos. Si los términos principales de _fi y f no comparten variables en común, entonces _S ij _siempre se reducirá a 0 (si utilizamos solo fi y f para _la reducción), por lo que no es necesario calcularlo en absoluto.

El algoritmo termina porque aumenta constantemente el tamaño del ideal monomial generado por los términos principales de nuestro conjunto F , y el lema de Dickson (o el teorema de la base de Hilbert ) garantiza que cualquier cadena ascendente de este tipo debe eventualmente volverse constante.

Complejidad

La complejidad computacional del algoritmo de Buchberger es muy difícil de estimar, debido a la cantidad de opciones que pueden cambiar drásticamente el tiempo de cálculo. Sin embargo, TW Dubé ha demostrado ^[1] que los grados de los elementos de una base de Gröbner reducida siempre están acotados por

${\displaystyle 2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}}$,

donde n es el número de variables y d el grado total máximo de los polinomios de entrada. Esto permite, en teoría, utilizar álgebra lineal sobre el espacio vectorial de los polinomios de grado acotado por este valor, para obtener un algoritmo de complejidad . ${\displaystyle d^{2^{n+o(1)}}}$

Por otra parte, hay ejemplos ^[2] donde la base de Gröbner contiene elementos de grado

${\displaystyle d^{2^{\Omega (n)}}}$,

y el límite superior de complejidad anterior es óptimo. Sin embargo, estos ejemplos son extremadamente raros.

Desde su descubrimiento, se han introducido muchas variantes del algoritmo de Buchberger para mejorar su eficiencia. Los algoritmos F4 y F5 de Faugère son actualmente los algoritmos más eficientes para calcular bases de Gröbner y permiten calcular de forma rutinaria bases de Gröbner que constan de varios cientos de polinomios, cada uno de ellos con varios cientos de términos y coeficientes de varios cientos de dígitos.

Véase también

• Algoritmo de finalización de Knuth-Bendix
• Algoritmo de Quine-McCluskey : algoritmo análogo para el álgebra de Boole

Referencias

1. Dubé, Thomas W. (1990). "La estructura de ideales polinómicos y bases de Gröbner". Revista SIAM de Computación . 19 (4): 750–773. doi :10.1137/0219053.
2. Mayr, Ernst W; Meyer, Albert R (1982). "La complejidad de los problemas verbales para semigrupos conmutativos e ideales polinomiales". Avances en Matemáticas . 46 (3): 305–329. doi : 10.1016/0001-8708(82)90048-2 .

Lectura adicional

• Buchberger, B. (agosto de 1976). "Base teórica para la reducción de polinomios a formas canónicas". Boletín ACM SIGSAM . 10 (3). ACM: 19–29. doi :10.1145/1088216.1088219. MR  0463136. S2CID  15179417.
• David Cox, John Little y Donald O'Shea (1997). Ideales, variedades y algoritmos: una introducción a la geometría algebraica computacional y al álgebra conmutativa , Springer. ISBN 0-387-94680-2 . 
• Vladimir P. Gerdt, Yuri A. Blinkov (1998). Bases involutivas de ideales polinómicos , Matemáticas y computadoras en simulación, 45:519ff

Enlaces externos

• "Algoritmo de Buchberger", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Algoritmo de Buchberger en Scholarpedia
• Weisstein, Eric W. "Algoritmo de Buchberger". MundoMatemático .