#10480: fast PowerSeries_poly multiplication
-------------------------------------------------+-------------------------
Reporter: pernici | Owner: malb
Type: enhancement | Status:
Priority: major | needs_review
Component: commutative algebra | Milestone: sage-6.2
Keywords: power series | Resolution:
Authors: Mario Pernici, Luis Felipe | Merged in:
Tabera Alonso | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #10255 | Stopgaps:
-------------------------------------------------+-------------------------
Changes (by rws):
* cc: zimmerma (added)
Comment:
Have you looked at the implementation of Karatsuba and Schönhage-Strassen
in GMP-ECM? Quote:
GMP-ECM features Schönhage-Strassen multiplication for polynomials in
stage 2 when factoring Fermat numbers (not in the new, fast stage 2 for
P+1 and P-1. This is to be implemented.) This greatly reduces the number
of
modular multiplications required, thus improving speed. It does, however,
restrict the length of the polynomials to powers of two, so that for a
given
number of blocks (-k parameter), the B2 value can only increase by factors
of
approximately 4.
For the number of blocks, choices of 2, 3 or 4 usually give best
performance.
However, if the polynomial degree becomes too large, relatively expensive
Karatsuba or Toom-Coom methods are required to split the polynomial before
Schönhage-Strassen's method can handle them. That can make a larger number
of blocks worthwhile. ...
--
Ticket URL: <http://trac.sagemath.org/ticket/10480#comment:23>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
