Opened 13 years ago
Closed 12 years ago
#331 closed enhancement (fixed)
compiled implementation of dense univariate polynomial arithmetic
Reported by: | dmharvey | Owned by: | somebody |
---|---|---|---|
Priority: | major | Milestone: | sage-3.1.3 |
Component: | basic arithmetic | Keywords: | |
Cc: | dmharvey@… | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
SAGE needs a compiled, well-optimised implementation of dense univariate polynomial arithmetic over a *generic* commutative base ring.
The current implementation is the python class Polynomial_generic_dense
in sage/rings/polynomial_element.py
.
The new implementation would probably use a python list to store the coefficients (maybe a C array? I'm not sure...), and would have optimised code for at least the following:
- addition, subtraction
- multiplication: classical algorithm, also karatsuba (but this should be optional, since it doesn't work well over certain base rings, especially where numerical stability is an issue)
- division, at least when the base ring is a field (or for monic divisors), using classical, divide-and-conquer, possibly newton's method
- polynomial evaluation
- retrieval of coefficients and conversion to/from python lists
- comparison, hashing
Change History (9)
comment:1 Changed 13 years ago by
comment:2 Changed 13 years ago by
related: #528
comment:3 Changed 13 years ago by
- Milestone changed from sage-2.9.2 to sage-2.9
Can this be closed with the NTL wrapper rewrite? If not what need to be done?
Cheers,
Michael
comment:4 Changed 12 years ago by
What is the status of this?
Cheers,
Michael
comment:5 Changed 12 years ago by
I believe this is implemented in lines 4000+ of http://hg.sagemath.org/sage-main/file/a175cdbeb408/sage/rings/polynomial/polynomial_element.pyx
comment:6 Changed 12 years ago by
Perhaps the title should be changed to "compiled implementation of asymptotically fast dense univariate polynomial arithmetic" :-)
comment:7 Changed 12 years ago by
We already have karatsuba, which leads to really bad bugs like
sage: R.<x> = RR[] sage: (x+1e20)^2 1.00000000000000*x^2 + 1.00000000000000e40
for inexact rings. I don't think there's anything for division yet though.
comment:8 Changed 12 years ago by
For multiplication, Karatubsa has complexity n^{1.58} in the degree; there exist algorithms with complexity n log(n) log(log(n)) over arbitrary (associative unital) rings. I think it's worth implementing this at some point.
Yes, we need division too. And we need a framework to deal with the very nasty bug you mentioned above. Basically Karatsuba should be disallowed by default for such rings, I don't see any other way around it. Perhaps the user should be able to call some interface for multiplication which uses karatsuba/etc on polynomials when the user knows in advance that the data is "uniform" enough to make the asymptotically fast algorithm accurate enough.
I totally can't work on this right now.
comment:9 Changed 12 years ago by
- Resolution set to fixed
- Status changed from new to closed
Well, since this ticket is somewhat vague and there exists some code which at least implements parts of what is wanted I am closing this as fixed. Please open other, more specific tickets for things you want to do in this area.
Cheers,
Michael
Some progress has been made on this: Robert Bradshaw moved the implementation of
Polynomial_generic_dense
into Cython (insage/rings/polynomial/polynomial_element.pyx
).Related: I am planning to start work on an implementation of polynomials over Z that interfaces directly with NTL instead of going via the
ntl.pyx
objects, as soon as #411 is resolved.