#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):
Obviously you did not try the computations with my patch, it is still much
slower than PARI for small number fields (as I acknowledge in the ticket,
PARI is around three times faster for degree two extensions):
{{{
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 5.94 s, sys: 0.02 s, total: 5.96 s
Wall time: 6.01 s
sage: %time _ = f._mul_karatsuba(g)
CPU times: user 1.31 s, sys: 0.00 s, total: 1.32 s
Wall time: 1.33 s
sage: K.set_karatsuba_threshold(8)
sage: %time _ = f._mul_karatsuba(g)
CPU times: user 0.97 s, sys: 0.00 s, total: 0.97 s
Wall time: 1.00 s
sage: %time fpari = nfpol_to_pari(f)
CPU times: user 0.24 s, sys: 0.00 s, total: 0.24 s
Wall time: 0.25 s
sage: %time gpari = nfpol_to_pari(g)
CPU times: user 0.24 s, sys: 0.00 s, total: 0.24 s
Wall time: 0.25 s
sage: %time hpari = fpari*gpari
CPU times: user 0.42 s, sys: 0.00 s, total: 0.42 s
Wall time: 0.44 s
sage: %time h = K(hpari)
CPU times: user 0.70 s, sys: 0.02 s, total: 0.72 s
Wall time: 0.73 s
}}}
If you take into account a naive transformation from sage data to pari and
back, the total time is worse than the mul_karatsuba time. So if a
specialiczed class would use PARI, this transformation has to be taken
into account.
This pari advantage disapears for bigger number fields
{{{
sage: K=CyclotomicField(7)[x]
sage: f=K.random_element(1500)
sage: g=K.random_element(1500)
sage: %time _ = f._mul_karatsuba(g)
CPU times: user 15.33 s, sys: 0.02 s, total: 15.35 s
Wall time: 15.44 s
sage: %time _ = f._mul_karatsuba(g,8)
CPU times: user 12.96 s, sys: 0.08 s, total: 13.03 s
Wall time: 13.10 s
sage: %time fpari = nfpol_to_pari(f)
CPU times: user 0.30 s, sys: 0.00 s, total: 0.30 s
Wall time: 0.32 s
sage: %time gpari = nfpol_to_pari(g)
CPU times: user 0.30 s, sys: 0.00 s, total: 0.31 s
Wall time: 0.32 s
sage: %time hpari = fpari*gpari
CPU times: user 24.26 s, sys: 0.02 s, total: 24.28 s
Wall time: 25.23 s
sage: %time h = K(hpari)
CPU times: user 1.48 s, sys: 0.03 s, total: 1.50 s
Wall time: 1.52 s
}}}
Note: for absolute number fields, I am used to set a karatsuba threshold
in 8.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:9>
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.
