#9944: categories for polynomial rings
--------------------------------------------+-------------------------------
Reporter: robertwb | Owner: nthiery
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.7.1
Component: categories | Resolution:
Keywords: | Work_issues:
Upstream: N/A | Reviewer: Nicolas M.
Thiéry, Mike Hansen, Martin Raum
Author: Robert Bradshaw, Simon King | Merged:
Dependencies: sage-4.7 |
--------------------------------------------+-------------------------------
Changes (by SimonKing):
* status: needs_work => needs_review
* dependencies: => sage-4.7
Old description:
> Currently, they're always just commutative rings.
>
> '''Apply:'''
> 1. [attachment:9944-poly-cat.patch]
> 2. [attachment:trac-9944-poly_cat_doctests.patch]
> 3. [attachment:trac-9944-poly-cat-review.patch]
> 4. [attachment:trac9944_polynomial_speedup.patch]
> 5. [attachment:trac9944_abvar_endomorphism.patch]
New description:
Currently, they're always just commutative rings.
'''Apply:'''
1. [attachment:9944-poly-cat.patch]
2. [attachment:trac-9944-poly_cat_doctests.patch]
3. [attachment:trac-9944-poly-cat-review.patch]
4. [attachment:trac9944_polynomial_speedup.patch]
5. [attachment:trac9944_abvar_endomorphism.patch]
6. [attachment:trac9944_faster_and_cleaner_coercion.patch]
--
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9944#comment:59>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
