#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):
Hello,
First of all, I want to say that it's great that you are looking at this
part of the Sage library and are trying to improve it!
From reading your ticket progress, it seems that perhaps you might benefit
from some help with this. Have you considered advertising this problem on
the developers' list at sage-devel? Perhaps someone else is interested in
this, too.
In any case, here are a couple of comments:
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.
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?
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.
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.
Best wishes,
Sebastian
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:6>
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.
