cleaning and enhancement to PolyDict #34000

videlec · 2022-06-16T09:04:15Z

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

The text was updated successfully, but these errors were encountered:

videlec · 2022-06-16T16:28:00Z

Branch: u/vdelecroix/34000

videlec · 2022-06-16T16:28:00Z

Commit: e48d741

videlec · 2022-06-16T16:28:00Z

New commits:

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

mezzarobba · 2022-06-18T07:54:01Z

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 · 2022-06-18T12:31:10Z

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 · 2022-06-18T18:30:34Z

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).

sagetrac-git · 2022-06-18T19:28:51Z

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`

sagetrac-git · 2022-06-18T19:28:51Z

Changed commit from e48d741 to 48413be

videlec · 2022-06-18T19:29:31Z

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 · 2022-06-18T19:30:31Z

comment:8

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

videlec · 2022-06-18T19:39:02Z

comment:9

Let me change RuntimeError for assertions.

sagetrac-git · 2022-06-18T19:44:39Z

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

`f6c6893`	`34000: replace RuntimeError with assertion`

sagetrac-git · 2022-06-18T19:44:39Z

Changed commit from 48413be to f6c6893

sagetrac-git · 2022-06-19T08:53:35Z

Changed commit from f6c6893 to 3341a98

sagetrac-git · 2022-06-19T08:53:35Z

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

`3341a98`	`34000: fix Polydict.homogenize and ETuple.eadd_p`

videlec · 2022-06-19T08:55:37Z

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`

sagetrac-git · 2022-06-19T09:50:21Z

Changed commit from 3341a98 to 0b0e48c

sagetrac-git · 2022-06-19T09:50:21Z

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

`0b0e48c`	`34000: fix zero coefficient in PolyDict.homogenize`

videlec · 2022-06-19T12:32:26Z

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

sagetrac-git · 2022-06-19T13:31:59Z

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

`fae4a25`	`34000: make a copy of input in PolyDict.__init__`

sagetrac-git · 2022-06-19T13:31:59Z

Changed commit from 0b0e48c to fae4a25

videlec · 2022-06-19T13:44:25Z

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 · 2022-06-19T18:07:08Z

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 · 2022-06-19T18:16:44Z

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 · 2022-06-19T18:31:34Z

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 · 2022-06-19T18:38:24Z

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 · 2022-06-19T18:44:26Z

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.

sagetrac-git · 2022-06-19T19:32:35Z

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

`680f8e0`	`34000: do not simplify zero coefficients in PolyDict`

sagetrac-git · 2022-06-19T19:32:35Z

Changed commit from fae4a25 to 680f8e0

videlec · 2022-06-19T19:34:52Z

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 · 2022-06-20T08:08:47Z

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.

sagetrac-git · 2022-08-12T16:01:49Z

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`

sagetrac-git · 2022-08-12T16:01:49Z

Changed commit from 680f8e0 to 52c5a25

videlec · 2022-08-12T16:02:41Z

comment:26

rebased on 9.7.beta8 and failing doctests modified

videlec · 2022-08-13T06:41:05Z

comment:27

green bot

tscrim · 2022-08-16T06:16:33Z

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 · 2023-02-13T01:59:22Z

Removed branch from issue description; replaced by PR #35020

vneiger · 2023-03-10T17:03:14Z

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 · 2023-03-18T20:38:58Z

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.

### 📚 Description Fixes #34000 (and more complete version of the proposition at #35020). A discussion about the general problem of inexact zeros has been opened at #35319 ### 📝 Checklist    - [x] I have made sure that the title is self-explanatory and the description concisely explains the PR. - [x] I have linked an issue or discussion. - [x] I have created tests covering the changes. - [x] I have updated the documentation accordingly. URL: #35174 Reported by: Vincent Delecroix Reviewer(s): Frédéric Chapoton, Travis Scrimshaw, Vincent Delecroix

videlec added this to the sage-9.7 milestone Jun 16, 2022

videlec added c: algebra labels Jun 16, 2022

This comment has been minimized.

Sign in to view

videlec added the s: needs review label Jun 16, 2022

This comment has been minimized.

Sign in to view

videlec added s: needs work and removed s: needs review labels Jun 19, 2022

videlec added s: needs review and removed s: needs work labels Aug 12, 2022

mkoeppe modified the milestones: sage-9.7, sage-9.8 Sep 19, 2022

mkoeppe removed this from the sage-9.8 milestone Jan 29, 2023

videlec mentioned this issue Jan 29, 2023

Polynomials over p-adics and power series are wrong #34024

Open

fchapoton mentioned this issue Feb 8, 2023

cleaning and enhancement to PolyDict #34000 #35020

Closed

3 tasks

mkoeppe removed the s: needs review label Feb 13, 2023

videlec mentioned this issue Feb 22, 2023

cleaning and enhancement to PolyDict #35174

Merged

4 tasks

vbraun closed this as completed in #35174 Mar 26, 2023

cleaning and enhancement to PolyDict #34000

cleaning and enhancement to PolyDict #34000

Comments

videlec commented Jun 16, 2022 • edited by mkoeppe

This comment has been minimized.

videlec commented Jun 16, 2022

videlec commented Jun 16, 2022

videlec commented Jun 16, 2022

mezzarobba commented Jun 18, 2022

videlec commented Jun 18, 2022

mezzarobba commented Jun 18, 2022

sagetrac-git mannequin commented Jun 18, 2022

sagetrac-git mannequin commented Jun 18, 2022

videlec commented Jun 18, 2022

videlec commented Jun 18, 2022

videlec commented Jun 18, 2022

sagetrac-git mannequin commented Jun 18, 2022

sagetrac-git mannequin commented Jun 18, 2022

sagetrac-git mannequin commented Jun 19, 2022

sagetrac-git mannequin commented Jun 19, 2022

This comment has been minimized.

videlec commented Jun 19, 2022

sagetrac-git mannequin commented Jun 19, 2022

sagetrac-git mannequin commented Jun 19, 2022

videlec commented Jun 19, 2022

sagetrac-git mannequin commented Jun 19, 2022

sagetrac-git mannequin commented Jun 19, 2022

videlec commented Jun 19, 2022

videlec commented Jun 19, 2022

videlec commented Jun 19, 2022

xcaruso commented Jun 19, 2022

videlec commented Jun 19, 2022

videlec commented Jun 19, 2022

sagetrac-git mannequin commented Jun 19, 2022

sagetrac-git mannequin commented Jun 19, 2022

videlec commented Jun 19, 2022

xcaruso commented Jun 20, 2022

sagetrac-git mannequin commented Aug 12, 2022

sagetrac-git mannequin commented Aug 12, 2022

videlec commented Aug 12, 2022

videlec commented Aug 13, 2022

tscrim commented Aug 16, 2022

mkoeppe commented Feb 13, 2023

vneiger commented Mar 10, 2023

videlec commented Mar 18, 2023

videlec commented Jun 16, 2022 •

edited by mkoeppe