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

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: [mg120322] Re: numeric Groebner bases et al [Was Re: Numerical accuracy/precision - this is a bug or a feature?]
• From: Richard Fateman <fateman at cs.berkeley.edu>
• Date: Tue, 19 Jul 2011 06:54:49 -0400 (EDT)

On 7/18/2011 3:13 AM, Andrzej Kozlowski wrote:

> Clearly one can emulate "significance tracking" in fixed precision
> arithmetic and thus implement Daniel's version of Groebner basis in, for
> example, Maple. It will almost certainly require clumsier and longer
> code.

By analogy, clearly one can emulate 'driving a bus' in a Boeing 747.
Indeed, all the driving around on the airport tarmac before/after the 
airborne part of the flight is very much like being driven around in a bus.

If all you need is a bus, using a 747 is inefficient.

The answer to the question: is there a really independent way of
> achieving the same final effect? is not known to me and I certainly did
> not imply that it was. And I think Richard should have known "what I
> mean" perfectly well, but it was not a convenient thing to know for him
> a that moment.

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.

If this is correct, then the single non-trivial algorithm that is needed 
is "polynomial evaluation".  We know that Mathematica doesn't do a great 
job on computing  x=2*x-x accurately. We also know how to evaluate a 
univariate polynomial at an interval point. I think it can be extended 
to multivariate, though perhaps in several ways.

I don't think there is a need to produce an independent implementation 
of anything; the same abstract structure of algorithms should hold.
The idea that one must come up with a different proof (that is, by not 
emulating the other proof) is irrelevant, 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


>
> Andrzej Kozlowski
>
>
>