#10255: improve karatsuba multiplication of univariate polynomials
--------------------------------+-------------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.6.1
Component: basic arithmetic | Keywords: karatsuba, multiplication,
polynomial
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Comment(by spancratz):
Hi Luis,
I'm sorry for the delay in my reply. Also, thank you Jeroen for adding
the explicit timings. Let me just go through a couple of things:
- "I feel that the ticket is ready for review"
I don't really agree. It is certainly in a rather useful state, but it
requires more people looking at it, using it, and providing feedback.
- For one, as you say, this "is a very basic feature, so we cannot
allow correctness bugs here." There should be a *lot* more tests. Rather
than having a single test case for illustrative purposes (as is the case
in many places in the Sage library), there should be more bulk tests here.
You could have that in the Sage framework e.g. by creating a list with
``f._mul_karatsuba(g) - f*g`` for many random pairs (f,g), then remove
duplicates from the list, and check that the list has length one and only
contains 0.
- Your code is still noticeably slower than PARI for the base ring
being a number field of small degree. I guess strongly that this will be
a much more typical use case than large degree number fields and as such
this is not acceptable.
- Another one of your examples is ``ZZ[x]['y']['z']['t']``. I think
this is a very bad example. I don't think one should ever expect a user
to work with a multivariate polynomial ring in this way just to get some
obscure speed-up. Of course, dense and sparse multivariate polynomial
rings offer massively different performance characteristic. Perhaps there
should be a ``dense`` option to ``MPolynomialRing``, but that's not for
this ticket. In any case, this example should not be relevant here.
Finally, if you really care about dense multivariate polynomials over the
integers, I am sure this can be done much, much faster using C or Cython
and arrays of ``mpz_t``'s for the coefficients. The speed-up of this will
be much, much larger than anything you get from nesting a bunch univariate
polynomial rings in Python.
- Finally, the statement
"If you take into account a naive transformation from sage data to pari
and back, the total time is worse than the mul_karatsuba time. So if a
specialiczed class would use PARI, this transformation has to be taken
into account."
is not true. In short, the code for polynomials over number fields should
then be changed so that the internal representation simply was the PARI
object --- no converting back and forth in between the computations
whatsoever!
I have looked at the currently only remaining failing test case in QQbar.
Unfortunately, I am very puzzled by what could possibly cause this and
don't have any help to offer right now.
By the way, I am sorry if this might sound a little harsh in places. Of
course, as said, I am still very happy to keep looking at this etc.
Best wishes,
Sebastian
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
