Opened 7 years ago

Last modified 6 years ago

#15427 new enhancement

Performance of casting polynomials to polynomials over finite fields

Reported by: afiori Owned by:
Priority: minor Milestone: sage-6.4
Component: performance Keywords: FiniteField Polynomial Casting
Cc: roed, jpflori Merged in:
Authors: Andrew Fiori Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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.

Attachments (1)

FiniteFieldPolyCast.patch (1.1 KB) - added by afiori 7 years ago.

Download all attachments as: .zip

Change History (6)

Changed 7 years ago by afiori

comment:1 Changed 7 years ago by afiori

  • Authors set to Andrew Fiori

comment:2 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 7 years ago by jpflori

  • Cc jpflori added

comment:5 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.