       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

```

• Prev by Date: Re: Polylogarithm Integration - Bis
• Next by Date: Re: Re: typesetting fractions
• Previous by thread: Re: FindLast NZ in list
• Next by thread: Re: Re: typesetting fractions