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 esos ceros comunes. Fue introducido por Bruno Buchberger simultáneamente con la definición de las bases de Gröbner.
El algoritmo euclidiano para el cálculo del máximo común divisor polinómico 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 conocer otros algoritmos de base de Gröbner, consulte Base de Gröbner § Algoritmos e implementaciones .
Una versión cruda de este algoritmo para encontrar una base para un ideal I de un anillo polinomial R procede de la siguiente manera:
El polinomio Si ij se conoce comúnmente como polinomio S , donde S se refiere a resta (Buchberger) o sizigia (otros). El par de polinomios al que está asociado se denomina comúnmente par crítico .
Existen numerosas formas de mejorar este algoritmo más allá de lo indicado anteriormente. Por ejemplo, se podrían reducir todos los elementos nuevos de F entre sí antes de agregarlos. Si los términos principales de f i y f j no comparten variables en común, entonces Si j siempre se reducirá a 0 (si usamos solo f i y f j para la reducción), por lo que no necesitamos calcularlo en absoluto.
El algoritmo termina porque aumenta consistentemente el tamaño del monomio ideal 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 al número de opciones que pueden cambiar dramáticamente 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
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 acotados por este valor, para obtener un algoritmo de complejidad .
Por otro lado, hay ejemplos [2] donde la base de Gröbner contiene elementos de grado
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 Buchberger para mejorar su eficacia. 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 los cuales tiene varios cientos de términos y coeficientes de varios cientos de dígitos.
