#10480: fast PowerSeries_poly multiplication
-----------------------------------+----------------------------------------
Reporter: pernici | Owner: malb
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.6.2
Component: commutative algebra | Keywords: power series
Author: mario pernici | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------------+----------------------------------------
Changes (by lftabera):
* status: new => needs_work
* milestone: sage-4.6.1 => sage-4.6.2
Comment:
Could you please check if the changes of #10255 in karatsuba
multiplication provide further improvement?
PowerSeries are constructed over commutative rings, but
polynomial_elements do not. Hence mul_trunc needs to work also over
noncommutative rings. It does not right now (al least lines 5342 and 5345
do not differenciate between left and right multiplication).
I see several improvements:
I think that
cdef int i, j, a1len, a2len, n1, n2, ih
in line 5334 should be Py_ssize_t, but maybe a cython expert should look
at this.
c = [0]*h in line 5346 of the patch is inefficient in several cases. One
of the most contributions in 10480 is to avoid python 0 'int' in the code,
that can be (relatively) expensive to coerce. I guess that this code will
be slow if the base ring is a number field (that has slow coercion).
The last loop is classical multiplication up to the precision required. I
wonder if part of that multiplication could use do_karatsuba or a
truncated_do_karatsuba.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10480#comment:1>
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.
