Re: GroebnerBasis (was Re: Documentation)

*To*: mathgroup at smc.vnet.net*Subject*: [mg58604] Re: [mg58577] GroebnerBasis (was Re: Documentation)*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Sat, 9 Jul 2005 04:08:04 -0400 (EDT)*References*: <200506240649.CAA29400@smc.vnet.net> <d9islb$co6$1@smc.vnet.net> <200507080446.AAA18309@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Stefan Karlsson wrote: > Daniel Lichtblau wrote: > > [...] > I have notized that in Mathematica 3.0 and Mathematica 5.0, > GroebnerBasis sometimes gives different results. Where 3.0, when > eliminating, gives a polynomial with very large coefficients, 5.0 > gives the empty set, although that's incorrect, probably due to > numerical cancellation, quite unexpectedly. > As an example, in Mathematica 5.0 > GroebnerBasis[{x - y, x - 1.01 y}, {y},{x}] > gives {1. y} while > GroebnerBasis[{x - y, x - 1.001 y}, {y},{x}] > gives {}. > The correct Groebner Basis, after elimination of x is of course {y}. > Likewise > GroebnerBasis[{x - y, x - 1.01 y}, {x, y}] > gives the correct {1. y, x} while > GroebnerBasis[{x - y, x - 1.01 y}, {x, y}] > gives the incorrect {x - 1.001 y} Interesting... > Though, if you add CoefficientDomain->Rationals, things works out quite > a bit better. (Default seems to be CoefficientDomain->InexactNumbers). > Thanks to this thread for that! Strictly speaking the default is Automatic, and in presence of approximate numbers that behaves as InexactNumbers. > Should really cancellation errors occur at this level of accurancy? Probably not. I'm changing a couple of values to better handle that. But I should mention that Groebner bases and machine arithmetic do not get along well, and, in my opinion, perhaps never will, at least not when the latter uses any variant of the Buchberger algorithm. To get better results you might work with bignums in significance arithmetic. The reason this si vastly preferable is that one need not impose artificial constants for "guessing" when something should be regarded as zero. Instead the arithmetic model will tell you when you are really in a neighborhood containing zero vs. having values that might (or might not) be deemed "small"; this is usually problem specific. Even with low precision bignums we get a reasonable result for the example below. In[5]:= GroebnerBasis[{x - y, x - N[1001/1000,8]*y}, {x,y}] Out[5]= {1.0000 y, x} > I agree with Andrzej that the different CoefficientDomains should be > more documented, and so the risk of inaccuracy in the default setting. > > Stefan Karlsson > Skövde University, Sweden I think the more important thing to document is that machine arithmetic does not cooperate well with Groebner bases, at least as currently implemented in Mathematica. Daniel Lichtblau Wolfram Research

**References**:**GroebnerBasis (was Re: Documentation)***From:*Stefan Karlsson <steka68@telia.com>