MathGroup Archive 2011

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

Search the Archive

Re: numeric Groebner bases et al [Was Re: Numerical accuracy/precision - this is a bug or a feature?]

  • To: mathgroup at smc.vnet.net
  • Subject: [mg120360] Re: numeric Groebner bases et al [Was Re: Numerical accuracy/precision - this is a bug or a feature?]
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Wed, 20 Jul 2011 06:31:30 -0400 (EDT)

On 07/19/2011 05:54 AM, Richard Fateman wrote:
> [...]
> I gather from previous correspondence (DanL), that what significance
> arithmetic is used for is a decision point as to whether some value is
> or is not possibly zero.
> The value is presumably the result of evaluating a (multivariate)
> polynomial whose coefficients are exact rationals [or maybe not] at a
> point where the coefficients are known as intervals [or maybe exact].
> Perhaps DanL can advise on this characterization.

It's not that, but simple coefficient arithmetic e.g. in running 
Buchberger's algorithm or one of the more recent alternatives. One has 
to know when some linear combination of coefficients cancels.


> [...]
> I don't think there is a need to produce an independent implementation
> of anything; the same abstract structure of algorithms should hold.

It does, in running Buchberger's algorithm. Not sure if that was 
specifically what you had in mind here but it seems relevant to mention.


> The idea that one must come up with a different proof (that is, by not
> emulating the other proof) is irrelevant,

Slightly tangential: Kondratyev et al proposed a variant to Groebner 
bases, which uses a variant of Buchberger's algorithm. In his thesis, 
Kondratyev did require a "different" set of proofs to show termination 
and correctness. Related to the usual proofs, but by no means identical 
and not exactly what i would view as emulation.


> but as it happens, the
> algorithm for evaluating a polynomial with guaranteed error does NOT
> emulate significance arithmetic by carrying along extra baggage at each
> operation. Crudely speaking, it evaluates the polynomial in
> floating-point, and then it evaluates the polynomial with the signs of
> all the coefficients changed to +.
>
> see slide 21 in
> http://www-pequan.lip6.fr/~graillat/papers/slides_MIMS.pdf
> which is something I just found with Google.
>
> RJF

Certainly there are various methods of gauging precision loss in numeric 
evaluation of polynomials, and some may be better than blind 
significance arithmetic. The slides look like something I should check 
more closely.


Daniel Lichtblau
Wolfram Research




  • Prev by Date: Re: Transforming an expression to publication form
  • Next by Date: Re: MultinormalDistribution Question
  • Previous by thread: Re: numeric Groebner bases et al [Was Re: Numerical accuracy/precision - this is a bug or a feature?]
  • Next by thread: Replace, test question