#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 spancratz):
Hi Luis,
> Ok, this is a bad example, I needed some rings that
> produced genuine Polynomial_generic_dense_field appart
> from number fields.
> Ok I agree, but this ticket is not about polynomials for number
> fields, but multiplication of Polynomial_generic_dense_field
> elements.
Well, which base ring is it that you are interested in?
I don't really think there is all that much point in squeezing
a small improvement out of the generic case when often much
more is available, even more so when it is not clear that your
patch improves the run-time across all base rings.
By the way, perhaps other developers might disagree with me.
Perhaps it would be a good idea for you to ask about this on
sage-devel?
Of course, these are just words... Here's an example:
{{{
sage: R.<x> = QQ[I][]
sage: f = R.random_element(1500)
sage: g = R.random_element(1500)
sage: %time _ = f._mul_generic(g)
CPU times: user 4.39 s, sys: 0.01 s, total: 4.40 s
Wall time: 4.42 s
sage: %time _ = f._mul_karatsuba(g)
CPU times: user 5.63 s, sys: 0.04 s, total: 5.67 s
Wall time: 5.73 s
sage: S.<y> = QQ[]
sage: f0 = S([f[i][0] for i in range(f.degree() + 1)])
sage: f1 = S([f[i][1] for i in range(f.degree() + 1)])
sage: g0 = S([g[i][0] for i in range(g.degree() + 1)])
sage: g1 = S([g[i][1] for i in range(g.degree() + 1)])
sage: timeit('f0 * g0 - f1 * g1')
125 loops, best of 3: 2.76 ms per loop
sage: timeit('f1 * g0 + f0 * g1')
125 loops, best of 3: 2.99 ms per loop
}}}
Here, the current code takes about 5s, whereas one can easily
complete the computation in 6ms. This improvement is much
better than the factor of 7 that your patch provides.
By the way, I believe a similar trick works for all polynomials
over number fields in the case when the degree of the polynomial
is typically larger than the degree of the number field.
In the opposite, when the degree of the number field is
typically larger than the degree of the polynomials, I guess
one would want to take a different approach.
> I also wanted to compare the algorithm with singular
> multivariate multiplication which I think it is considered
> fairly good.
Hopefully, my code snippet above convinces you that the current
implementation of ``QQ[I]['x']`` isn't all that good.
> Note that ZZ[x][y] are currently arrays of mpz_t elements.
I do not think this is true. ZZ['x']['y'] is different from
ZZ['x','y']. The latter is implemented as a sparse multivariate
polynomial ring. But the former is *not* implemented as a single
contiguous array of ``mpz_t``'s but as a list of coefficients,
where each coefficient (i.e. polynomials in ZZ['x']) is again
implemented (in FLINT, this time) as an array of ``mpz_t``'s.
That is to say, here you have nested lists, which is not was I
meant: I meant a single contiguous array of ``mpz_t``'s. I'm
not saying one should do that in the generic case, but if one
really cares about dense two-variate polynomials over ZZ, this
approach should be favourable.
Anyway, all that said, let's be more positive again and look
at your actual code:
- In ``_mul_generic``, I think you should move some of
the isolated and non-edge cases from TESTS to EXAMPLES.
TESTS should then contains more bulk tests as suggested
earlier on this ticket.
- In ``_mul_generic``, your calls to ``list()`` will likely
create new lists of objects. If they are guaranteed to
be shallow copies of the elements, that is ok. This needs
to be verified. If they are deep copies, however, this
should be changed.
- The code in ``do_karatsuba`` is not very readable. I think
this can easily be improved by removing all the comments
from the function body --- there are many more comment lines
then actual code lines! --- into a brief descriptive
documentation in the function header.
Best wishes,
Sebastian
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#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.
