Performance of casting polynomials to polynomials over finite fields

[be5da901-b603-4a23-a619-a961be3f50a0]

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.

CC: @roed314 @jpflori

Component: performance

Keywords: FiniteField Polynomial Casting

Author: Andrew Fiori

Issue created by migration from https://trac.sagemath.org/ticket/15427

[be5da901-b603-4a23-a619-a961be3f50a0]

Attachment: FiniteFieldPolyCast.patch.gz

[be5da901-b603-4a23-a619-a961be3f50a0]

Author: Andrew Fiori