Timing issues for Multiplication in LaurentPolynomialRing() (version 6.2)

[Markus-Ludwig Wermer]

Hey everyone,

since my update to Sage 6.2 I noticed some timing issues when multiplying elements of LaurentPolynomialRing() over some finite fields, say FiniteField(25).

Some basic multiplications were more than 10 times faster in Sage 6.1.1. 

Is there a way to speed up those multiplications?

Also the ordering of elements in the LaurentPolynomialRing is reversed compared to 6.1.1. It would be good, if such changes are noted somewhere.

Best

Markus

One may check the following:

The settings:

Myfield.<a> = FiniteField(25)

L.<t> = LaurentPolynomialRing(Myfield)

The function:

def MultiplicationTime(element, factor, steps):

    ti = time.time()

    factor2 = factor^-1

    for i in range(steps):

        element = factor * element

        element = factor2 * element

    print time.time() - ti

I am using Win7 64bit -Intel i7 2600 - Oracle VM :4.3.10. Sage 6.1.1 and Sage 6.2 have the same settings:

When calling MultiplicationTime(a*t,t,32000), the timing in Sage 6.1.1 varies around 0.17 and  in Sage 6.2 around 1.9.

When calling MultiplicationTime(a*t,a,32000), the timing in Sage 6.1.1 varies around 0.3 and  in Sage 6.2 around 6.2.

I know, that the implementation of LuarentPolynomialRing was rewritten, and now some exponentoverflow - problems I had are gone (in the given function, the call with more than 32768 steps raised an exponent overflow in Sage 6.1.1, although the exponent stays the same after each pair of multiplication).

[Nils Bruin]

On Wednesday, June 4, 2014 7:32:38 AM UTC-7, Markus-Ludwig Wermer wrote:

Some basic multiplications were more than 10 times faster in Sage 6.1.1. 

Is there a way to speed up those multiplications?

 

We can get a reasonable first impression of what is taking most time by profiling some code:

 %prun  MultiplicationTime(a*t,t,32000)

        1    1.334    1.334    1.812    1.812 <ipython-input-3-9aaa272deab5>:1(MultiplicationTime)
    64006    0.297    0.000    0.421    0.000 {method 'element_from_data' of 'sage.rings.finite_rings.element_givaro.Cache_givaro' objects}
   128007    0.055    0.000    0.068    0.000 finite_field_givaro.py:359(gen)
    64006    0.038    0.000    0.459    0.000 finite_field_givaro.py:226(_element_constructor_)
    64006    0.028    0.000    0.056    0.000 gap.py:1648(is_GapElement)
    64015    0.028    0.000    0.028    0.000 {isinstance}
    64002    0.018    0.000    0.018    0.000 laurent_polynomial_ring.py:707(polynomial_ring)
   128007    0.012    0.000    0.012    0.000 {method 'gen' of 'sage.rings.finite_rings.element_givaro.Cache_givaro' objects}

%prun  MultiplicationTime(a*t,a,32000)

        1    4.315    4.315    5.699    5.699 <ipython-input-3-9aaa272deab5>:1(MultiplicationTime)
    64001    0.725    0.000    0.737    0.000 polynomial_ring.py:306(_element_constructor_)
    64001    0.350    0.000    0.501    0.000 {method 'element_from_data' of 'sage.rings.finite_rings.element_givaro.Cache_givaro' objects}
   128002    0.065    0.000    0.079    0.000 finite_field_givaro.py:359(gen)
    64001    0.060    0.000    0.067    0.000 finite_field_givaro.py:174(degree)
    64001    0.049    0.000    0.550    0.000 finite_field_givaro.py:226(_element_constructor_)
   128002    0.048    0.000    0.048    0.000 {isinstance}
    64001    0.036    0.000    0.072    0.000 gap.py:1648(is_GapElement)
    64001    0.029    0.000    0.029    0.000 laurent_polynomial_ring.py:707(polynomial_ring)
   128002    0.013    0.000    0.013    0.000 {method 'gen' of 'sage.rings.finite_rings.element_givaro.Cache_givaro' objects}
    64001    0.007    0.000    0.007    0.000 {method 'exponent' of 'sage.rings.finite_rings.element_givaro.Cache_givaro' objects}

This suggests that element_from_data uses significant time. This is a generic conversion routine! Looking around in the call graph would probably show where this happens. Given most elements lie in the right ring already, it may well be possible to avoid it and/or optimize the code path through it for frequent cases ( little tip-off is the freqent use of is_GapElement, which probably should not be checked at all, because this code doesn't ever seem to come near GapLib. It's also cheap, though, so by itself not really responsible for a lot of time use)

You may also want to check if the degradation in performance is uniform. The examples you are trying are quite basic and perhaps not typical for most use (getting an idea of what "most use" is would already be very useful in general and certainly for optimizing!). Is the current implementation perhaps better in other cases?

[Nils Bruin]

On Wednesday, June 4, 2014 8:58:37 AM UTC-7, Nils Bruin wrote:

This suggests that element_from_data uses significant time. This is a generic conversion routine! Looking around in the call graph would probably show where this happens. Given most elements lie in the right ring already, it may well be possible to avoid it and/or optimize the code path through it for frequent cases ( little tip-off is the freqent use of is_GapElement, which probably should not be checked at all, because this code doesn't ever seem to come near GapLib. It's also cheap, though, so by itself not really responsible for a lot of time use)

As it turns out, this gets triggered by sage.rings.polynomial.laurent_polynomial.LaurentPolynomial_univariate.__normalize, because it wants to know the valuation of the underlying polynomial. It has this little loop, which you would think is pretty fast:

            for k from 0 <= k <= self.degree():
                if self[k]:
                    return ZZ(k)

However, this ends up executing Polynomial_ZZ_pEX.__getitem__, which leads to:

            K = self._parent.base_ring()
            return K(ZZ_pE_c_to_list(c_pE))

triggering conversion of a list to a Givaro finite field: the slow case. So the problem (if there is any) seems to be that retrieving coefficients of a polynomial is relatively slow, because apparently the coefficients of the polynomial are not stored exactly as elements of the base field.

In general, it seems it would be good if the sequence K(ZZ_pE_c_to_list(ZZ_pEX_coeff(self.x,i))) could be shortcut a bit if self is an NTL poly over a Givaro field K. Given that polynomial_zz_pex seems to ensure it always uses the same minimal polynomial for its coefficients as the base field does, it should be possible to shortcut the conversion by quite a bit. The profile above does indicate that in certain cases, these conversions can end up being quite dominant in runtimes.