#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):
Sebastian,
Thanks for looking at this. I feel that the ticket is ready for review,
but there is a doctest fail and I wanted to understand why. My impression
is that the doctest should be changed, but I did not have enough time to
dig it.
Replying to [comment:6 spancratz]:
> 1) What is your main motivation for wanting to improve this code?
If you want to achieve faster computations in polynomial rings over
specific rings, QQ[i], you should most definitely either write some Cython
code or even a separate C library. You should *not* be tinkering with the
generic Python multiplication code. To keep with the example, if you are
interested in QQ[i], then (just as a first idea) you should represent your
polynomials as sums of two polynomials internally, one for the real part
and one for the imaginary code. This approach also applies to other
number fields of small degree.
My primary interest was univariate polynomial rings over number fields of
degree around 30-40. I was considering to use the specific class I have
added in #8558, because, for number field base rings, the slowness comes
really from adding number field elements by python 0. But then I realised
that the karatsuba multiplication is not well enough implemented if both
polynomials have different degree, so I changed the cython code improving
here and there.
> 2) Stating what you definitely already know: Karatsuba
multiplication trades additions and multiplications in the base ring.
Thus, the threshold highly depends on the relative speeds of addition and
multiplication, and it will be very difficult for you to make a default
choice that is useful in general. Even worse, what about base rings where
multiplication is faster than addition?
That is why the default threshold is zero. No classical multiplication at
all. But I have added a ring-dependent parameter to change this value.
Univariate polynomial rings have now a method set_karatsuba_threshold to
deal with this issue. Rings in which addition is faster than
multiplication also benefits from karatsuba, since the number of additions
is also subquadratic in the degree of the polynomials.
> 3) I haven't looked at the details, but I believe you might simply
not be able to apply this code to polynomial rings with inexact base
rings.
By default, unless the user calls explicitelly _mul_karatsuba,
mutiplication for inexact rings is the classical multiplication algorithm.
I have not changed this. Also,if a class (ZZ[x], GF(5)[x], etc.) has its
own multiplication code, my patch does not change this.
> All that said, while this patch looks very interesting, I think there
are a lot of things that need to be sorted out. By the way, I am not
quite sure whether any one else is currently reading this ticket, but at
least during the next week I should have a lot of time to look at this.
Thanks!, if you have any question on why I changed this or that or have
further suggestions/improvements, do not hesitate to ask.
Luis
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:7>
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.
