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>
- GroebnerBasis (was Re: Documentation)