On Saturday, December 13, 2014 4:05:09 PM UTC+1, Bruno Grenet wrote: > > Working on ticket #15790 <http://trac.sagemath.org/ticket/15790>,¹ I've > noticed that coercion from Sparse Polynomial Ring over ZZ to Dense > Polynomial over ZZ with FLINT implementation is unexpectedly slow. It is > not the case with the NTL implementation, and it is actually not the case > either if we do not do coercion but simply define the same polynomial > directly: > > sage: R.<x> = PolynomialRing(ZZ,sparse=True) > sage: S.<y> = PolynomialRing(ZZ,implementation="FLINT") > sage: T.<z> = PolynomialRing(ZZ,implementation="NTL") > sage: f=x^100000 > > sage: %time S(f) # Coercion, with FLINT > CPU times: user 8.83 s, sys: 96 ms, total: 8.92 s > Wall time: 8.94 s > y^100000 > > sage: %time T(f) # Coercion, with NTL > CPU times: user 32.1 ms, sys: 0 ns, total: 32.1 ms > Wall time: 32.1 ms > z^100000 > > sage: %time _= y^100000 # Direct input, with FLINT > CPU times: user 624 µs, sys: 4 µs, total: 628 µs > Wall time: 637 µs > > Despite the fact that this is way faster with NTL, the time complexity > seems to be linear with NTL and quadratic with FLINT. >
This is a bug in flint. When we set the k:th coefficient, we first zero-extend the polynomial from its current length, write the coefficient, and then normalise by removing leading zero coefficients. When the polynomial is zero and the coefficient to be written is zero, this costs O(k). So for constructing x^n from the list [0, 0, 0, ..., 1], the cost becomes O(n^2). If you want a quick workaround in Sage, change __init__ in polynomial_integer_dense_flint.pyx (line 249) to loop in reverse order. That leaves the question of why it takes Sage 30 ms to do a conversion that should take < 1 ms. Presumably, instead of creating a temporary Python list with 10^5 zeros in it, it would be better to iterate only over the nonzero coefficients when the input is a sparse polynomial. Fredrik -- You received this message because you are subscribed to the Google Groups "sage-devel" 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-devel. For more options, visit https://groups.google.com/d/optout.
