#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):
Replying to [comment:12 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?
The fact that I am interested in polynomials over number fields does not
invalidate the fact that the current generic karatsuba method must be
changed because it is too inefficient. Do you think that mul_karatsuba is
ok when it is slower for degree 1500 polynomials?
> 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.
It does improve across all rings (or at least is not worse) because:
- It has less function calls, less slicing of lists and less if
branches (low impact).
- It does not perform plenty of unnecessary additions of 0 +
ModuleElement (high impact over some base rings, like number fields or
orders of number fields).
- User has control over the karatsuba threshold, this can speed up
things in some cases. By default the threshold is the same as the previous
implementation. So this is not worse than the previous method (quite ring
dependent).
- The case of different sized polynomials is inefficient in the
current implementation (high impact over every ring).
This last reason is very important. For instance, take a pair of
polynomials over ZZ. One of degree twice the other. _mul_karatsuba is
slower than _mul_generic independently of the degree. This is a bug in my
opinion.
{{{
sage: K=ZZ[x]
sage: f=K.random_element(4000)
sage: g=K.random_element(2000)
sage: h=K.random_element(1500)
sage: %time _= f._mul_generic(g)
CPU times: user 0.90 s, sys: 0.00 s, total: 0.90 s
Wall time: 0.90 s
sage: %time _= f._mul_karatsuba(g)
CPU times: user 2.65 s, sys: 0.00 s, total: 2.66 s
Wall time: 2.66 s
sage: %time _= f._mul_karatsuba(h)
CPU times: user 3.41 s, sys: 0.00 s, total: 3.41 s
Wall time: 3.42 s
}}}
With patch:
{{{
sage: K=ZZ[x]
sage: f=K.random_element(4000)
sage: g=K.random_element(2000)
sage: h=K.random_element(1500)
sage: %time _=f._mul_generic(g)
CPU times: user 0.90 s, sys: 0.00 s, total: 0.90 s
Wall time: 0.91 s
sage: %time _=f._mul_karatsuba(g)
CPU times: user 0.24 s, sys: 0.00 s, total: 0.24 s
Wall time: 0.24 s
sage: %time _=f._mul_karatsuba(h)
CPU times: user 0.25 s, sys: 0.00 s, total: 0.25 s
Wall time: 0.25 s
}}}
I do not care if FLINT is lightning fast here. This example is just a
symptom that _mul_karatsuba is not doing its job compared with
_mul_generic. Moreover, multiplying a polynomial of degree 4000 and other
of degree 1500 is much slower than multiplying a polynomial of degree 4000
and other of degree 2000. With the patch they cost around the same time,
not something I am confortable with.
More examples for more rings, taking two polynomials. One of degree 27 and
the other 31. The first line is the time taking with my patch, second line
with SAGE 4.6.
{{{
ZZ[x]
625 loops, best of 3: 195 µs per loop
625 loops, best of 3: 435 µs per loop
ZZ[I][x]
625 loops, best of 3: 1.05 ms per loop
5 loops, best of 3: 219 ms per loop
ZZ[I,sqrt(2)][x]
25 loops, best of 3: 10.3 ms per loop
5 loops, best of 3: 317 ms per loop
QQ[x]
625 loops, best of 3: 1 ms per loop
125 loops, best of 3: 1.93 ms per loop
Integers(6)[x]
625 loops, best of 3: 263 µs per loop
625 loops, best of 3: 890 µs per loop
ZZ[x]['y']
625 loops, best of 3: 263 µs per loop
125 loops, best of 3: 5.06 ms per loop
QuaternionAlgebra(1,1)[x]
125 loops, best of 3: 2.36 ms per loop
125 loops, best of 3: 4.43 ms per loop
GF(2)[x].fraction_field()[y]
5 loops, best of 3: 44 ms per loop
5 loops, best of 3: 70.6 ms per loop
QQ[x].fraction_field()['y']
5 loops, best of 3: 229 ms per loop
5 loops, best of 3: 290 ms per loop
GF(5)[x].quotient_ring(x^5-x)[x]
5 loops, best of 3: 53.5 ms per loop
5 loops, best of 3: 80.6 ms per loop
SR[x]
625 loops, best of 3: 1.26 ms per loop
125 loops, best of 3: 3.95 ms per loop
QQ['x,y,z']['t']
25 loops, best of 3: 25.7 ms per loop
25 loops, best of 3: 34.1 ms per loop
GF(7^2,'a')[x] #Here the time is virtually the same due to the cost of
creating the lists
5 loops, best of 3: 68.8 ms per loop
5 loops, best of 3: 71.3 ms per loop
}}}
- x200 faster for orders of number fields
- x30 for relative orders
- x2 faster for quaternion algebras
- x2 for the symbolic ring
I do not think that this is a small improvement.
> 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?
I'll do
> 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.
Ok, but you are disregarding all other cases.
> 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.
I have not really changed _mul_generic, only moved the code to avoid
duplication of code. Calling list is already in the original code. list is
also used for addition by the way. But I realize something, I have to take
care of inline operations in the code. If base ring elements are inmutable
(as I think they are expected to) this will just call non-inlined
operations. If they are mutable, multiplication of polynomials will change
the input polynomials, which is wrong. I will change this.
> - 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.
I will take a look,
Best regards,
Luis
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:13>
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.
