#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 lftabera):
Hi Sebastian,
Replying to [comment:10 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.
This is my fault. Of course I have made much more testing (random
polynomials over different rings and ranged degrees), but they are not
reflected in the ticket. I will upload the scripts I used for testing.
> - 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.
Ok I agree, but this ticket is not about polynomials for number fields,
but multiplication of Polynomial_generic_dense_field elements.
A new class for polynomials over number fields would be good, but that is
a different ticket. Also, the claim that PARI is better for small degrees
is not so clear to me, at least without some nontrivial work.
K.random_element creates polynomials with very small coefficients and no
denominator, these polynomials are not the most common user-base case in
my opinion. For such polynomials, it seems to me that memory management is
the problem, creating and destroying lots of number field elements. If you
take not so big coefficients and, specially, if your coefficients do have
denominators, then PARI is not better due to flint integers in sage.
Note: computations made on an old laptop.
{{{
sage: f=K.random_element(15,10**6) / ZZ.random_element(10**6)
sage: g=K.random_element(15,10**6) / ZZ.random_element(10**6)
sage: fpari = nfpol_to_pari(f)
sage: gpari = nfpol_to_pari(g)
sage: %timeit _=f._mul_karatsuba(g,8)
125 loops, best of 3: 4.56 ms per loop
sage: %timeit fpari*gpari
25 loops, best of 3: 11 ms per loop
sage: f=K.random_element(1500,10**6) / ZZ.random_element(10**6)
sage: g=K.random_element(1500,10**6) / ZZ.random_element(10**6)
sage: fpari = nfpol_to_pari(f)
sage: gpari = nfpol_to_pari(g)
sage: %time _=f._mul_karatsuba(g,8)
CPU times: user 3.90 s, sys: 0.05 s, total: 3.95 s
Wall time: 9.30 s
sage: %time _=fpari*gpari
CPU times: user 7.17 s, sys: 0.08 s, total: 7.25 s
Wall time: 18.11 s
}}}
> - 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.
Ok, this is a bad example, I needed some rings that produced genuine
Polynomial_generic_dense_field appart from number fields. I also wanted to
compare the algorithm with singular multivariate multiplication which I
think it is considered fairly good. Note that ZZ[x][y] are currently
arrays of mpz_t elements.
> - 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!
Answered above.
> 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.
QQbar is an exact ring, so it will use karatsuba multiplication. But
computations are done inexactly if they are safe. Since the karatsuba code
for different degree polynomials have changed, then the inexact results
for inexact rings have also changed. I think that this is the reason for
the change of the doctest here.
> 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.
Do not worry, certainly your comments and Jeroen's are really welcome.
Luis
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:11>
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.
