On Apr 29, 2010, at 8:30 AM, rjf wrote:
Again, I see no definition of what you mean by accuracy in the result of polynomial multiplication. If you look at the actual algebraic formula for any given coefficient in the result, you see it is the sum of products of coefficients from the inputs, and the possibility of cancellation depends on the magnitude and sign of those terms, and the order and arrangement of the operations. You can rearrange them various ways, but if I want to play some kind of adversary game with you, and you tell me how you are going to compute it, then I believe I can come up with coefficients that will give you answers for particular coefficients that are quite bad.
This is a good question. The easiest position to take is that of MPFR-- considering the inputs as exact rationals, how far off is the output (say, coefficient by coefficient) from the actual result. One could also use other measures, such as an L^2 norm over some compact region (like [-1,1]). What may make sense for many applications is some kind of a "slopped absolute" precision, as has been discussed with p-adic polynomials. These would have good behavior on |x| < a or |x| > a depending on the slope.
It all really depends on your application, and currently we don't define, let alone make guarantees, on the precision of the result (and nor does Maxima as far as I understand). We do, however, try to avoid algorithms that are known to be numerically unstable.
As far as specifics as to which work on asymptotic complexity is irrelevant, I think that as a first cut you should assume that ALL the published theoretical work is irrelevant to practice. , There are particular authors whose work combines poor exposition, elaborate and unnecessary notation, complicated proposals, non-implementation, and unfounded claims. Note that these defects do not make a theoretical paper unpublishable, or even "wrong". After all, for some n>N the claim may be true, just that N represents a problem size that requires all the electrons in the universe to represent explicitly.
Fortunately for us, many asymptotically fast algorithms do have cutoffs well within the size ranges we regularly encounter, and low enough that it makes a significant difference in the runtime.
- Robert -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
