From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.symbolic
Subject: Re: Polynomial equations
Date: 7 Feb 1996 20:07:48 GMT

In article <1996Feb6.165731.12556@ixwin.ihep.su>,
 <nikitin_i@m10.ihep.su> wrote:
>1. Sometimes the number of generators in Groebner basis becomes greater than
>the number of initial ideal generators. For example, in Mathematica
>GroebnerBasis[{x^3-y,x^2+y},{x,y}]  is  {y + y^2, y + x*y, x^2 + y}.
>How can this happen?

Well, why not? A Groebner basis is a basis for an ideal in the usual sense,
but it is specifically enlarged so that a sort of division algorithm may
be used to determine (for example) membership in this ideal. Roughly speaking,
one enlarges the basis to include one polynomial of every minimal multidegree.
I'm not sure quite how bad it can get but I know from experience that
the list of generators can grow quite a bit; if someone told me an
n-generator ideal can produce a 2^n-element Groebner basis, I would not
be surprised. It's also true (unlike your example) that the degrees of
the generators can increase. I have seen results along the following lines:
an ideal with generators of degree at most  n  can yield a Groebner basis
with generators of degree roughly  n^2.

Groebner bases are "nice" in the sense that once you have them, other
computations are easy; they are not nice in the sense that they are 
particularly easy to read nor to compute from a set of generators.

>2. I need your advice in one special problem. I should solve a system
>of 6 quadratic equations: P1(x1,..x6)=H1, ... P6(x1,..x6)=H6,
>where P* are homogenous 2nd degree polynomials of variables.
>Their coefficients are rational numbers, but the r.h.s. H* are symbolic
>parameters. The system is somewhat special (the number of monomials
>in each equation is much less than 6(6+1)/2=27), but there is no any
>evident structure like diagonality. I wish to reduce it into Groebner's
>form: P'1(x1)=0, P'2(x1,x2)=0, ... P'6(x1,..x6)=0,
>and then solve it numerically step by step. However, on our VAX the procedures
>GroebnerBasis[] and Solve[] cannot find solutions (during 2 days).
>Is there some way to speed up this calculations? Or may be other methods
>would be more appropriate?

Yes, this is common. I have had some better luck using  Macaulay, a computer
program specifically written around Groebner bases for work in commutative
algebra and algebraic geometry. Last I checked it was available by ftp
from  Harvard (try zariski.harvard.edu). It assumes you are working mod  p
but you can choose a large  p  and probably will get the same result as
one would obtain in characteristic zero. Perhaps the designers of Mathematica
had too many goals in mind to allow for efficiency in all (or any?)

Since your goal is a numerical solution anyway, it seems reasonable to
try something like (multivariable) Newton's method on the original
system. It would help, I suppose, if you knew from theoretical considerations
how many solutions to expect, and roughly where the solutions lay.
This would avoid the problems with Groebner bases altogether.

dave