Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.soft-sys.math.mathematica > #3801

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

Show all headers | View raw

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
>
>
>

Back to comp.soft-sys.math.mathematica | Previous | Next | Find similar | Unroll thread

Thread

Re: numeric Groebner bases et al [Was Re: Numerical accuracy/precision - this is a bug or a feature?] Richard Fateman <fateman@cs.berkeley.edu> - 2011-07-19 10:57 +0000

csiph-web