#10255: improve karatsuba multiplication of univariate polynomials
--------------------------------+-------------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.6.2
Component: basic arithmetic | Keywords: karatsuba, multiplication,
polynomial
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Comment(by spancratz):
Hi Luis,
I am terribly sorry for not writing on this thread again any earlier;
after returning to the UK following the Sage bug days in Seattle, I was
busy catching up on some other things. Anyway...
> > > 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?
Of course, it is great that (via this patch!) there might soon be some
code which speeds up the generic implementation. But to be honest,
personally I don't think the generic implementation is all that important;
after all, it is only a fall-back option used if no-one has brought up
enough energy to implement something more specific.
> I do not care if FLINT is lightning fast here.
I feel this is a bit of a shame. Like rjf mentioned on sage-devel for
many base rings you will be able to come up with something much, much
faster than this small (by comparison!) improvement.
> 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.
Of course, you are right, this is ridiculous. Implicit zero-padding (or
even explicit, if you assume only references are stored) should be nearly
for free, so a 4000 by 1500 product shouldn't cost any noticeably more
than a 4000 by 2000 product. (Of course, ideally it should cost less!)
> - 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.
Obviously, we can agree to disagree here. In absolute terms, all of the
above improvements are fantastic! In relative terms, looking at what
would be possible just by writing base ring specific code, however, I am
confident you could do better.
> > 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
> > }}}
>
> Ok, but you are disregarding all other cases.
Obviously, and deliberately so. But please let me know which ring you
actually, mathematically care about. I would not be surprised if we could
come up with something noticeably faster!
By the way, I am not sure whether anyone else is looking at this bit of
code. While I can't promise how much spare time I will have in the next
couple of weeks, I am happy to keep looking at this, run tests, give
comments etc.
Best wishes,
Sebastian
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:15>
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.
