#10255: improve karatsuba multiplication of univariate polynomials
--------------------------------+-------------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7.2
Component: basic arithmetic | Keywords: karatsuba, multiplication,
polynomial
Work_issues: | Upstream: N/A
Reviewer: | Author: Luis Felipe Tabera Alonso
Merged: | Dependencies:
--------------------------------+-------------------------------------------
Old description:
> For univariate polynomials over exact rings, plain karatsuba is used.
>
> However, the degree in which karatsuba starts to be better than plain
> multiplication looks too high for me.
>
> Some optimization must be made.
>
> {{{
> sage: K=QQ[I][x]
> sage: f=K.random_element(1500)
> sage: g=K.random_element(1500)
> sage: %time _ = f._mul_generic(g)
> CPU times: user 6.03 s, sys: 0.08 s, total: 6.11 s
> Wall time: 6.43 s
> sage: %time _ = f._mul_karatsuba(g)
> CPU times: user 6.95 s, sys: 0.06 s, total: 7.01 s
> Wall time: 7.76 s
> }}}
>
> For instance, many time is used adding elements of the ring with python
> 0. Causing an overhead of up to 75% for some rings.
>
> With the added patch we can get up to gain of four times the speed.
New description:
For univariate polynomials over exact rings, plain karatsuba is used.
However, the degree in which karatsuba starts to be better than plain
multiplication looks too high for me.
Some optimization must be made.
{{{
sage: K=QQ[I][x]
sage: f=K.random_element(1500)
sage: g=K.random_element(1500)
sage: %time _ = f._mul_generic(g)
CPU times: user 6.03 s, sys: 0.08 s, total: 6.11 s
Wall time: 6.43 s
sage: %time _ = f._mul_karatsuba(g)
CPU times: user 6.95 s, sys: 0.06 s, total: 7.01 s
Wall time: 7.76 s
}}}
For instance, many time is used adding elements of the ring with python 0.
Causing an overhead of up to 75% for some rings.
With the added patch we can get up to gain of four times the speed.
Apply: trac_karatsuba_improvements.2.patch
--
Comment(by lftabera):
rebase against 4.7.1
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:19>
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.
