search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.41k stars 475 forks source link

disallow ZZ['x'] -> SR coercion #24965

Open rwst opened 6 years ago

rwst commented 6 years ago

Because of

sage: SR.has_coerce_map_from(ZZ['x'])
True

the conversion ZZ['x'] -> SR['x'] goes through the base ring. As a consequence integral polynomials are badly converted into symbolic polynomials (and not into polynomial with symbolic coefficients)

sage: p = (polygen(ZZ)^2 + 1).change_ring(SR)
sage: p.constant_coefficient()
x^2 + 1
sage: type(_)
<type 'sage.symbolic.expression.Expression'>

One option would be to disallow the coercion ZZ['x'] -> SR (but keeping the conversion). Such change is non-backward compatible because of the two following use cases

sage: x = SR.var('x')
sage: R.<y0, y1> = ZZ[]
sage: x.subs(x=y0/y1)
y0/y1

will give

sage: x = SR.var('x')
sage: R.<y0, y1> = ZZ[]
sage: x.subs(x=y0/y1)
Traceback (most recent call last):
...
TypeError: no canonical coercion from Fraction Field of
Multivariate Polynomial Ring in y0, y1 over Integer Ring
to Symbolic Ring

Component: commutative algebra

Issue created by migration from https://trac.sagemath.org/ticket/24965

rwst commented 6 years ago

Branch: u/rws/symboliczero001

rwst commented 6 years ago

Commit: 05708a2

rwst commented 6 years ago

New commits:

05708a2insert print stmts
rwst commented 6 years ago

Description changed:

--- 
+++ 
@@ -26,7 +26,7 @@
 One can see
 - SR is tested for zero once;
 - the coefficients are tested once;
-- twice `x^2 + 1` is tested for zero
+- twice `x^2 + 1` is tested for zero. Note that `x^2 + 1` is the zeroth coefficient, not the polynomial itself.
 - three times `__nonzero__` calls itself at point 2.

 Inserting `return False` at the top of `__nonzero__` reduces the time to 70us. The culprit is the testing of `x^2 + 1`.
videlec commented 6 years ago
comment:4

The code should never test whether x^2 + 1 is zero as a symbolic expression. I don't understand the trace that you obtain.

videlec commented 6 years ago
comment:5

I mean 3 x^2 + 1 <type 'sage.symbolic.expression.Expression'> and 4 x^2 + 1 <type 'sage.symbolic.expression.Expression'> should not be there.

videlec commented 6 years ago
comment:6

In other words

sage: p = SR['x'](polygen(ZZ, 'x'))
sage: p.degree()
0

should be

sage: p = SR['x'](polygen(ZZ, 'x'))
sage: p.degree()
1

Nobody cares whether it is slow or not. It is just wrong.

rwst commented 6 years ago
comment:7

Replying to @videlec:

Nobody cares whether it is slow or not. It is just wrong.

So I thought earlier in #24942 comment:12, and now it turns out it's the reason for slowness. Changing the description.

rwst commented 6 years ago

Description changed:

--- 
+++ 
@@ -1,36 +1,9 @@
-This branch shows that the generic polynomial code is not aware of the symbolic zero problem. On Sage develop, the operation

-sage: p = polygen(ZZ)^2 + 1 -sage: %timeit p.change_ring(SR) -1000 loops, best of 3: 322 µs per loop -sage: %timeit p.change_ring(RR) -100000 loops, best of 3: 12.9 µs per loop +sage: p = (polygen(ZZ)^2 + 1).change_ring(SR) +sage: p.constantcoefficient() +x^2 + 1 +sage: type() +<type 'sage.symbolic.expression.Expression'>

-takes much longer with SR because `Expression.__nonzero__` is ultimately called. For the problems with this, see https://trac.sagemath.org/wiki/symbolics/nonzero

-The branch adds 5 print statements before the calls to `__nonzero__` are made. The output is:
-
-```
-sage: p = polygen(ZZ)^2 + 1
-sage: p.change_ring(SR)
-0 Symbolic Ring
-1 1 [0, 1]
-2 1 Symbolic Ring
-3 x^2 + 1 <type 'sage.symbolic.expression.Expression'>
-2 x^2 + 1 Symbolic Ring
-4 x^2 + 1 <type 'sage.symbolic.expression.Expression'>
-2 x^2 + 1 Symbolic Ring
-x^2 + 1
-```
-One can see
-- SR is tested for zero once;
-- the coefficients are tested once;
-- twice `x^2 + 1` is tested for zero. Note that `x^2 + 1` is the zeroth coefficient, not the polynomial itself.
-- three times `__nonzero__` calls itself at point 2.
-
-Inserting `return False` at the top of `__nonzero__` reduces the time to 70us. The culprit is the testing of `x^2 + 1`.
-
-One easy solution that does not require the interface change outlined in https://trac.sagemath.org/wiki/symbolics/nonzero would be implementing #21201.
-
-This branch should then be replaced with an improvement in the places marked.
rwst commented 6 years ago

Changed commit from 05708a2 to none

rwst commented 6 years ago

Changed branch from u/rws/symboliczero001 to none

videlec commented 6 years ago
comment:8

And note that I already explicitely said what needs to be done to fix this in #24942 comment:13

rwst commented 6 years ago
comment:9

Fact is that PolynomialRing_general._element_constructor is not called at all here.

videlec commented 6 years ago
comment:10

This is completely broken because of

sage: SR.has_coerce_map_from(ZZ['x'])
True

As a consequence of the above, the conversion ZZ[x] -> SR['x'] goes through the base ring SR of the codomain.

videlec commented 6 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,10 @@
+Because of
+
+```
+sage: SR.has_coerce_map_from(ZZ['x'])
+True
+```
+the conversion `ZZ['x'] -> SR['x']` goes through the base ring. As a consequence integral polynomials are badly converted into symbolic polynomials

sage: p = (polygen(ZZ)^2 + 1).changering(SR) @@ -6,4 +13,3 @@ sage: type() <type 'sage.symbolic.expression.Expression'>

-
videlec commented 6 years ago

Description changed:

--- 
+++ 
@@ -13,3 +13,12 @@
 sage: type(_)
 <type 'sage.symbolic.expression.Expression'>

+ +We disallow the map ZZ['x'] -> SR as a coercion (but keep it as a conversion). This might not be desirable as the following would not be symbolic expressions anymore (but polynomials) + + +sage: SR('x') * polygen(ZZ) +x^2 +sage: SR('x') * polygen(ZZ, 'y') +x*y +

videlec commented 6 years ago

Description changed:

--- 
+++ 
@@ -14,7 +14,7 @@
 <type 'sage.symbolic.expression.Expression'>

-We disallow the map ZZ['x'] -> SR as a coercion (but keep it as a conversion). This might not be desirable as the following would not be symbolic expressions anymore (but polynomials) +We disallow the map ZZ['x'] -> SR as a coercion (but keep it as a conversion). This might not be desirable as the following would not be symbolic expressions anymore (but polynomials in SR['x'])

 sage: SR('x') * polygen(ZZ)
videlec commented 6 years ago
comment:14

The code of SR._coerce_map_from_ is so nice

elif is_PolynomialRing(R) or is_MPolynomialRing(R) or \
     is_FractionField(R) or is_LaurentPolynomialRing(R):
    base = R.base_ring()
    return base is not self and self.has_coerce_map_from(base)
videlec commented 6 years ago

Description changed:

--- 
+++ 
@@ -14,11 +14,26 @@
 <type 'sage.symbolic.expression.Expression'>

-We disallow the map ZZ['x'] -> SR as a coercion (but keep it as a conversion). This might not be desirable as the following would not be symbolic expressions anymore (but polynomials in SR['x']) +We disallow the map ZZ['x'] -> SR as a coercion (but keep it as a conversion). This might not be desirable as the following behavior would not be preserved + +- SR('x') * polygen(ZZ) would become a polynomial in SR['x'] (with coefficient x) (and not anymore the expression x^2) +- substitutions with polynomial values will not be possible anymore. The following example

-sage: SR('x') * polygen(ZZ)
-x^2
-sage: SR('x') * polygen(ZZ, 'y')
-x*y
+sage: x = SR.var('x')
+sage: R.<y0, y1> = ZZ[]
+sage: x.subs(x=y0/y1)
+y0/y1
videlec commented 6 years ago

Description changed:

--- 
+++ 
@@ -14,7 +14,7 @@
 <type 'sage.symbolic.expression.Expression'>

-We disallow the map ZZ['x'] -> SR as a coercion (but keep it as a conversion). This might not be desirable as the following behavior would not be preserved +One option would be to disallow the coercion ZZ['x'] -> SR (but keeping the conversion). Such change is highly non-backward compatible

videlec commented 6 years ago

Description changed:

--- 
+++ 
@@ -4,7 +4,7 @@
 sage: SR.has_coerce_map_from(ZZ['x'])
 True

-the conversion ZZ['x'] -> SR['x'] goes through the base ring. As a consequence integral polynomials are badly converted into symbolic polynomials +the conversion ZZ['x'] -> SR['x'] goes through the base ring. As a consequence integral polynomials are badly converted into symbolic polynomials (and not into polynomial with symbolic coefficients)

 sage: p = (polygen(ZZ)^2 + 1).change_ring(SR)
@@ -14,7 +14,7 @@
 <type 'sage.symbolic.expression.Expression'>

-One option would be to disallow the coercion ZZ['x'] -> SR (but keeping the conversion). Such change is highly non-backward compatible +One option would be to disallow the coercion ZZ['x'] -> SR (but keeping the conversion). Such change is non-backward compatible because of the two following use cases

videlec commented 6 years ago
comment:18

Here you have to choose:

rwst commented 6 years ago
comment:19

The first sounds correct. But the fix is over my head, I have no idea about how to fix this.

nbruin commented 6 years ago
comment:20

It looks like the degree 0 result is consistent with how name ambiguities are resolved elsewhere:

sage: f=QQ['x']['x'](QQ['x'].0)
sage: f.degree()
0

There is an x in SR, SR is supposed to be a ring, so ZZ coerces into it. As a result, ZZ['x'] coerces into it as well. Furthermore, that means that ZZ['x'] coerces as constants into SR['x'].

videlec commented 6 years ago
comment:21

Then you are free to clarify the description and set to "won't fix".

videlec commented 6 years ago
comment:22

Or better: to document and test this feature in the SR documentation!