MathGroup Archive 2005

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

Search the Archive

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


  • Prev by Date: Re: Problem with multiple function calling from a novice...
  • Next by Date: Re:Re: Set of strings reducing problem
  • Previous by thread: GroebnerBasis (was Re: Documentation)
  • Next by thread: Re: GroebnerBasis (was Re: Documentation)