El algoritmo de Buchberger

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 con raíces comunes y que resulta más conveniente para extraer información sobre dichas raíces. Fue introducido por Bruno Buchberger simultáneamente con la definición de las bases de Gröbner.

El algoritmo euclidiano para calcular el máximo común divisor de un polinomio es un caso especial del algoritmo de Buchberger, restringido a polinomios de una sola variable. La eliminación gaussiana de un sistema de ecuaciones lineales es otro caso especial donde el grado de todos los polinomios es igual a uno.

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

Una versión rudimentaria de este algoritmo para encontrar una base para un ideal I de un anillo de polinomios 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 , denotemos por g _i el término principal de f _i con respecto al orden 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 = ⁠ a _ij / g _i ⁠ f _i − ⁠ a _ij / g _j ⁠ f _j (Los términos principales aquí se cancelarán por construcción) .
4. Reduzca S _ij , con el algoritmo de división multivariada relativo al conjunto G hasta que el resultado no sea más reducible. Si el resultado es distinto de cero, agréguelo a G .
5. Repita los pasos 2 a 4 hasta que se hayan considerado 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 el polinomio S , donde S se refiere a la resta (Buchberger) o a la sizigia (otros). El par de polinomios con los que se asocia se conoce comúnmente como par crítico .

Existen muchas maneras de mejorar este algoritmo más allá de lo ya mencionado. Por ejemplo, todos los nuevos elementos de F pueden reducirse entre sí antes de sumarlos. Si los términos principales de f _i y f _j no comparten variables, entonces S _ij siempre se reducirá a 0 (si se utilizan únicamente f _i y f _j para la reducción), por lo que no es necesario calcularlo.

El algoritmo termina porque está aumentando 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.

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-1}}}$,

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 otro lado, 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 mencionado anteriormente es óptimo. Sin embargo, tales 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 más eficientes para calcular bases de Gröbner y permiten calcular rutinariamente bases de Gröbner compuestas por varios cientos de polinomios, cada uno con varios cientos de términos y coeficientes de varios cientos de dígitos.

Al menos una implementación del algoritmo de Buchberger ha sido demostrada como correcta dentro del asistente de pruebas Rocq (anteriormente llamado Coq). ^{[ 3 ]}

En la biblioteca SymPy para Python , el algoritmo de Buchberger (mejorado) se implementa como sympy.polys.polytools.groebner(). ^{[ 4 ]}

• Algoritmo de completación de Knuth-Bendix
• Algoritmo de Quine-McCluskey : algoritmo análogo para el álgebra booleana.

• Buchberger, B. (agosto de 1976). "Fundamentos teóricos 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 polinomiales , Matemáticas y computadoras en simulación, 45:519 y ss.

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