Talk:Gröbner basis

Untitled

If I'm not mistaken, this algorithm generalizes not only Euclid's algorithm but also Gaussian elimination and the simplex algorithm. I don't know enough about it to incorporate those topics into the article. Can someone do that? 128.101.13.104 02:15, 6 Nov 2003 (UTC)

I think you're mistaken about the simplex algorithm. I'm pretty sure that it is wasteful to do Gauss-Jordan elimination this way. In fact it seems to be like doing numerous eliminations in parallel.

Charles Matthews 09:26, 6 Nov 2003 (UTC)

I think the rewrite of the article has made it less accessible. For example, trying to give an exact characterisation of a GB in the opening sentence means that the technical density is immediately at a maximum.

Charles Matthews 11:13, 9 Jun 2004 (UTC)

About polynomial systems

The text implies that a polynomial system with finitely many solutions can be "solved" using the Gröbner basis. But if the system has zero solutions, then this technique won't always demonstrate that fact, right? Perhaps the article should say "If the system has a finite nonzero number of solutions..." or some such. I'd change it myself, but I'm a bit new to Gröbner bases, and would like some assurance that I'm right. Staecker 17:46, 25 Jun 2005 (UTC)

In fact, if there is no solution, then by the Nullstellensatz the polynomial 1 belongs to the ideal, and since its leading monomial is 1 and is the smallest element in every term order, the reduced minimal GB will be exactly {1}, so You would know. For the other thing, look up lexikographic order, FGLM (Jean C. Faugere is the F), RUR by Fabrice Rouillier, also called "geometric solution" in other contexts. A first result on finite numbers of solutions is that for each variable there has to be a polynomial in the GB with a pure power of said variable as leading monomial.--LutzL 14:28, 29 August 2005 (UTC)

Gröbner basis and Hironaka

Copied from User talk:LutzL for possible use by others. --Lambiam^Talk 14:49, 5 May 2006 (UTC)
(Lambiam adressing LutzL:) Hi. Concerning your recent edit of Gröbner basis, I am not sure that Hironaka's theory of "standard bases" is exactly the same. See for example Joachim Apel, Division of entire functions by polynomial ideals, in Proc. AAECC 11, LNCS 948 (1995), pp. 82-95. So if you agree but think the addition is nevertheless important, I propose that you change the text into something like: "In 1964, at almost the same time and independently, Heisuke Hironaka had developed a closely related theory, which he called standard bases." I'm not sure how close this is to your areas of expertise, but I you have interest, time and patience, perhaps you could also add some of this to the Hironaka article, putting it in context, and if possible cite the references as provided by Apel's paper. Cheerio. Lambiam^Talk 13:46, 3 May 2006 (UTC)

As I understand it now, the standard bases are defined for ideals in the ring of Puisseux series. Thus they contain Gröbner bases as a special case. The real contribution of Buchberger to the fundamentals is the proof that his algorithm stops in finite time. Perhaps it should be mentioned somewhere that the idea comes from the non-constructive proof by Hilbert of the Basissatz (Kronecker had a constructive proof, but only formulated for bivariate polynomials) -- No, I'm not an expert in the whole of the topic of Gröbner bases. They are interesting to me in the aspect of their inefficiency. I got most of my knowledge from Gethgen/vonzur Gathen: Modern Algebra, where they mention H. Hironaka in the second sentence of the introduction. And from M. Guisty: Bases standard, élimination et complexité, notes of a lecture given at X, where some propositions are attributed to Hironaka.--LutzL 07:29, 5 May 2006 (UTC)

I'm not an expert either and I don't have access to a library, so I wouldn't be comfortable making any changes of substance. I'll copy this exchange to the talk page of the article in the hope that a next reader can do something with it. --Lambiam^Talk 14:43, 5 May 2006 (UTC)

Definition of Reduced Gröbner Bases

The definition of reduced bases didn't make sense. As it was written, it referred to the "ideal generated by the leading coefficient", which is always all of R. Therefore, the condition for a reduced basis could never be satisfied.

I changed "coefficient" to "term". Now at least it at least makes sense, although I don't have a reference to be sure whether it is correct. If anyone would care to look it up and check it that would be good. When I find a reference I will do so. Heatkernel 10:58, 8 May 2006 (UTC)

Example of Groebner basis

Hello. I am aware that a Groebner basis, in general, may be tremendously verbose. Even so I wonder if we can give some kind of example. A set of examples which shows the increasingly verbose Groebner bases for a progression of simple problems would be terrific. 207.174.201.18 21:15, 23 June 2006 (UTC)

I have just produced what I think is a relatively simple example and counterexample for the Dutch Wikipedia. Feel free to verify and copy that.--Lieven Smits (talk) 09:21, 9 April 2014 (UTC)

Update: I have tried a quick translation of my own Dutch text but I would appreciate it if someone could check its content and style.--Lieven Smits (talk) 21:08, 9 April 2014 (UTC)

Thanks for adding this example. Its formatting deserves some improvement; I'll do this later, if it will not be done before by another editor (just now I have not too much time for WP). Some hints for further improvements:

• It could be useful to show the difference if lexicographical ordering is replaced by a degree ordering.
• Gaussian elimination and Euclid's algorithm for polynomials are special instances of Gröbner basis computation, which deserve to appear in the example section.

D.Lazard (talk) 09:00, 10 April 2014 (UTC)

Solving equations

Solving equations is the elementary application which, from my point of view, motivates the theory. The formulas, { f₁[x₁, ..., x_n] = a₁, ..., f_m[x₁, ..., x_n] = a_m} and g(x_n) = b, can be simplified into {f₁[x₁, ..., x_n] = 0, ..., f_m[x₁, ..., x_n] = 0} and g(x_n) = 0 . For example a circle cutting a straight line: x²+y²−4 = y−1 = 0. You do not need to understand ideals in order to understand the problem of solving systems of equations with several unknowns. Bo Jacoby 08:17, 8 August 2007 (UTC).

Hi Bo, nice to see You again. And now, what was the point? The main application of GB, as it is my experience, is to prove structural theorems in algebraic geometry. Such as estimates on the Hilbert polynomial, number of rational points etc. Your point is valid, but the number of solvable systems is rather small.--LutzL 06:45, 9 August 2007 (UTC)

Thanks LutzL! Regarding Gröbner bases I am a pupil and not a teacher. I may have got it wrong. I was looking for methods for solving algebraic equations in several unknowns. It is a practical and elementary problem. If the system of equations is f_m[x_n] = 0, where each f_m is a polynomial in the variables x_n, then any polynomial, p, in the ideal spanned by the f_m makes an equation p[x_n] = 0. Elimination of variables is construction of a system of algebraic equations, p_n[x_n] = 0, each in one unknown. Algebraic equations in one unknown can be solved numerically by the Durand-Kerner method, and so we are done. Am I on the track? Bo Jacoby 14:51, 9 August 2007 (UTC).

Earliest examples

An IP hinted at a paper "Les Invariants des formes binaires" in Jour. Des Mathematiques Pure and Applique'es, (1900), se'rie 5/ T 6, pp 141-156.", which is available from a digitisation project site (PDF). There exists an english translation at a Gröbner bibliography project (PDF) which claims it as an early example of a computed Gröbner basis. Perhaps someone might include in in the article.--LutzL (talk) 09:37, 6 December 2007 (UTC)

Examples please

I wish this article had some examples. I was not able to get a clue about what was going on even though I know what a polynomial ring is and I know what an ideal is. —Mark Dominus (talk) 14:58, 12 October 2011 (UTC)

Rather than add an example, I added an intuitive description. If you still think that is insufficient, please say so. Simplex (talk) 15:02, 21 March 2013 (UTC)

See above under "Example of Groebner basis"--Lieven Smits (talk) 21:09, 9 April 2014 (UTC)

Info from the Russian Wikipedia

Their article differs substantially from ours. We could improve ours by using information from theirs. Here is the Google Translation of http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%B8%D0%B5:

röbner basis of some ideal I of the algebra of polynomials K [x_1, \ ldots, x_n] concerning the order of " \ Prec "On monomials - is a finite set of polynomials G K [x_1, \ ldots, x_n] such that the highest (relative \ Prec ) Member of each polynomial of I divided by a senior member of at least one polynomial of G. The order \ Prec must be complete and in addition to the following two conditions:

   Multiplicativity: x ^ a \ prec x ^ b entails x ^ {a + c} \ prec x ^ {b + c} .
   Minimum unit: 1 \ prec x ^ a For a> 0 . 

Content

   1 Types of Gröbner
       1.1 Minimum Gröbner
       1.2 The reduced Gröbner 
   2 Algorithms for constructing
   3 Applications
   4 History
   5 Notes
   6 Links 

Types of Gröbner Minimum Gröbner

Minimal Gröbner basis of a polynomial ideal I is called its Gröbner G, such that:

   Coefficient of the leading monomial of each p \ in G equal to one.
   Each leading monomial p \ in G is the leading monomial of any other q \ in \ {G \ setminus {p} \}

The reduced Gröbner

Reduced Gröbner basis of a polynomial ideal I is called its Gröbner G, such that:

   Coefficient of the leading monomial of each p \ in G equal to one.
   Each leading monomial p \ in G not divisible by the leading monomial one other elements of the basis. 

For the reduced Gröbner basis of the ideal we have the following statement:

Let I - polynomial ideal, and given a monomial ordering. Then there is a unique reduced Gröbner basis of the ideal I. Algorithms for constructing

The earliest construction algorithm reduced Gröbner basis of the ideal is Buchberger algorithm . Interestingly, the well-known Gaussian elimination for solving systems of linear equations is a special case of the Buchberger algorithm.

In addition, the French mathematician Jean-Charles Fougeres proposed algorithms F4 and F5 finding Gröbner basis. Applications

Gröbner basis is the most important concept of computer algebra , algebraic geometry and computational commutative algebra . History

Austrian mathematician Wolfgang Graebner developed the theory of standard bases for the free commutative case in the early 30's, and published it in 1950 , [1] where he wrote: '

I started using this method 17 years ago for a variety of examples, including the very complex. The original text (in German) [показать] '

In 1964 a similar concept for the local rings was developed Heysuki Hironaka, received Fildovskuyu Prize in 1970 . He introduced a system of polynomials called the standard basis.

The concept of Gröbner basis was introduced in 1965 an Austrian mathematician Bruno Buchberger , a former student of Graebner. Buchberger proposed a constructive procedure for constructing Gröbner basis in the form of efficient computer algorithm, which was later called Buchberger algorithm .

The existence of a standard basis of the ideal is based on the "lemma of composition", which was first proved for the most complex of the known cases (free Lie ) A. Shirshov . [2] The correct similar result for the free associative and commutative case was considered obvious and did not attract much attention until later works LI bokuto on the theory of attachment in the body of associative rings and rings with specified properties. In 1972 L. I. Bokut published "lemma Shirshov's Song" for the free associative case the notes of a course on associative algebras Novosibirsk University. From this and oral communication, it became known to American algebraist J. Bergman, who published it in 1979 under the name of «Diamond Lemma» (Diamond Lemma), however, strong evidence in missing and was identified only mimic diagram of "fusion" needed to understand the idea of ​​the Shirshov composition. After the publication of Bergman "Diamond Lemma" became popular among algebraists and geometers, it also drew attention to the "Gröbner basis" Buchberger. In the mid 80's the standard basis for superalgebras and color Lie was built Moscow algebraists AA Mikhalev. Notes

   ↑ W. Gröbner (1950). " Über Die Eliminationstheorie ". Monatshefte für Mathematik 54: 71-78.
   ↑ CSF, 1962, Volume 3, № 2, p. 292-296. 

References

   Pankratiev EV Introduction to computer algebra .
   Arzhantsev IV Gröbner bases and algebraic equations . - M.: MCCME , 2003. - 68. - ISBN 5-94057-095-X
   Churkin VA Systems of polynomial equations, ideals and their bases, dividers .
   D. Cox, J. Little, D. O'Shea, Ideals, varieties and algorithms. Introduction to computational aspects of algebraic geometry and commutative algebra.
   Bernd Sturmfels. What is a Gröbner Basis? 

Crasshopper (talk) 16:23, 19 February 2013 (UTC)

Intuitive explanation

I removed the following from the article. I cannot see how it contributes anything of value. --345Kai (talk) 23:37, 18 April 2013 (UTC)

Intuitive notion

The study of ideals is fundamental to commutative algebra and algebraic geometry. Ideals contain infinitely many elements, so, as in linear algebra, it is preferable to obtain a finite generating set with certain desirable qualities.

It is no surprise that not all generating sets possess these qualities; after all, in linear algebra one typically desires a basis of the vector space, which, in addition to generating the space, can contain only elements that are linearly independent. This property allows us to compute easily properties of the space, such as its dimension.

In this vein, a Gröbner basis is a generating set of an ideal, with certain desirable qualities that allow one to answer important questions about the ideal or an object it describes. The similarities do not end there; as noted already, the computation of a Gröbner basis generalizes Gaussian elimination of a system of linear polynomials to non-linear polynomials.

As explained above, I had added it in lieu of an example. I wish you had taken the time to look through the discussion first, but if you find it unhelpful for the task, I shan't bother putting it back. Simplex (talk) 17:56, 18 March 2014 (UTC)

Gjunter's work

Thanks to Spidsen for adding to this article the reference to Gjunters work to this article. Since I have modified Spidsen's edit to follow the guidelines of the Manual of style, this user has introduced several modifications, that I will revert for the following reasons:

• He has changed "doctoral advisor" into "doctoral supervisor", although the correct word is "advisor".
• "was the first to introduce": This is an editorial comment (see WP:PEACOCK), not supported by the source and controversial (Janet and Riquier bases, in differential algebra, have been introduced earlier, and some people consider them as precursors of Gröbner bases)
• "these polynomial ideals, commonly know as Gröbner bases": A Gröbner basis is not an ideal. Thus this sentence is a mathematical nonsense.
• Spidsen asserts implicitly that Gjunter's bases are exactly the same as Gröbner bases. This is not supported by the source. On the contrary, as far I understand, the source asserts that Spidsen considers only homogeneous polynomials, while, at least at the beginning, Buchberger did consider only the non-homogeneous case. This the reason for talking of the similarity than of the identity of the theories.

For these reasons, I will revert all the last Spidsen's edits. D.Lazard (talk) 18:58, 18 August 2014 (UTC)

(1) The mathematical community http://www.ams.org/notices/201103/rtx110300365p.pdf https://cms.math.ca/Community/intl will decide on the fate of this article.

(2) Gjunter was definitely the first who developed the concept of monomial and polynomial ideals, long before Buchberger did. It was only that during the First Word war and the ensuing Russian revolution his publications did not get any attention until the Forties. His publications were rediscovered by some East German mathematicians, who had access to the Leningrad mathematical archives in the late Eighties.

(3) Ph.D. or doctoral ""supervisor"" would be the correct term. I have had one at the University of Glasgow, where I did my research. http://www.timeshighereducation.co.uk/features/10-truths-a-phd-supervisor-will-never-tell-you/2005513.article

— Preceding unsigned comment added by Spidsen (talk • contribs) 10:07, 21 August 2014 (UTC)

Please, sign your post with four tildes (<~~~~). Also, follow the guidelines of WP:TALK for placing and formatting them correctly. Its is boring to do that in your place.

Your point (1): the fate of a Wikipedia article depends only on Wikipedia community. See WP:CONSENSUS for understanding how decisions are taken in case of conflict.

Your point (2): "Gjunter was definitely the first who developed the concept of monomial and polynomial ideals". This is definitely wrong, as David Hilbert and Francis Sowerby Macaulay have developed the theory of polynomial ideals before him. It is true that it seems to be the first to have developed a theory which seems equivalent to that of Gröbner bases. However, the rules of Wikipedia requires that every fact of this kind must be supported by a reliable source (see WP: No original research). In your formulation, "the first" is not supported by any reliable source, and the equivalence between Gröbner bases and Gjunter theory in not clearly supported by Renschuch et al. article, which is the only paper that I know of, which cite Gjunter work. It follows that "the Georgian mathematician N.M. Gjunter introduced in 1913 a notion which is similar to Gröbner bases" is the only one which can be sourced and therefore the only one that is compatible with Wikipedia policies. Moreover, in view of the low impact of Gjunter work there is no reason to emphasize too much on it (see WP:DUE).

Your point (3): The choice of the terms doctoral advisor or doctoral supervisor depends on the countries, and probably, sometimes, of the universities. However, doctoral advisor seems the most widely used. In any case, the Wikipedia article is Doctoral advisor, while Doctoral supervisor is only a redirect to the preceding. It follows that changing "advisor" to "supervisor" must not been done without specific good reasons.

It follows that your last edits break Wikipedia guidelines and policies. I'll revert them. Please, do not insert them unless if some other editors support them in this talk page, for reaching a consensus. D.Lazard (talk) 13:38, 21 August 2014 (UTC)

Performance of Implementations

FGb, Faugère's own implementation of his F4 algorithm, available as a Maple library. 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.

Is this still up to date? The anwsers to this question on Computational Science Stack Exchange and this benchmark seem to suggest that the fastest implmentation is now mgb, the Gröbner basis library shipped with Maple. 212.201.44.244 (talk) 18:36, 24 January 2018 (UTC)

April 2021

I would like to add a detailed explanation of the full reduction of f by a set of polynomials G which is implemented by the Buchberger algorithm used to compute the Groebner basis. I would like to add this right after the paragraph "Given a finite set of polynomials" in the reduction section. This would include at least one long-division example to compute this. Shall I first post this explination here for everyone's review?Youriens (talk) 22:18, 8 April 2021 (UTC)

Be bold and proceed. It is easier to discuss your project if it is in the article. However, if you are reverted, do not take it personally: this could mean that a discussion is needed to reach a consensus, per the process WP:BRD. D.Lazard (talk) 09:16, 9 April 2021 (UTC)

Ok I added a sub-section "Example reductions with Lexicographic ordering" under "Reduction" section however, my long-division is somewhat poorly formatted as I was unable to use the latex \hspace command to align the rows. If the members here approve of this addition, could someone help me better format the long-division rows?Youriens (talk) 19:46, 9 April 2021 (UTC)

For horizontal alignment, the standard way is using `\begin{align}...\end{align} environment (see Help:math). However you have this problem because your use of long division notation. IMO, this is not a good idea, for several reasons: this is a notation that is specific to some countries and may be confusing for readers from other countries; this is a notation that is generally not used by reliable sources on this subject; this suggests wrongly that one must finish the division by a polynomial before starting the division by another polynomial. By the way, your examples are not well chosen, as they do not show two fundamental facts; firstly one may have to divide, say, by $f_{1},$ then by $f_{2},$ and again by $f_{1};$ secondly, the result of the division may depend on order in which the divisors are chosen, and Buchberger's algorithm is specifically designed for making unique the result of the division process.

Instead of long division notation, is is commonly clearer to use a notation similar to that of rewriting theory, such as $f_{1}\;{\overset {-mg}{\longrightarrow }}\;f_{2}$ for expressing the division step consisting to substract $mg$ from $f_{1}.$

There are various other issues in your edit, some are minor, such as the excess of capitalization (see MOS:COMMONNAMECAPS). Some are more fundamental. For example, you give too much details for things that are well described in other articles (such as Monomial ordering), and this hides the main points that must be illustrated, such as the above mentioned ones. D.Lazard (talk) 09:13, 10 April 2021 (UTC)

Thanks for that critique above. I see someone has already improved the section nicely and I am grateful. So as not to change too much, I made only a minor correction describing how f needs to be "continuously" reduced by the elements in G until the remainder is no longer reducible. I personally would like to keep the long-division and I realize I could use \! and \; to manually adjust the indentations so will try to improve the formatting today; however I am only a novice in the matter and wished to add this section because I could not find a clearly-written and complete description elsewhere on the web; however, I realize I'm a novice with the subject so if others more knowledgeable wish to replace them with the suggestion above or something else, I won't add them back. Also, I was not aware Buchberger's algorithm required any specific ordering of the divisors. This is important to me because I was planning to request likewise, adding a full example of computing a reduced basis in the Buchberger's article. I could also come up with an example which includes dividing by $f_{1},f_{2},f_{1}$. — Preceding unsigned comment added by Youriens (talk • contribs) 12:29, 10 April 2021 (UTC)

Please, don't forget to sign your posts in talk pages with four tildes (~~~~)

I have completely rewritten your example for focusing on facts that are fundamental for Gröbner bases, and removing computational details that tend to hide these important properties. For this, I have changed the polynomial f for having an example of two different complete reductions. D.Lazard (talk) 13:22, 11 April 2021 (UTC)

Complexity references

The section title Complexity contains the following sentence:

On the other hand, if all polynomials in the reduced Gröbner basis a homogeneous ideal have a degree of at most D, the Gröbner basis can be computed by linear algebra on the vector space of polynomials of degree less than 2D, which has a dimension $O(D^{n})$.

I'm struggling to find the reference that contains this result. Could someone please cite the correct source. Anon65536 (talk) 16:07, 13 May 2024 (UTC)

The original result is mine, modulo the standard formula for the dimension of the homogeneous polynomials of a given degree. It because of this result and the results in Giusti's paper in the same proceeeings that most texts about the complexity of computation with multivariate polynomials focus on the degrees of involved polynomials rather than on the arithmetic or bit complexity.

References

D.Lazard (talk) 16:51, 13 May 2024 (UTC)

Thank you very much. It’s a nice result. Maybe you should cite it the corresponding paragraph. Anon65536 (talk) 07:17, 14 May 2024 (UTC)

Because of the WP:COI, it is difficult to add it myself. D.Lazard (talk) 08:49, 14 May 2024 (UTC)