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>, 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