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 dmharvey

Some progress has been made on this: Robert Bradshaw moved the implementation of Polynomial_generic_dense into Cython (in sage/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.

comment:2 Changed 13 years ago by dmharvey

related: #528

comment:3 Changed 13 years ago by mabshoff

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

What is the status of this?

Cheers,

Michael

comment:6 Changed 12 years ago by dmharvey

Perhaps the title should be changed to "compiled implementation of asymptotically fast dense univariate polynomial arithmetic" :-)

comment:7 Changed 12 years ago by robertwb

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 dmharvey

For multiplication, Karatubsa has complexity n1.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 mabshoff

  • 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

Note: See TracTickets for help on using tickets.