cleaning and enhancement to PolyDict

[videlec]

We provide some cleaning and speed up to the PolyDict class by always enforcing keys to be ETuple (some parts of the code did assume that was the case). As a consequence we deprecate the usage of the constructor arguments force_int_exponents and force_etuples.

We also simplify the design by getting rid of PolyDict.__zero (and hence deprecating the argument zero of the PolyDict constructor).

Along the way, we fix

sage: R = ZZ['x']['y,z']
sage: y, z = R.gens()
sage: y.integral(y)
1/2*y^2
sage: parent(y.integral(y))
Multivariate Polynomial Ring in y, z over Univariate Polynomial Ring in x over Integer Ring

and

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([0, 1, 0])
sage: e.eadd_p(0, 0).nonzero_positions()
[0, 1]

CC: @xcaruso @mezzarobba @saraedum

Component: algebra

Author: Vincent Delecroix

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

[videlec]

Description changed:

--- 
+++ 
@@ -1 +1,14 @@
+We provide some cleaning and speed up to the `PolyDict` class by always enforcing keys to be `ETuple` (some parts of the code did assume that was the case). As a consequence we deprecate the usage of the constructor arguments `force_int_exponents` and `force_etuples`.

+We also simplify the design by getting rid of `PolyDict.__zero` (and hence deprecating the argument `zero` of the `PolyDict` constructor).
+
+Along the way, we fix
+
+```
+sage: R = ZZ['x']['y,z']
+sage: y, z = R.gens()
+sage: y.integral(y)
+1/2*y^2
+sage: parent(y.integral(y))
+Multivariate Polynomial Ring in y, z over Univariate Polynomial Ring in x over Integer Ring
+```

[videlec]

Branch: u/vdelecroix/34000

[videlec]

Commit: e48d741

[videlec]

New commits:

7deaa24	34000: cleaning and enhancement to polydict
e48d741	34000: remove PolyDict.__pow__

[mezzarobba]

comment:3

Two things that I did not understand while skimming through the code:

• in MPolynomial_polydict.integral(), why do you have two different code paths for determining the result's parent?
• what do the RuntimeErrors now raised by PolyDict on various occasions correspond to?

[videlec]

comment:4

Replying to @mezzarobba:

Two things that I did not understand while skimming through the code:

Thanks for having a look.

• in MPolynomial_polydict.integral(), why do you have two different code paths for determining the result's parent?

I shamefully copied the code from univariate polynomials, see polynomial_element.pyx#L3980-L3985

• what do the RuntimeErrors now raised by PolyDict on various occasions correspond to?

One of them is ensuring that keys are ETuple. All others are here because I also made uniform that no coefficient is zero. At least, it did not break any test.

[mezzarobba]

comment:5

Replying to @videlec:

• what do the RuntimeErrors now raised by PolyDict on various occasions correspond to?

One of them is ensuring that keys are ETuple. All others are here because I also made uniform that no coefficient is zero. At least, it did not break any test.

Sorry, my question was not clear. I was mostly wondering why you were raising RuntimeErrors rather than ValueErrors/TypeErrors/... (if the purpose was argument checking) or using assertions (if you wanted to guard against things that should never happen).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

6eac6b0	34000: cleaner optimization in derivative/integral
065d42e	34000: clarify RuntimeError
48413be	34000: two little optimizations

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e48d741 to 48413be

[videlec]

comment:7

Replying to @mezzarobba:

Replying to @videlec:

• what do the RuntimeErrors now raised by PolyDict on various occasions correspond to?

One of them is ensuring that keys are ETuple. All others are here because I also made uniform that no coefficient is zero. At least, it did not break any test.

Sorry, my question was not clear. I was mostly wondering why you were raising RuntimeErrors rather than ValueErrors/TypeErrors/... (if the purpose was argument checking) or using assertions (if you wanted to guard against things that should never happen).

It is really a RuntimeError : it is assumed that keys are ETuple and coefficients are nonzero.

[videlec]

comment:8

I hope I clarified the code related to your comments in ​6eac6b0 and 065d42e.

[videlec]

comment:9

Let me change RuntimeError for assertions.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

f6c6893

34000: replace RuntimeError with assertion

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 48413be to f6c6893

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f6c6893 to 3341a98

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

3341a98

34000: fix Polydict.homogenize and ETuple.eadd_p

[videlec]

Description changed:

--- 
+++ 
@@ -12,3 +12,11 @@
 sage: parent(y.integral(y))
 Multivariate Polynomial Ring in y, z over Univariate Polynomial Ring in x over Integer Ring

+and + + +sage: from sage.rings.polynomial.polydict import ETuple +sage: e = ETuple([0, 1, 0]) +sage: e.eadd_p(0, 0).nonzero_positions() +[0, 1] +

[videlec]

comment:12

In the last commit I fixed a bug in eadd_p and optimized homogenize in order to fix a bug that show up in doctests from sage.schemes.elliptic_curve.constructor.

---

New commits:

3341a98

34000: fix Polydict.homogenize and ETuple.eadd_p

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3341a98 to 0b0e48c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

0b0e48c

34000: fix zero coefficient in PolyDict.homogenize

[videlec]

comment:14

sage -t --long src/sage/rings/tate_algebra_element.pyx  # 5 doctests failed
sage -t --long src/sage/rings/tate_algebra_ideal.pyx  # 3 doctests failed
sage -t --long src/sage/rings/polynomial/multi_polynomial.pyx  # 1 doctest failed

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

fae4a25

34000: make a copy of input in PolyDict.__init__

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0b0e48c to fae4a25

[videlec]

comment:16

@Xavier Caruso: now that I made systematic zero coefficient removal in polydict.pyx I have trouble with Tate algebras. Namely, it seems that you always want to keep zeros there even though there is no natural way we can make difference between exact and inexact zero in the base ring

sage: R = Zp(2, print_mode='digits', prec=10)
sage: R(0, 5).is_zero()
True
sage: R(0, 5) == R(0)
True
sage: not (R(0, 5) != R(0))
True

This affects code such as

sage: R = Zp(2, print_mode='digits', prec=10)
sage: A.<x,y> = TateAlgebra(R)
sage: f = 1 + 64*x
sage: f -= R(1, 5)
sage: f
...00000 + ...0000000001000000*x

which now returns ...0000000001000000*x.

On the other hand, I believe that the code in Tate algebra is buggy for the following reason. The conversion R -> A does not commute with binary operations

sage: R = Zp(2, print_mode='digits', prec=10)
sage: A.<x,y> = TateAlgebra(R)
sage: A(R(1)) - A(R(1,5))
...00000
sage: A(R(1) - R(1,5))
0

The following is also broken

sage: A({(1,1): R(0,5)})
0

(it should have been R(0,5)*x*y which prints as ...00000*x*y)

The main question is : how do we test whether an element is exactly zero in R ? r.precision_absolute() == infinity and r.is_zero()? I could introduce an attribute zero_test in PolyDict to make this check consistently.

[videlec]

comment:17

For the same reason as in comment:16 multivariate polynomials over p-adics are similarly broken in the current sage

sage: R = Zp(2)
sage: Rxy.<x,y> = R[]
sage: Rxy(R(0,5))
0
sage: x - x
0

[videlec]

comment:18

Replying to @videlec:

For the same reason as in comment:16 multivariate polynomials over p-adics are similarly broken in the current sage

sage: R = Zp(2)
sage: Rxy.<x,y> = R[]
sage: Rxy(R(0,5))
0
sage: x - x
0

hmm as well as multivariate polynomial rings over power series

sage: R.<x> = PowerSeriesRing(QQ)
sage: A.<y,z> = R[]
sage: O(x^3) * y
0

[xcaruso]

comment:19

Replying to @videlec:

The main question is : how do we test whether an element is exactly zero in R ? r.precision_absolute() == infinity and r.is_zero()? I could introduce an attribute zero_test in PolyDict to make this check consistently.

I think you can use the method _is_exact_zero for padics.

I'll have a look at the bug in coercion from base ring to Tate algebra you noticed.

[videlec]

comment:20

Replying to @xcaruso:

Replying to @videlec:

The main question is : how do we test whether an element is exactly zero in R ? r.precision_absolute() == infinity and r.is_zero()? I could introduce an attribute zero_test in PolyDict to make this check consistently.

I think you can use the method _is_exact_zero for padics.

Thanks. Though very specific to p-adics. And it does not exist for power series.

I'll have a look at the bug in coercion from base ring to Tate algebra you noticed.

It is not a bug in the coercion system. It is the way elements of the Tate algebra are constructed. The PolyDict class does a cleaning of zero coefficients in its input.

[videlec]

comment:21

As far as this ticket is concerned there is an easy way out : leave simplification of zero coefficients in PolyDict to the user (via the PolyDict.remove_zeros method). This will solve the construction issues with Tate algebra.

I opened ticket #34024 to fix polynomials.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

680f8e0

34000: do not simplify zero coefficients in PolyDict

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from fae4a25 to 680f8e0

[videlec]

comment:23

@Xavier Caruso Even with comment:21 implemented I got the following failure

sage -t --random-seed=31078045756822634162710736872151007113 tate_algebra_ideal.pyx
**********************************************************************
File "tate_algebra_ideal.pyx", line 857, in sage.rings.tate_algebra_ideal.groebner_basis_pote
Failed example:
    I.groebner_basis(algorithm="PoTe", prec=100)  # indirect doctest
Expected:
    [...0000000001*x^3 + ...2222222222*y + ...000000000*x^2*y^2 + O(3^99 * <x, y>),
     ...0000000001*x^2*y + ...01210121020 + O(3^100 * <x, y>),
     ...0000000001*y^2 + ...01210121020*x + ...000000000*x^2*y^3 + ...0000000000*x^3*y + O(3^99 * <x, y>)]
Got:
    [...0000000001*x^3 + ...2222222222*y + ...000000000*x^2*y^2 + O(3^99 * <x, y>),
     ...0000000001*x^2*y + ...01210121020 + O(3^100 * <x, y>),
     ...0000000001*y^2 + ...01210121020*x + ...0000000000*x^3*y + O(3^99 * <x, y>)]
**********************************************************************
File "tate_algebra_ideal.pyx", line 1104, in sage.rings.tate_algebra_ideal.groebner_basis_vapote
Failed example:
    I.groebner_basis(algorithm="VaPoTe", prec=100)  # indirect doctest
Expected:
    [...0000000001*x^3 + ...2222222222*y + ...000000000*x^2*y^2 + O(3^99 * <x, y>),
     ...0000000001*x^2*y + ...01210121020 + O(3^100 * <x, y>),
     ...0000000001*y^2 + ...01210121020*x + ...000000000*x^2*y^3 + ...0000000000*x^3*y + O(3^99 * <x, y>)]
Got:
    [...0000000001*x^3 + ...2222222222*y + ...000000000*x^2*y^2 + O(3^99 * <x, y>),
     ...0000000001*x^2*y + ...01210121020 + O(3^100 * <x, y>),
     ...0000000001*y^2 + ...01210121020*x + ...0000000000*x^3*y + O(3^99 * <x, y>)]
**********************************************************************
2 items had failures:
   1 of   9 in sage.rings.tate_algebra_ideal.groebner_basis_pote
   1 of  10 in sage.rings.tate_algebra_ideal.groebner_basis_vapote
    [126 tests, 2 failures, 3.46 s]

Also, it did not magically fix comment:16 since Tate algebras use multivariate polynomials over p-adic rings...

[xcaruso]

comment:24

Replying to @videlec:

@Xavier Caruso Even with comment:21 implemented I got the following failure

Hmm. Difficult to say what is the correct answer. I'll try to investigate this more but maybe, the easiest fix is to change the doctest.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

54bacfb	34000: clarify RuntimeError
1f08c97	34000: two little optimizations
e597bd7	34000: replace RuntimeError with assertion
b6eb9e5	34000: fix Polydict.homogenize and ETuple.eadd_p
5966dc3	34000: fix zero coefficient in PolyDict.homogenize
0c026ec	34000: make a copy of input in PolyDict.__init__
5e0aa5c	34000: do not simplify zero coefficients in PolyDict
49e78f9	34000: fix doctest in multi_polynomial.pyx
a19ca7c	34000: change tate algebras doctests
52c5a25	34000: doc details

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 680f8e0 to 52c5a25

[videlec]

comment:26

rebased on 9.7.beta8 and failing doctests modified

[videlec]

comment:27

green bot

[tscrim]

comment:28

I think some timings are needed here before a positive review to see what sort of speed regressions we incur because we no longer have the option to turn off certain features and checks.

Why is addition the only operation that gets a special in-place operation? I think it would be good to make this universal.

It is generally not a good ideal to check if type(e) is not ETuple:. I understand this is faster than isinstance(e, ETuple), but it is less future-proof if someone subclasses ETuple.

Naively coverage seems to have decreased; e.g., __len__ no longer has documentation. It is a bit of a misdirect that the coverage has increased as it is just total percentage.

[mkoeppe]

Removed branch from issue description; replaced by PR #35020

[vneiger]

Just for reference, I want to point out that PR #35174 also seems to fix another bug with eadd_p (in addition, but likely related, to the one mentioned in the initial description of this issue). With the current version 10.0.beta3, the following makes SageMath crash with memory issues such as invalid pointer, invalid next size, ... : ETuple([0,1,1]).eadd_p(1,0) .

The problem seems independent of the nonzero values (the 1's) and seems to persist in lengths 4 and more. E.g. ETuple([0,2,4,3]).eadd_p(5,0) crashes as well, but ETuple([0,2]).eadd_p(5,0) will not crash.

With PR #35174 , and I suppose thanks to this commit , this issues appears to have been solved.

[videlec]

Indeed, the nonzero_values is merely here to check consistency of the data. The crash does not systematically happen as the accessed memory might be in the allowed zone.