GroebnerBasis and Polynomial Routines

*To*: mathgroup at smc.vnet.net*Subject*: [mg46230] GroebnerBasis and Polynomial Routines*From*: "David Park" <djmp at earthlink.net>*Date*: Thu, 12 Feb 2004 07:15:55 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

In the response to my recent question about algebraic manipulation with Mathematica (and thanks to everyone for the replies) I had a private response from Andrzej Kozlowski that I thought was very informative on the usefulness of GroebnerBasis. He gave me permission to pass it along to MathGroup. ____________________________________________________________________________ David, "Groebner basis" or rather the Buchsberger algorithm is perhaps the most useful algorithm in all of computer algebra. What it does is let you perform division of polynomials in more than one variable in a canonical way. In the case of polynomials in one variable this is essentially obvious; every body learns it (or used to) in school. But if you try to think how to do it for polynomials in, say, two variables you will notice that it is not at all obvious, in fact there is no natural or canonical way to do this. However, you can do it if you choose a way of ordering monomials in a sensible way. Each choice of such an ordering lets you do more than just divide polynomials: what you can do is replace a system of polynomial equations by another system which has the same solutions but is "triangular", meaning that each equation in turn involves fewer variables than the previous one. This is exactly what a Groebner basis together with polynomial division with respect to it (PolynomialReduce) does for you. In practice you no not really need to know much about Groebner basis as such since many Mathematica functions us it automatically. However, it is useful to know about how different monomial orderings affect the outcome: they can make a huge difference to performance. This aspect is controlled by the option MonomialOrder that you can find in many algebraic functions that use Groebner basis. (Some, like Solve do not have this option because they use a special setting called EliminationOrder). Of course knowing more about Groebner basis gives you more flexibility in deciding how it is used. The easiest introduction to all these techniques is: D. Cox, J. Little, and D. O'Shea (1992). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Computer Algebra. Undergraduate Texts in Mathematics. Springer-Verlag. With best regards Andrzej