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