# Changes between Version 44 and Version 59 of Ticket #9944

Ignore:
Timestamp:
05/13/11 15:44:45 (9 years ago)
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

### Legend:

Unmodified
• Property Dependencies changed from to `sage-4.7`