[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
>
>
>
Prev by Date:
**Question about adding events to ndsolve**
Next by Date:
**Re: Solve never calls Equal?**
Previous by thread:
**Re: numeric Groebner bases et al [Was Re: Numerical accuracy/precision - this is a bug or a feature?]**
Next by thread:
**Re: numeric Groebner bases et al [Was Re: Numerical accuracy/precision - this is a bug or a feature?]**
| |