En matemáticas , y más específicamente en álgebra computacional, geometría algebraica computacional y álgebra conmutativa computacional , una base de Gröbner es un tipo particular de conjunto generador de un ideal en un anillo polinómico K [ x 1 ,…, x n ] sobre un campo K . Una base de Gröbner permite deducir fácilmente muchas propiedades importantes del ideal y la variedad algebraica asociada , como la dimensióny el número de ceros cuando es finito. El cálculo de bases de Gröbner es una de las principales herramientas prácticas para resolver sistemas de ecuaciones polinomiales y calcular las imágenes de variedades algebraicas bajo proyecciones o mapas racionales .
El cálculo de la base de Gröbner puede verse como una generalización multivariante, no lineal, tanto del algoritmo de Euclides para calcular los máximos divisores comunes polinomiales , como de la eliminación gaussiana para sistemas lineales. [1]
Las bases de Gröbner se introdujeron en 1965, junto con un algoritmo para calcularlas ( algoritmo de Buchberger ), por Bruno Buchberger en su Ph.D. tesis. Los nombró en honor a su asesor Wolfgang Gröbner . En 2007, Buchberger recibió la Association for Computing Machinery 's París Kanellakis Teoría y Práctica premio para este trabajo. Sin embargo, el matemático ruso Nikolai Günther había introducido una noción similar en 1913, publicada en varias revistas matemáticas rusas. Estos artículos fueron en gran parte ignorados por la comunidad matemática hasta que fueron redescubiertos en 1987 por Bodo Renschuch et al. [2] En 1964, Heisuke Hironaka desarrolló de forma independiente un concepto análogo para las series de potencias multivariadas , quien las denominó bases estándar . Este término ha sido utilizado por algunos autores para denotar también bases de Gröbner.
Muchos autores han extendido la teoría de las bases de Gröbner en diversas direcciones. Se ha generalizado a otras estructuras, como polinomios sobre anillos ideales principales o anillos polinomiales , y también a algunas clases de anillos y álgebras no conmutativas, como las álgebras de Ore .
Fondo
Anillo polinomial
Las bases de Gröbner se definen principalmente para ideales en un anillo polinomial sobre un campo K . Aunque la teoría funciona para cualquier campo, la mayoría de los cálculos de base de Gröbner se realizan cuando K es el campo de los racionales o los enteros módulo un número primo.
Un polinomio es una suma donde el son elementos distintos de cero de K y elson monomios o "productos energéticos" de las variables. Esto significa que un monomio M es un producto donde el son números enteros no negativos. El vectorse llama el vector exponente de M . La notación a menudo se abrevia como. Los monomios se definen de forma única por sus vectores exponentes, por lo que las computadoras pueden representar los monomios de manera eficiente como vectores exponentes y los polinomios como listas de vectores exponentes y sus coeficientes.
Si es un conjunto finito de polinomios en un anillo polinomial R , el ideal generado por F es el conjunto de combinaciones lineales de elementos de F con coeficientes en todo R :
Orden monomial
Todas las operaciones relacionadas con las bases de Gröbner requieren la elección de un orden total en los monomios, con las siguientes propiedades de compatibilidad con la multiplicación. Para todos los monomios M , N , P ,
- .
Un pedido total que satisface estas condiciones a veces se denomina pedido admisible .
Estas condiciones implican que el orden es un orden de pozo , es decir, cada secuencia estrictamente decreciente de monomios es finita.
Aunque la teoría de la base de Gröbner no depende de una elección particular de una ordenación monomial admisible, tres ordenaciones monomiales son especialmente importantes para las aplicaciones:
- Ordenamiento lexicográfico , comúnmente llamado lex o plex (para ordenamiento léxico puro).
- Orden lexicográfico inverso de grado total , comúnmente llamado degrevlex .
- Orden de eliminación , lexdeg .
La teoría de la base de Gröbner se introdujo inicialmente para el ordenamiento lexicográfico. Pronto se advirtió que la base de Gröbner para degrevlex es casi siempre mucho más fácil de calcular, y que casi siempre es más fácil calcular una base de lex Gröbner calculando primero la base degrevlex y luego usando un "algoritmo de cambio de orden". Cuando se necesita eliminación , degrevlex no es conveniente; se pueden usar tanto lex como lexdeg pero, de nuevo, muchos cálculos son relativamente fáciles con lexdeg y casi imposibles con lex.
Una vez que se fija el orden de un monomio, los términos de un polinomio (producto de un monomio con su coeficiente distinto de cero) se ordenan naturalmente por monomios decrecientes (para este orden). Esto hace que la representación de un polinomio como una lista ordenada de pares vector coeficiente-exponente sea una representación canónica de los polinomios. La primera (la más grande) término de un polinomio p para este pedido y la correspondiente monomio y el coeficiente se llaman, respectivamente, el término principal , que conduce monomio y coeficiente principal y denotado, en este artículo, LT ( p ), lm ( p ) y lc ( p ).
Reducción
El concepto de reducción , también llamado división multivariante o cálculo de forma normal , es fundamental para la teoría de bases de Gröbner. Es una generalización multivariante de la división euclidiana de polinomios univariados .
En esta sección suponemos una ordenación monomial fija, que no se definirá explícitamente.
Dados dos polinomios f y g , se dice que f es reducible por g si algún monomio m en f es un múltiplo del monomio principal lm ( g ) de g . Si m es el monomio principal de f, entonces se dice que f es reducible con plomo por g . Si c es el coeficiente de m en f y m = q lm ( g ), la reducción de un paso de f por g es la operación que asocia af el polinomio
Las principales propiedades de esta operación son que el polinomio resultante no contiene el monomio my que los monomios mayores que m (para el orden de los monomios) permanecen sin cambios. Esta operación no está, en general, definida de forma única; si varios monomios en f son múltiplos de lm ( g ), entonces se puede elegir arbitrariamente cuál reducir. En la práctica, es mejor elegir el más grande para el orden del monomio, porque de lo contrario las reducciones posteriores podrían reintroducir el monomio que se acaba de eliminar.
Dado un conjunto finito G de polinomios, se dice que f es reducible o de plomo-reducible por G si es reducible o de plomo-reducible, respectivamente, por un elemento g de G . Si es el caso, entonces se define. La reducción (completa) de f por G consiste en aplicar iterativamente este operador hasta obtener un polinomio , Que es irreducible por G . Se llama una forma normal de f por G . En general, esta forma no se define de forma única (no es una forma canónica ); esta no unicidad es el punto de partida de la teoría de bases de Gröbner.
Para los cálculos de base de Gröbner, excepto al final, no es necesario hacer una reducción completa: una reducción de plomo es suficiente, lo que ahorra una gran cantidad de cálculo.
La definición de la reducción muestra inmediatamente que, si h es una forma normal de f por G , entonces tenemos
donde el son polinomios. En el caso de polinomios univariados, si G consta de un solo elemento g , entonces h es el resto de la división euclidiana de f por g , q g es el cociente y el algoritmo de división es exactamente el proceso de reducción de adelanto. Por esta razón, algunos autores utilizan el término división multivariante en lugar de reducción.
Ejemplos de reducción
En los ejemplos de esta sección, los polinomios tienen tres indeterminados x , y y z , y el orden monomial que se usa es el orden monomial cones decir, para comparar dos monomios, primero se comparan los exponentes de x ; sólo cuando los exponentes de x son iguales, se comparan los exponentes de y ; y los exponentes de z se comparan solo cuando los demás exponentes son iguales.
Para tener una visión clara del proceso de reducción, uno tiene que reescribir polinomios con sus términos en orden decreciente. Por ejemplo, si
debe ser reescrito
Esto permite tener el monomio principal primero (para el orden elegido); aquí
Considere la reducción de por con y
Para el primer paso de reducción, se puede reducir el primero o el segundo término. Sin embargo, la reducción de un término equivale a eliminar este término a costa de agregar nuevos términos más bajos, y, si no es el primer término reducible que se reduce, es posible que una reducción adicional agregue un término similar, que debe ser reducido de nuevo. Por lo tanto, siempre es mejor reducir primero el término reducible más grande (para el orden monomial).
El término principal de f es reducible por Entonces el primer paso de reducción consiste en multiplicar por –2 x y sumando el resultado af :
Como el término principal de es un múltiplo de los principales monomios de ambos y uno tiene dos opciones para el segundo paso de reducción. Si uno elige se obtiene un polinomio que se puede reducir de nuevo por
No es posible una mayor reducción, así que se puede elegir para la reducción completa de f . Sin embargo, uno obtiene un resultado diferente con la otra opción para el segundo paso:
Por lo tanto, la reducción completa de f puede resultar en o
Se ha introducido el algoritmo de Buchberger para resolver las dificultades inducidas por esta no unicidad. En términos generales consiste en añadir a G los polinomios que son necesarios para la singularidad de la reducción por G .
Aquí el algoritmo de Buchberger comenzaría agregando a G el polinomio
En efecto, puede reducirse aún más por y esto produce de nuevo. Sin embargo, esto no completa el algoritmo de Buchberger, ya que xy da resultados diferentes, cuando se reduce por o
Definicion formal
Una base de Gröbner G de un I ideal en un anillo polinomial R sobre un campo es un conjunto generador de I caracterizado por cualquiera de las siguientes propiedades, expresadas en relación con algún orden monomial :
- el ideal generado por los términos principales de polinomios en I es igual al ideal generado por los términos principales de G ;
- el término principal de cualquier polinomio en I es divisible por el término principal de algún polinomio en G ;
- la división multivariante de cualquier polinomio en el anillo polinomial R por G da un resto único;
- la división multivariante por G de cualquier polinomio en el ideal I da el resto 0 .
Todas estas propiedades son equivalentes; diferentes autores utilizan diferentes definiciones según el tema que eligen. Las dos últimas propiedades permiten realizar cálculos en el anillo de factores R / I con la misma facilidad que la aritmética modular. Es un hecho significativo del álgebra conmutativa que las bases de Gröbner siempre existen y pueden calcularse eficazmente para cualquier ideal dado por un subconjunto generador finito.
La división multivariante requiere un ordenamiento monomial, la base depende del ordenamiento monomial elegido, y diferentes ordenamientos pueden dar lugar a bases de Gröbner radicalmente diferentes. Dos de los ordenamientos más utilizados son el ordenamiento lexicográfico y el orden lexicográfico inverso de grados (también llamado orden lexicográfico inverso graduado o simplemente orden de grados total ). El orden lexicográfico elimina las variables; sin embargo, las bases de Gröbner resultantes suelen ser muy grandes y costosas de calcular. El orden lexicográfico inverso de grados generalmente proporciona los cálculos de base de Gröbner más rápidos. En este orden, los monomios se comparan primero por grado total, con los lazos rotos tomando el monomio más pequeño con respecto al orden lexicográfico con las variables invertidas.
En la mayoría de los casos (polinomios en un número finito de variables con coeficientes complejos o, más generalmente, coeficientes sobre cualquier campo, por ejemplo), existen bases de Gröbner para cualquier orden monomial. El algoritmo de Buchberger es el método más antiguo y conocido para calcularlos. Otros métodos son los algoritmos F4 y F5 de Faugère , basados en las mismas matemáticas que el algoritmo de Buchberger, y los enfoques involutivos, basados en ideas del álgebra diferencial . [3] También hay tres algoritmos para convertir una base de Gröbner con respecto a un orden monomial a una base de Gröbner con respecto a un orden monomial diferente: el algoritmo FGLM , el algoritmo impulsado por Hilbert y el algoritmo de caminata de Gröbner . Estos algoritmos se emplean a menudo para calcular bases lexicográficas de Gröbner (difíciles) a partir de bases de Gröbner de grado total (más fáciles).
Una base de Gröbner se denomina reducida si el coeficiente principal de cada elemento de la base es 1 y no hay monomio en ningún elemento de la base en el ideal generado por los términos principales de los otros elementos de la base. En el peor de los casos, el cálculo de una base de Gröbner puede requerir un tiempo exponencial o incluso doblemente exponencial en el número de soluciones del sistema polinomial (para el orden lexicográfico inverso de grado y el orden lexicográfico, respectivamente). A pesar de estos límites de complejidad, tanto las bases de Gröbner estándar como las reducidas son a menudo computables en la práctica, y la mayoría de los sistemas de álgebra por computadora contienen rutinas para hacerlo.
El concepto y los algoritmos de las bases de Gröbner se han generalizado a submódulos de módulos libres sobre un anillo polinomial. De hecho, si L es un módulo libre sobre un anillo R , entonces se puede considerar R ⊕ L como un anillo definiendo el producto de dos elementos de L como 0. Este anillo puede identificarse con, where is a basis of L. This allows to identify a submodule of L generated by with the ideal of generated by and the products , . If R is a polynomial ring, this reduces the theory and the algorithms of Gröbner bases of modules to the theory and the algorithms of Gröbner bases of ideals.
The concept and algorithms of Gröbner bases have also been generalized to ideals over various rings, commutative or not, like polynomial rings over a principal ideal ring or Weyl algebras.
Ejemplo y contraejemplo
Let R = Q[x,y] be the ring of bivariate polynomials with rational coefficients and consider the ideal I = <f,g> generated by the polynomials
- f( x, y) = x2 − y
- g( x, y) = x3 − x
Two other elements of I are the polynomials
- k( x, y) = − xf( x, y) + g( x, y) = xy − x
- h( x, y) = xk( x, y) − ( y - 1) f( x, y) = y2 − y
Under lexicographic ordering with x > y we have
- lt( f) = x2
- lt( g) = x3
- lt( h) = y2
The ideal generated by {lt(f),lt(g)} only contains polynomials that are divisible by x2 which excludes lt(h) = y2; it follows that {f, g} is not a Gröbner basis for I.
On the other hand, we can show that {f, k, h} is indeed a Gröbner basis for I.
Firstly, f and g, and therefore also h, k and all the other polynomials in the ideal I have the following three zeroes in the (x,y) plane in common, as indicated in the figure: {(1,1),(−1,1),(0,0)}. Those three points are not collinear, so I does not contain any polynomial of the first degree. Neither can I contain any polynomials of the special form
- m( x, y) = cx + p( y)
with c a nonzero rational number and p a polynomial in the variable y only; the reason being that such an m can never have two distinct zeroes with the same value for y (in this case, the points (1,1) and (−1,1)).
From the above it follows that I, apart from the zero polynomial, only contains polynomials whose leading term has degree greater than or equal to 2; therefore their leading terms are divisible by at least one of the three monomials
- { x2, xy, y2} = {lt( f),lt( k),lt( h)}.
This means that {f, k, h} is a Gröbner basis for I with respect to lexicographic ordering with x > y.
Propiedades y aplicaciones de las bases Gröbner
Unless explicitly stated, all the results that follow[4] are true for any monomial ordering (see that article for the definitions of the different orders that are mentioned below).
It is a common misconception that the lexicographical order is needed for some of these results. On the contrary, the lexicographical order is, almost always, the most difficult to compute, and using it makes impractical many computations that are relatively easy with graded reverse lexicographic order (grevlex), or, when elimination is needed, the elimination order (lexdeg) which restricts to grevlex on each block of variables.
Equality of ideals
Reduced Gröbner bases are unique for any given ideal and any monomial ordering. Thus two ideals are equal if and only if they have the same (reduced) Gröbner basis (usually a Gröbner basis software always produces reduced Gröbner bases).
Membership and inclusion of ideals
The reduction of a polynomial f by the Gröbner basis G of an ideal I yields 0 if and only if f is in I. This allows to test the membership of an element in an ideal. Another method consists in verifying that the Gröbner basis of G∪{f} is equal to G.
To test if the ideal I generated by f1, …, fk is contained in the ideal J, it suffices to test that every fi is in J. One may also test the equality of the reduced Gröbner bases of J and J ∪ {f1, ...,fk}.
Solutions of a system of algebraic equations
Any set of polynomials may be viewed as a system of polynomial equations by equating the polynomials to zero. The set of the solutions of such a system depends only on the generated ideal, and, therefore does not change when the given generating set is replaced by the Gröbner basis, for any ordering, of the generated ideal. Such a solution, with coordinates in an algebraically closed field containing the coefficients of the polynomials, is called a zero of the ideal. In the usual case of rational coefficients, this algebraically closed field is chosen as the complex field.
An ideal does not have any zero (the system of equations is inconsistent) if and only if 1 belongs to the ideal (this is Hilbert's Nullstellensatz), or, equivalently, if its Gröbner basis (for any monomial ordering) contains 1, or, also, if the corresponding reduced Gröbner basis is [1].
Given the Gröbner basis G of an ideal I, it has only a finite number of zeros, if and only if, for each variable x, G contains a polynomial with a leading monomial that is a power of x (without any other variable appearing in the leading term). If it is the case the number of zeros, counted with multiplicity, is equal to the number of monomials that are not multiple of any leading monomial of G. This number is called the degree of the ideal.
When the number of zeros is finite, the Gröbner basis for a lexicographical monomial ordering provides, theoretically, a solution: the first coordinates of a solution is a root of the greatest common divisor of polynomials of the basis that depends only of the first variable. After substituting this root in the basis, the second coordinates of this solution is a root of the greatest common divisor of the resulting polynomials that depends only on this second variable, and so on. This solving process is only theoretical, because it implies GCD computation and root-finding of polynomials with approximate coefficients, which are not practicable because of numeric instability. Therefore, other methods have been developed to solve polynomial systems through Gröbner bases (see System of polynomial equations for more details).
Dimension, degree and Hilbert series
The dimension of an ideal I in a polynomial ring R is the Krull dimension of the ring R/I and is equal to the dimension of the algebraic set of the zeros of I. It is also equal to number of hyperplanes in general position which are needed to have an intersection with the algebraic set, which is a finite number of points. The degree of the ideal and of its associated algebraic set is the number of points of this finite intersection, counted with multiplicity. In particular, the degree of a hypersurface is equal to the degree of its definition polynomial.
Both degree and dimension depends only on the set of the leading monomials of the Gröbner basis of the ideal for any monomial ordering.
The dimension is the maximal size of a subset S of the variables such that there is no leading monomial depending only on the variables in S. Thus, if the ideal has dimension 0, then for each variable x there is a leading monomial in the Gröbner basis that is a power of x.
Both dimension and degree may be deduced from the Hilbert series of the ideal, which is the series , where is the number of monomials of degree i that are not multiple of any leading monomial in the Gröbner basis. The Hilbert series may be summed into a rational fraction
where d is the dimension of the ideal and is a polynomial such that is the degree of the ideal.
Although the dimension and the degree do not depend on the choice of the monomial ordering, the Hilbert series and the polynomial change when one changes of monomial ordering.
Most computer algebra systems that provide functions to compute Gröbner bases provide also functions for computing the Hilbert series, and thus also the dimension and the degree.
Elimination
The computation of Gröbner bases for an elimination monomial ordering allows computational elimination theory. This is based on the following theorem.
Consider a polynomial ring in which the variables are split into two subsets X and Y. Let us also choose an elimination monomial ordering "eliminating" X, that is a monomial ordering for which two monomials are compared by comparing first the X-parts, and, in case of equality only, considering the Y-parts. This implies that a monomial containing an X-variable is greater than every monomial independent of X. If G is a Gröbner basis of an ideal I for this monomial ordering, then is a Gröbner basis of (this ideal is often called the elimination ideal). Moreover, consists exactly of the polynomials of G whose leading terms belong to K[Y] (this makes very easy the computation of , as only the leading monomials need to be checked).
This elimination property has many applications, some of them are reported in the next sections.
Another application, in algebraic geometry, is that elimination realizes the geometric operation of projection of an affine algebraic set into a subspace of the ambient space: with above notation, the (Zariski closure of) the projection of the algebraic set defined by the ideal I into the Y-subspace is defined by the ideal
The lexicographical ordering such that is an elimination ordering for every partition Thus a Gröbner basis for this ordering carries much more information than usually necessary. This may explain why Gröbner bases for the lexicographical ordering are usually the most difficult to compute.
Intersecting ideals
If I and J are two ideals generated respectively by {f1, ..., fm} and {g1, ..., gk}, then a single Gröbner basis computation produces a Gröbner basis of their intersection I ∩ J. For this, one introduces a new indeterminate t, and one uses an elimination ordering such that the first block contains only t and the other block contains all the other variables (this means that a monomial containing t is greater than every monomial that do not contain t). With this monomial ordering, a Gröbner basis of I ∩ J consists in the polynomials that do not contain t, in the Gröbner basis of the ideal
In other words, I ∩ J is obtained by eliminating t in K. This may be proven by remarking that the ideal K consists in the polynomials such that and . Such a polynomial is independent of t if and only a=b, which means that
Implicitization of a rational curve
A rational curve is an algebraic curve that has a parametric equation of the form
where and are univariate polynomials for 1 ≤ i ≤ n. One may (and will) suppose that and are coprime (they have no non-constant common factors).
Implicitization consists in computing the implicit equations of such a curve. In case of n = 2, that is for plane curves, this may be computed with the resultant. The implicit equation is the following resultant:
Elimination with Gröbner bases allow to implicitize for any value of n, simply by eliminating t in the ideal If n = 2, the result is the same as with the resultant, if the map is injective for almost every t. In the other case, the resultant is a power of the result of the elimination.
Saturation
When modeling a problem by polynomial equations, it is highly frequent that some quantities are supposed to be non-zero, because, if they are zero, the problem becomes very different. For example, when dealing with triangles, many properties become false if the triangle is degenerated, that is if the length of one side is equal to the sum of the lengths of the other sides. In such situations, there is no hope of deducing relevant information from the polynomial system if the degenerate solutions are not dropped out. More precisely, the system of equations defines an algebraic set which may have several irreducible components, and one has to remove the components on which the degeneracy conditions are everywhere zero.
This is done by saturating the equations by the degeneracy conditions, which may be done by using the elimination property of Gröbner bases.
Definition of the saturation
The localization of a ring consists in adjoining to it the formal inverses of some elements. This section concerns only the case of a single element, or equivalently a finite number of elements (adjoining the inverses of several elements is equivalent to adjoin the inverse of their product). The localization of a ring R by an element f is the ring where t is a new indeterminate representing the inverse of f. The localization of an ideal I of R is the ideal of When R is a polynomial ring, computing in is not efficient, because of the need to manage the denominators. Therefore, the operation of localization is usually replaced by the operation of saturation.
The saturation with respect to f of an ideal I in R is the inverse image of under the canonical map from R to It is the ideal consisting in all elements of R whose products by some power of f belongs to I.
If J is the ideal generated by I and 1-ft in R[t], then It follows that, if R is a polynomial ring, a Gröbner basis computation eliminating t allows to compute a Gröbner basis of the saturation of an ideal by a polynomial.
The important property of the saturation, which ensures that it removes from the algebraic set defined by the ideal I the irreducible components on which the polynomial f is zero, is the following: The primary decomposition of consists in the components of the primary decomposition of I that do not contain any power of f.
Computation of the saturation
A Gröbner basis of the saturation by f of a polynomial ideal generated by a finite set of polynomials F, may be obtained by eliminating t in that is by keeping the polynomials independent of t in the Gröbner basis of for an elimination ordering eliminating t.
Instead of using F, one may also start from a Gröbner basis of F. Which method is most efficient depends on the problem. However, if the saturation does not remove any component, that is if the ideal is equal to its saturated ideal, computing first the Gröbner basis of F is usually faster. On the other hand, if the saturation removes some components, the direct computation may be dramatically faster.
If one wants to saturate with respect to several polynomials or with respect to a single polynomial which is a product there are three ways to proceed which give the same result but may have very different computation times (it depends on the problem which is the most efficient).
- Saturating by in a single Gröbner basis computation.
- Saturating by then saturating the result by and so on.
- Adding to F or to its Gröbner basis the polynomials and eliminating the in a single Gröbner basis computation.
Effective Nullstellensatz
Hilbert's Nullstellensatz has two versions. The first one asserts that a set of polynomials has an empty set of common zeros in an algebraic closure of the field of the coefficients if and only if 1 belongs to the generated ideal. This is easily tested with a Gröbner basis computation, because 1 belongs to an ideal if and only if 1 belongs to the Gröbner basis of the ideal, for any monomial ordering.
The second version asserts that the set of common zeros (in an algebraic closure of the field of the coefficients) of an ideal is contained in the hypersurface of the zeros of a polynomial f, if and only if a power of f belongs to the ideal. This may be tested by a saturating the ideal by f; in fact, a power of f belongs to the ideal if and only if the saturation by f provides a Gröbner basis containing 1.
Implicitization in higher dimension
By definition, an affine rational variety of dimension k may be described by parametric equations of the form
where are n+1 polynomials in the k variables (parameters of the parameterization) Thus the parameters and the coordinates of the points of the variety are zeros of the ideal
One could guess that it suffices to eliminate the parameters to obtain the implicit equations of the variety, as it has been done in the case of curves. Unfortunately this is not always the case. If the have a common zero (sometimes called base point), every irreducible component of the non-empty algebraic set defined by the is an irreducible component of the algebraic set defined by I. It follows that, in this case, the direct elimination of the provides an empty set of polynomials.
Therefore, if k>1, two Gröbner basis computations are needed to implicitize:
- Saturate by to get a Gröbner basis
- Eliminate the from to get a Gröbner basis of the ideal (of the implicit equations) of the variety.
Implementaciones
- CoCoA free computer algebra system for computing Gröbner bases.
- GAP free computer algebra system that can perform Gröbner bases calculations.
- FGb, Faugère's own implementation of his F4 algorithm, available as a Maple library.[5] To the date, as of 2014, it is, with Magma, the fastest implementation for rational coefficients and coefficients in a finite field of prime order.
- Macaulay 2 free software for doing polynomial computations, particularly Gröbner bases calculations.
- Magma has a very fast implementation of the Faugère's F4 algorithm.[6]
- Maple has implementations of the Buchberger and Faugère F4 algorithms, as well as Gröbner trace.
- Mathematica includes an implementation of the Buchberger algorithm, with performance-improving techniques such as the Gröbner walk, Gröbner trace, and an improvement for toric bases.
- SINGULAR free software for computing commutative and noncommutative Gröbner bases.
- SageMath provides a unified interface to several computer algebra systems (including SINGULAR and Macaulay), and includes a few Gröbner basis algorithms of its own.
- SymPy Python computer algebra system uses Gröbner bases to solve polynomial systems.
Áreas de aplicación
Error-Correcting Codes
Gröbner basis has been applied in the theory of error-correcting codes for algebraic decoding. By using Gröbner basis computation on various forms of error-correcting equations, decoding methods were developed for correcting errors of cyclic codes,[7] affine variety codes,[8] algebraic-geometric codes and even general linear block codes.[9] Applying Gröbner basis in algebraic decoding is still a research area of channel coding theory.
Ver también
- Buchberger's algorithm
- Faugère's F4 and F5 algorithms
- Graver basis
- Janet basis
- Regular chains, an alternative way to represent algebraic sets
Referencias
- ^ Lazard, Daniel (1983). "Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations". Computer Algebra. Lecture Notes in Computer Science. 162. pp. 146–156. doi:10.1007/3-540-12868-9_99. ISBN 978-3-540-12868-7.
- ^ Renschuch, Bodo; Roloff, Hartmut; Rasputin, Georgij G.; Abramson, Michael (June 2003). "Contributions to constructive polynomial ideal theory XXIII: forgotten works of Leningrad mathematician N. M. Gjunter on polynomial ideal theory" (PDF). SIGSAM Bull. 37 (2): 35–48. doi:10.1145/944567.944569. S2CID 1819694.
- ^ Gerdt, Vladimir P.; Blinkov, Yuri A. (1998). "Involutive Bases of Polynomial Ideals". Mathematics and Computers in Simulation. 45 (5–6): 519–541. arXiv:math/9912027. doi:10.1016/S0378-4754(97)00127-4. S2CID 10243294.
- ^ Cox, David A.; Little, John; O'Shea, Donal (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer. ISBN 0-387-94680-2.
- ^ FGb home page
- ^ Steel, Allan. "Gröbner Basis Timings Page".
- ^ Chen, X.; Reed, I.S.; Helleseth, T.; Truong, T.K. (1994). "Use of Gröbner bases to decode binary cyclic codes up to the true minimum distance". IEEE Transactions on Information Theory. 40 (5): 1654–61. doi:10.1109/18.333885.
- ^ Fitzgerald, J.; Lax, R.F. (1998). "Decoding affine variety codes using Gröbner bases". Designs, Codes and Cryptography. 13 (2): 147–158. doi:10.1023/A:1008274212057. S2CID 2515114.
- ^ Bulygin, S.; Pellikaan, R. (2009). "Decoding linear error-correcting codes up to half the minimum distance with Gröbner bases". Gröbner Bases, Coding, and Cryptography. Springer. pp. 361–5. ISBN 978-3-540-93805-7.
Otras lecturas
- Adams, William W.; Loustaunau, Philippe (1994). An Introduction to Gröbner Bases. Graduate Studies in Mathematics. 3. American Mathematical Society. ISBN 0-8218-3804-0.
- Li, Huishi (2011). Gröbner Bases in Ring Theory. World Scientific. ISBN 978-981-4365-13-0.
- Becker, Thomas; Weispfenning, Volker (1998). Gröbner Bases. Graduate Texts in Mathematics. 141. Springer. ISBN 0-387-97971-9.
- Buchberger, Bruno (1965). An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal (PDF) (PhD). University of Innsbruck.— (2006). Translated by Abramson, M. "Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal". Journal of Symbolic Computation. 41 (3–4): 471–511. doi:10.1016/j.jsc.2005.09.007. [This is Buchberger's thesis inventing Gröbner bases.]
- Buchberger, Bruno (1970). "An Algorithmic Criterion for the Solvability of a System of Algebraic Equations" (PDF). Aequationes Mathematicae. 4: 374–383. doi:10.1007/BF01844169. S2CID 189834323. (This is the journal publication of Buchberger's thesis.) Burchberger, B.; Winkler, F., eds. (26 February 1998). "An Algorithmic Criterion for the Solvability of a System of Algebraic Equations". Gröbner Bases and Applications. London Mathematical Society Lecture Note Series. 251. Cambridge University Press. pp. 535–545. ISBN 978-0-521-63298-0.
- Buchberger, Bruno; Kauers, Manuel (2010). "Gröbner Bases". Scholarpedia. 5 (10): 7763. doi:10.4249/scholarpedia.7763.
- Fröberg, Ralf (1997). An Introduction to Gröbner Bases. Wiley. ISBN 0-471-97442-0.
- Sturmfels, Bernd (November 2005). "What is ... a Gröbner Basis?" (PDF). Notices of the American Mathematical Society. 52 (10): 1199–1200, a brief introductionCS1 maint: postscript (link)
- Shirshov, Anatoliĭ I. (1999). "Certain algorithmic problems for Lie algebras" (PDF). ACM SIGSAM Bulletin. 33 (2): 3–6. doi:10.1145/334714.334715. S2CID 37070503. (translated from Sibirsk. Mat. Zh. Siberian Mathematics Journal 3 (1962), 292–296).
- Aschenbrenner, Matthias; Hillar, Christopher (2007). "Finite generation of symmetric ideals". Transactions of the American Mathematical Society. 359 (11): 5171–92. doi:10.1090/S0002-9947-07-04116-5. S2CID 5656701. (on infinite dimensional Gröbner bases for polynomial rings in infinitely many indeterminates).
enlaces externos
- Faugère's own implementation of his F4 algorithm
- "Gröbner basis", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- Buchberger, B. (2003). "Gröbner Bases: A Short Introduction for Systems Theorists" (PDF). In Moreno-Diaz, R.; Buchberger, B.; Freire, J. (eds.). Computer Aided Systems Theory — EUROCAST 2001: A Selection of Papers from the 8th International Workshop on Computer Aided Systems Theory. Springer. pp. 1–19. ISBN 978-3-540-45654-4.
- Buchberger, B.; Zapletal, A. "Gröbner Bases Bibliography".
- Comparative Timings Page for Gröbner Bases Software
- Prof. Bruno Buchberger Bruno Buchberger
- Weisstein, Eric W. "Gröbner Basis". MathWorld.
- Gröbner basis introduction on Scholarpedia