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