[Date Index] [Thread Index] [Author Index]

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