Changes between Version 44 and Version 59 of Ticket #9944
- Timestamp:
- May 13, 2011, 3:44:45 PM (12 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 classesThis 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 parentP
of a polynomialself
is already known when callingself._new_constant_poly(a, P)
, so that it would be a waste of time to callself.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 withP.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 inP
without calling coercion, and if it has_rmul_
and if_rmul_
does not returnNone
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 genericconstant_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 alsoQQ
) they can be implemented withFLINT
orNTL
. 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
andsparse
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
- Added
- Removed
- Modified
-
Ticket #9944
-
Property
Dependencies
changed from
to
sage-4.7
-
Property
Dependencies
changed from
-
Ticket #9944 – Description
v44 v59 7 7 4. [attachment:trac9944_polynomial_speedup.patch] 8 8 5. [attachment:trac9944_abvar_endomorphism.patch] 9 6. [attachment:trac9944_faster_and_cleaner_coercion.patch]