#15427: Performance of casting polynomials to polynomials over finite fields
-------------------------+-------------------------------------------------
Reporter: afiori | Owner:
Type: | Status: new
enhancement | Milestone: sage-5.13
Priority: minor | Keywords: FiniteField Polynomial
Component: | Casting
performance | Authors:
Merged in: | Report Upstream: N/A
Reviewers: | Branch:
Work issues: | Dependencies:
Commit: |
Stopgaps: |
-------------------------+-------------------------------------------------
One would expect the performance of casting the usual way (as in test 1
below) to be at least not much worse than test 2:
{{{
sage: QQX=QQ['x']
sage: QP=Qp(3,30);
sage: R=QP.residue_field();
sage: RX=R['x'];
sage: prim=primes_first_n(1000)
sage: polysQQ = [ QQX(prim[i:i+30]) for i in range(1,900)]
sage: def test1(PR,l):
return [PR(P) for P in l];
....:
sage: def test2(PR,l):
return [PR([PR.base_ring()(coef) for coef in P.list()]) for P in
l];
....:
sage: %timeit test1(RX,polysQQ)
1 loops, best of 3: 478 ms per loop
sage: %timeit test2(RX,polysQQ)
1 loops, best of 3: 230 ms per loop
}}}
Especially since the actual implementation of casting that is performed
essentially reduces to converting to a list and casting as we do in test
2.
The problem is that the implementation of list->polynomial casting
provided by Polynomial_template is very much not optimal, sufficiently so
that two of the three implementing classes handle lists in their own
__init__ rather than passing through to polynomial template.
The polynomial->polynomial casting is then also inefficient as it converts
the poly to a list and recalls __init__. In the original code this
bypassed the optimized list implementations in the implementing class,
this is what the current patch changes. The effect on performance is as
follows:
{{{
sage: %timeit test1(RX,polysQQ)
1 loops, best of 3: 219 ms per loop
}}}
There is still room for improvement, the current (and with patch)
implementation will in most cases end up calling
Polynomial_template.__init__ twice, and likely also Polynomial.__init__
twice, this is wasteful (even though the calls are largely no-ops). It
would probably be better to, in addition to the currently proposed patch,
special case casts from polynomials in the implementing classes the same
way lists are done to avoid this.
--
Ticket URL: <http://trac.sagemath.org/ticket/15427>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
