Changes between Version 44 and Version 59 of Ticket #9944

Timestamp:

05/13/11 15:44:45 (11 years ago)

Author:

SimonKing

Comment:

Finally I got my new patch to work. Here are the new features and, in particular, the new timings. I think it was worth the effort!

Polynomial Construction Functors

sage: R.<x> = PolynomialRing(GF(5), sparse=True)
sage: F,B = R.construction()
sage: F(B) is R
True   # was False

zero_element

In various places, constructions such as self.parent()(0) are used. It should be more efficient to have self.parent().zero_element() instead, in particular if this is cached using the improved cached methods from #11115.

That means I had to introduce zero_element() for various classes, mostly in sage/modular.

Fix zero element of free module homomorphisms

The following used to fail with an error:

sage: V = span([[1/2,1,1],[3/2,2,1],[0,0,1]],ZZ)
sage: V.Hom(V).zero()
Free module morphism defined by the matrix
[0 0 0]
[0 0 0]
[0 0 0]
Domain: Free module of degree 3 and rank 3 over Integer Ring
Echelon ...
Codomain: Free module of degree 3 and rank 3 over Integer Ring
Echelon ...

Calling any parent with None should return zero

This used to be true for finite prime fields, but failed with an error for finite non-prime fields:

sage: GF(5)(None)
0
sage: GF(5^2,'a')(None)
0

Implement/improve _new_constant_poly for various polynomial classes

This is the main reason why the timings stated below have improved. I thought that _new_constant_poly should be a method of a polynomial ring, but I think it should better stay as a method of polynomials: Polynomials are often implemented in Cython, but polynomial rings in Python.

In order to get a little bit of more speed, I introduce another parameter to _new_constant_poly, namely the parent in which the new polynomial is supposed to be created. This is because often the parent P of a polynomial self is already known when calling self._new_constant_poly(a, P), so that it would be a waste of time to call self.parent() internally to determine the parent.

Improve Polynomial Base Injection Morphisms and use it for coercion

Conversion into a polynomial ring P from its base ring occurs frequently and should be as quick as possible.

I had already improved the performance in the old patch version. However, it turned out to be better to use _new_constant_poly, rather than always using multiplication with P.one().

The rule is now: If P.an_element() has a _new_constant_poly method then it is used. Otherwise, if one can construct a one element in P without calling coercion, and if it has _rmul_ and if _rmul_ does not return None then it is used. Otherwise, P._element_constructor_ is used.

Polynomial base injection morphisms are now always registered as coercion.

Call method for compiled polynomials

The documentation for compiled polynomials states that it can be called, although the cdef method .eval(...) has less overhead. That was not true, there has been no __call__ method. I added one.

Constant polynomial section

It was stated that it uses the constant_coefficient method, which can be optimized for a particulare polynomial type. However, in fact a generic constant_coefficient method was explicitly called, even if a polynomial type did provide a more efficient method. That has now changed.

Sparse versus dense versus differently implemented polynomial rings

A univariate polynomial ring can be sparse or dense, and if it is dense and over ZZ (or also QQ) they can be implemented with FLINT or NTL. Dense and sparse rings used to be equal, but they were not identical - a violation to the unique parent assumption.

Moreover, in the multivariate case, the implementation and sparse arguments had no effect on the resulting ring, but were used in the cache key, yielding another violation of the unique parent assumption.

I resolved these violations. I was not sure whether one should silently ignore arguments that are not used, or should raise an error if they are provided. I decided to ignore sparse if it is not supported, and raise an error for dense or multivariate rings if an implementation is not supported.

We have, e.g.:

sage: S.<x,y> = PolynomialRing(ZZ,sparse=True)
sage: S is ZZ['x','y']
True  # used to be False
sage: R.<x> = PolynomialRing(ZZ,sparse=True,implementation='FLINT')
sage: S.<x> = PolynomialRing(ZZ,sparse=True,implementation='NTL')
sage: R is S
True  # used to be False
sage: R == ZZ['x']
False # used to be True
sage: S.<x,y> = PolynomialRing(ZZ, implementation='NTL')
Traceback (most recent call last):
...
ValueError: The NTL implementation is not known for multivariate polynomial rings

The last example used to return a ring that was equal but not identic to ZZ['x','y']!

Polynomial rings are now equal if and only if they are identical. Coercions exist from the non-default to the default version of a ring (hence, from sparse to dense, from NTL to FLINT.

sage: R.<x> = PolynomialRing(ZZ)
sage: S.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: R == S
False
sage: R.has_coerce_map_from(S)
True
sage: S.has_coerce_map_from(R)
False
sage: S.<x> = PolynomialRing(ZZ, sparse=True)
sage: R == S
False
sage: R.has_coerce_map_from(S)
True
sage: S.has_coerce_map_from(R)
False

By consequence, the parent of a sum of polynomials is now unique - it used to depend on the summation order if dense and sparse summands were involved.

Documentation and examples

I think all changes are covered by doctests. Occasionally I fixed wrongly formatted docstrings.

Performance

Here are the new timings for the examples that we had discussed above. I use sage-4.7.alpha5 with the patches from this ticket applied, and I compare with timings that I had obtained with an unpatched version of sage-4.7.alpha5

There is no significant change in the startup time: I got 1.253 for sage.all in unpatched sage, but the margin of error seems rather wide.

$ sage -startuptime
...
== Slowest (including children) ==
1.100 sage.all (None)
0.279 sage.schemes.all (sage.all)
0.178 twisted.persisted.styles (sage.all)
0.164 elliptic_curves.all (sage.schemes.all)
0.162 ell_rational_field (elliptic_curves.all)
0.150 ell_number_field (ell_rational_field)
...

Here is the example brought up by Jeroen. There is now a drastic speedup were previously was a drastic slow down:

sage: S = GF(9,'a')
sage: %time for n in range(8): S = PolynomialRing(S,'w')
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
# unpatched: 0.04 s
sage: len(S.variable_names_recursive())
8
sage: timeit("S(0)")
625 loops, best of 3: 27.9 µs per loop
# with only the other patches: 83 ms
# unpatched: 121 µs

Here is the example brought up by Martin Raum:

sage: R = PolynomialRing(ZZ, ['a' + str(n) for n in range(10000)])
sage: x = R.gen(0)
sage: timeit('(2*x - 1)^2 + 5', number = 10^4)
10000 loops, best of 3: 58.2 µs per loop
# unpatched: 66.9 µs

Here are the arithmetic examples that I had provided earlier:

sage: R.<x> = ZZ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 8.58 µs per loop
# unpatched: 23.6 µs
sage: R.<x> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 8.4 µs per loop
# unpatched: 25.8 µs
sage: R.<x> = GF(3)[]   # sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 66.4 µs per loop
# unpatched: 90.1 µs
sage: R.<x> = QQ['t'][]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 75.4 µs per loop
# unpatched: 117 µs
sage: R.<x,y> = ZZ[]  # sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 7.85 µs per loop
# unpatched: 13.6 µs
sage: R.<x,y> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 7.33 µs per loop
# unpatched: 16.9 µs
sage: R.<x,y> = GF(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 6.59 µs per loop
# unpatched: 11.2 µs
sage: R.<x,y> = QQ['t'][]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 158 µs per loop
# unpatched: 251 µs
sage: R.<x,y> = Qp(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 488 µs per loop
# unpatched: 521 µs
sage: R.<x> = Qp(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 894 µs per loop
# unpatched: 1.06 ms
sage: R.<x> = PolynomialRing(GF(9,'a'), sparse=True)
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 236 µs per loop
# unpatched: 265 µs

So, in all examples there is a noticeable speedup.

Conclusion

The new patch cleans coercion of polynomial rings, by enforcing uniqueness of parents.

It considerably improves the performance, even when comparing with the improvements that were introduced in the previous patches.

sage -testall -long passed. So, it is finally ready for review again.

Depends on sage-4.7

Apply Apply 9944-poly-cat.patch 9944-poly-cat-doctests.patch trac-9944-poly-cat-review.patch trac9944_polynomial_speedup.patch trac9944_abvar_endomorphism.patch trac9944_faster_and_cleaner_coercion.patch