#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: |
-----------------------------------+----------------------------------------
Comment(by pernici):
lftabera wrote:
>In that case, one can play with set_karatsuba_threshold in the underlying
univariate polynomial ring to try to find a better balance between
karatsuba and classical multiplication.
Right, one can always use your Karatsuba code; in the case of multivariate
series it seems to me that the best value for K_threshold is infinity.
I have posted some benchmarks in #10532; I have no idea why,
but the case K_threshold =infinity and classical multiplication
perform the same for QQ and GF(7), while the former performs much better
than the latter in the case of RR; I guess that this might generalize to
the statement that the former performs much better than the latter in the
case of (a class of) fields not covered by libsingular.
I do not think that optimizing the code to avoid summing to Python 0
would change much the performance of do_mul_trunc,
since that part of the code takes little time.
I think that do_trunc_karatsuba is faster than do_mul_trunc
because in the former there is a clever split
{{{
left_even = left[::2]; left_odd = left[1::2]
}}}
corresponding to
separating the polynomial `p(t)` in `p_even(t^2)` and `t*p_odd(t^2)`
so that the precision `prec` in `t` is reduced to the precision
`n1=(prec+1)//2` in `t^2`
{{{
l = do_trunc_karatsuba(left_even, right_even, n1, K_threshold)
}}}
while in the latter b and d are the polynomials reduced to `O(t^e)`,
with `e` close to `prec//2`, so that the product is done at full precision
{{{
t0 = do_mul_trunc(b,d,h), with h = prec.
}}}
The middle products in the two cases are comparable.
Maybe you could add a comment about the splitting in do_trunc_karatsuba?
Also there is in the docstring of do_generic_product the misprint `bellow`
.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10480#comment:12>
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.
