When multiplying two univariate polynomials over RR[x], Sage uses the
naive O(n^2) algorithm. The docstring for _mul_ cites numerical
stability as the reason to not use asymptotically faster algorithms:
"Here we use the naive `O(n^2)` algorithm, as asymptotically faster
algorithms such as Karatsuba can have very inaccurate results due to
intermediate rounding errors. "
(this is followed by an example where Karatsuba multiplication is shown
to mess up compared to naive multiplication)
Can we do any better? Does anyone know of any algorithms for
numerically stable fast univariate polynomial multiplication (better
than the naive algorithm)?
Thanks,
Jason
--
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
