bugs in infinite polynomial ring

[williamstein]

1. Here's one, from a fresh session in sage-4.3.alpha0:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: x[2^31]
Traceback (most recent 
...
OverflowError: range() result has too many items
sage: x[100]
TypeError: ...

Why do we get a TypeError doing x[100] after the overflow error?

2. Here's another bug, probably the result of using string parsing (?), but I'm not sure:

sage: X.<a,b> = InfinitePolynomialRing(QQ)
sage: a[100]
a100
sage: a[2/3]
1/3*a2

then the following weird error.

sage: a[Mod(2,3)]
Traceback (most recent ...)
...
TypeError: reduce() of empty sequence with no initial value

which is made weirder because the same input again suddenly works!

sage: a[Mod(2,3)]
a2

Here's one that is weird, due to not validating input before passing it off to the libsingular coercion function:

sage: X.<a,b> = InfinitePolynomialRing(QQ)
sage: a[0]
a0
sage: a['0+5']
a0 + 5
sage: a['0+5^2']
a0 + 25

It's also really weird that the variable names have to be a single letter and that the base ring has to be a field. Why?:

sage: X.<alpha,beta>= InfinitePolynomialRing(QQ)
Traceback (most recent call last):
ValueError: variable names must be of length 1

sage: X.<x,y> = InfinitePolynomialRing(ZZ)
Traceback (most recent call last):
TypeError: The base ring (= Integer Ring) must be a field

CC: @mwhansen @nathanncohen @nthiery

Component: algebra

Keywords: infinite polynomial ring coercion

Author: Simon King

Reviewer: John Cremona

Merged: sage-4.3.3.alpha0

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

[simon-king-jena]

comment:1

I am glad to see in various posts on sage-devel and sage-support that finally people are using Infinite Polynomial Rings. They are using it in a way that I did not think of when I worked on the code (but perhaps Mike Hansen had this in mind? After all, it started with his implementation).

The fact that people seem not to use it for Symmetric Groebner Bases implies two things:

• The current default implementation (which goes back to Mike Hansen) is good for Symmetric Groebner Bases, but not so good for other applications. So, should we change the default?

• The new usage reveals a couple of bugs, that should be fixed.

My impression is that the code needs a thorough overhaul. Can we use this ticket for it?

[simon-king-jena]

comment:2

Here some words on the requirement that variable names must be single letters.

The generators x,y,... of an Infinite Polynomial Ring R are, mathematically, generators of R as a free module over the group algebra of the symmetric group G of the natural numbers (starting with 1, while 0 is fixed).

A variable in R can be thought of as a pair (x,n), where x is a generator of R and n is a natural number. G acts on the pair by acting on n. In a text book, one would write it x_n. In the implementation, such variable x_n is returned by x[n]. We refer to n as the "index" of x[n].

It has an underlying "classical" polynomial x[n]._p. The question is: To what classical polynomial ring should x[n]._p belong?

• The dense implementation (due to Mike Hansen) is: x[n]._p belongs to the ring with variables x0,x1,...,x{n},y0,y1,...,y{n}.

• The sparse implementation (my starting point) is: x[n]._p belongs to the ring with variable x{n}.

Of course, when doing algebraic operations in the sparse implementation, the underlying polynomial ring must be extended. In the dense implementation, this is only needed when G acts, or if one does a conversion, say, of a string 'x10000+2*y100001' into R.

But that's the point: How can I find the maximal index of Infinite Polynomials when doing arithmetic, G-action or conversion? Note that by arithmetic operations the terms of maximal index may cancel, so, it is not easily possible to infer the maximal index of a sum, given the maximal indices of a summand. And how should one find out the maximal index in a given string?

I thought that an easy solution is to infer the maximal index from a string representation of the underlying classical polynomial q._p, if q is an Infinite Polynomial. This is one place where regular expressions occur. In order to simplify the regular expressions, generator names should be as simple as possible.

There is another point. I wanted to implement Aschenbrenner's and Hillar's algorithm for finding Symmetric Groebner Bases. This requires a monomial ordering on R. Of course, I am using monomial orderings of the underlying classical polynomial rings.

But this means: If I construct the parent of q._p (again, q an Infinite Polynomial) then I must order the occurring variables. Usually, the variable names have to be sorted, first, by the name of the generator and, secondly, by the index. Again, I sought to do this operation as quick and easy as possible.

And these are the reasons why I imposed the name restriction:

1. The name of the variable name should allow (for a human) to infer the name of the generator and the index. So, it should be something like var_name = str(generator_name)+str(index) or var_name = str(generator_name)+'_'+str(index).

2. For the computer, it should be easy and fast to determine generator name and index from the variable name. This is why I ask to have a single letter for the generator name, so that one has generator_name, index = var_name[0], int(var_name[1:].

But what about just requiring that generator_name must not contain "". Then, one could say var_name = str(generator_name)+''+str(index), and process var_name by split('_'). How much slower would this be? Apparently 50%:

sage: f = lambda x,y: (x,int(y))
sage: s = 'x_1234'
sage: timeit("a,b = f(*s.split('_',1))")
625 loops, best of 3: 1.73 µs per loop
sage: timeit("a,b = s[0],int(s[2:])")
625 loops, best of 3: 1.11 µs per loop

Actually the approach using "" has one benefit: Suppose one is given the string representation of the underlying polynomial and wants to determine the maximal index. This can be found using a simple regular expression, since a sequence of digits defines an index if and only if it is preceded by "". Thus:

sage: import re
sage: P = re.compile('_[0123456789]+')  # this will be done only once
sage: s = '1000000*alpha_1234*beta_4321^1223923923+gamma_234*delta_1'
sage: max([int(x[1:]) for x in P.findall(s)])
4321

So, in the end of the day, using "_" could be faster.

Would it be OK to say "generator names must be alphanumeric and must not contain underscore"?

[simon-king-jena]

comment:3

Here is one example why I chose to use regular expressions.

Often I have to find out what variables (i.e., generator and shift) occur in what power in the leading monomial of a polynomial. So:

# Create a polynomial ring
# (the typical underlying finite polynomial ring of a densely
#  implemented InfinitePolynomialRing)
sage: Vars = ['x_'+str(n) for n in range(50)]+['y'+str(n) for n in range(50)]
sage: R = PolynomialRing(QQ,Vars)
# Create a big random element
sage: p = R.random_element()
sage: p *= R.random_element()
sage: p *= R.random_element()
sage: p *= R.random_element()
sage: p *= R.random_element() 

The generic approach to get the exponents of the variables in the leading monomial is, of course, the method exponents(). We need to associate the exponent with the variable, so, let's zip two lists:

sage: zip(Vars,p.lm().exponents()[0])
[('x_0', 0),
 ('x_1', 2),
 ('x_2', 0),
 ('x_3', 0),
 ('x_4', 0),
 ('x_5', 0),
 ('x_6', 0),
... 

It is a long list, and we still did not separate the generator name from the shift.

Now, do essentially the same with regular expressions:

sage: import re
sage: RE = re.compile('([a-zA-Z0-9]+)_([0-9]+)\^?([0-9]*)')
sage: RE.findall(str(p.lm()))
[('x', '1', '2'),
 ('x', '13', '2'),
 ('x', '16', ''),
 ('x', '23', ''),
 ('x', '45', '')] 

The list is much shorter, and moreover generator names and shifts are already told apart. This is actually the typical situation for elements of Infinite Polynomial Rings in dense implementation: Only few variables from the underlying finite polynomial ring appear in the leading monomial.

And I guess this is why the regular expression is faster:

sage: timeit('L = RE.findall(str(p.lm()))')
625 loops, best of 3: 23.8 µs per loop
sage: timeit('L = zip(Vars,p.lm().exponents()[0])')
625 loops, best of 3: 40.5 µs per loop 

IIRC, in a very early stage of my implementation, I did use exponents(). But it soon turned out that it was too slow for Gröbner basis computations.

[simon-king-jena]

comment:4

I am now going through the bugs that you reported:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: x[2^31]
Traceback (most recent 
...
OverflowError: range() result has too many items
sage: x[100]
TypeError: ...

I found the reason: There is one attribute of X that is changed even when x[2^31] fails. When subsequently calling x[100], that attribute makes the sytem believe that the underlying polyomial ring is big enough to fit x100 --- which is not the case.

My plan is to go through the whole code before posting a patch. I hope that's fine.

[simon-king-jena]

comment:5

Concerning the erroneous result of a[2/3] or a['0+5']: It is correct that it comes from the use of strings. I am now explicitely converting the argument to an integer. It is silly that I forgot it in the original implementation. This also fixes the a[Mod(2,3)] bug.

I meanwhile have code that allows for any alphanumeric variable names. Only requirement: isalnum() must return True (in particular, there must be no underscore in the name, as I have explained above). I am now testing the new code and will hopefully soon be able to post it.

The reason for requiring a base field: It is needed for my original application, Symmetric Gröbner Bases. But as people now want other applications, it seems fair to allow any base ring that is also allowed for classical polynomial rings. So, the exception should only be raised in the groebner_basis method of symmetric ideals.

[simon-king-jena]

comment:6

Hi!

I implemented what I suggested above and fixed the reported bugs, but I found that changing the new variable naming scheme (x_10 rather than x10) would break some doc tests of sage/numerical/mip.pyx.

But if I remember correctly, Nathann was considering to remove the use of Infinite Polynomial Rings from mip.pyx. What is the status? Is there a ticket for it? Then the two tickets should be somehow coordinated.

Does this mean "status needs-info"? I guess so...

Cheers,
Simon

[nathanncohen]

comment:7

Here it is !! Perhaps you do not need fixing the docstrings in class mip as they should be changed by this patch soon :

#7561

I'm mainly waiting for a answer from Martin and this ticket should be settled :-)

Nathann

[simon-king-jena]

comment:8

Replying to @nathanncohen:

Here it is !! Perhaps you do not need fixing the docstrings in class mip as they should be changed by this patch soon :

#7561

I'm mainly waiting for a answer from Martin and this ticket should be settled :-)

Thanks for the info!

I hope I will be able to post a patch today, without changing the mip.pyx doc tests.

[simon-king-jena]

comment:9

While I started to comment my patch, I found that not all issues are resolved. For example, I can define an infinite polynomial ring whose base ring is another infinite polynomial ring -- but the computations with elements of such ring don't quite work yet.

Sorry.

Later, I'll provide another patch that fixes it.

[simon-king-jena]

Changed keywords from none to infinite polynomial ring coercion

[simon-king-jena]

comment:10

Hi!

Cc to Nicolas, since it partially concerns categories/functors.

We proudly present a major revision of Infinite Polynomial Rings; the patch bomb is relative to sage-4.3.alpha1.

First of all, it fixes the bugs that William stated in the ticket description.

Second, it is now possible to use any commutative base ring; the restriction of using fields is now moved to the groebner_basis() method.

Third, and that's the biggest change: It now uses the strength of Sage's coercion machinery in pushout.py. I hope I did not overdo my use of it...

Bug fixes

Answer to William's failing examples:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: x[2^31]
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
...
IndexError: Variable index is too big - consider using the sparse implementation

I think that error message is clearer, and it gives a good advice...

sage: x[100]
x_100

So, that bug is gone.

sage: X.<a,b> = InfinitePolynomialRing(QQ)
sage: a[100]
a_100
sage: a[2/3]
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: The index (= 2/3) must be an integer
sage: a[Mod(2,3)]
a_2
sage: X.<a,b> = InfinitePolynomialRing(QQ)
sage: a[0]
a_0
sage: a['0+5']
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: invalid literal for int() with base 10: '0+5'

Extensions

The variable names can be any alphanumeric string. The base ring can be any commutative ring. Note the rhyme...

sage: A.<t> = ZZ[]
sage: X.<alpha,beta>= InfinitePolynomialRing(A)
sage: X
Infinite polynomial ring in alpha, beta over Univariate Polynomial Ring in t over Integer Ring
sage: 1/2*alpha[2]*t^3+alpha[1]*beta[4]^2
1/2*t^3*alpha_2 + alpha_1*beta_4^2
sage: latex(_)
(\frac{1}{2} t^{3}) \alpha_{2} + \alpha_{1}\beta_{4}^{2}

1.1.
Some words on the implementation for arbitrary base rings: Working on it, I discovered some bugs in MPolynomialRing_polydict, as I reported on sage-devel. However, there was no answer (so, apparently no interest).

Therefore I decided to just work around these bugs. One issue is to evaluate a string 'x_2*t', if 'x_2' is a variable in an infinite polynomial ring and 't' is a variable in the base ring. gens_dict() would at most know about 'x_2' --- but with the additional complication that there is no fixed finite list of variables for the infinite polynomial ring.

Solution

I introduced a dictionary-like class InfiniteGenDict, that returns a variable of an infinite polynomial ring, given its name.

And I introduced a class GenDictWithBasering that returns a variable of the ring or its base-ring or the base-ring of its base-ring or... The first answer wins.

I think that this class might be of general use, e.g., for fixing issues in MPolynomialRing_polydict.

Examples:

sage: R.<a,b> = InfinitePolynomialRing(QQ['t'])
sage: R('a_0*t')
t*a_0
sage: _.parent()
Infinite polynomial ring in a, b over Univariate Polynomial Ring in t over Rational Field
sage: R._P
Multivariate Polynomial Ring in a_1, a_0, b_1, b_0 over Univariate Polynomial Ring in t over Rational Field
sage: type(_)
<class 'sage.rings.polynomial.multi_polynomial_ring.MPolynomialRing_polydict_domain'>
sage: R._P('a_0*t')
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: unable to convert string

This is what I mean by "bug in MPolynomialRing_polydict"! And this is why I use string evaluation as a last resort, since this works much better:

sage: R.gens_dict()
GenDict of Infinite polynomial ring in a, b over Univariate Polynomial Ring in t over Rational Field
sage: _._D
[InfiniteGenDict defined by ['a', 'b'], {'t': t}, {'1': 1}]
sage: sage_eval('a_0*t',R.gens_dict())
t*a_0
sage: R.gens_dict()['t'].parent()
Univariate Polynomial Ring in t over Rational Field
sage: R.gens_dict()['a_4'].parent()
Infinite polynomial ring in a, b over Univariate Polynomial Ring in t over Rational Field

I think that GenDictWithBasering can provide a solution for the trouble with MPolynomialRing_polydict. As I showed, direct string conversion was flawed. But the following works:

sage: from sage.rings.polynomial.infinite_polynomial_ring import GenDictWithBasering
sage: D = GenDictWithBasering(R._P, R._P.gens_dict())
sage: sage_eval('a_0*t',D)
t*a_0
sage: _.parent()
Multivariate Polynomial Ring in a_1, a_0, b_1, b_0 over Univariate Polynomial Ring in t over Rational Field

It is now possible to construct quotient rings of infinite polynomial rings by symmetric ideals. Here, of course, it is required to have a field as base ring (for Groebner bases)

sage: R.<x> = InfinitePolynomialRing(QQ)
sage: I = R.ideal([x[1]*x[2] + x[3]])

Note that I is not a symmetric Groebner basis (the symmetric Groebner basis of a principal symmetric ideal is generally not formed by a single polynomial!):

sage: G = R*I.groebner_basis()
sage: G
Symmetric Ideal (x_1^2 + x_1, x_2 - x_1) of Infinite polynomial ring in x over Rational Field
sage: Q = R.quotient(G)
sage: p = x[3]*x[1]+x[2]^2+3
sage: Q(p)
-2*x_1 + 3

By the second generator of G, variable x_n is equal to x_1 for any positive integer n.
By the first generator of G, x_1³ is equal to x_1 in Q. Indeed, we have

sage: Q(p)*x[2] == Q(p)*x[1]*x[3]*x[5]
True

Note that the one doc test in quotient_ring.py has a doc test involving symmetric ideals. I don't know who wrote it, but (s)he forgot to use a symmetric Groebner basis for the ideal.

Coercion

I discovered construction functors and pushout, and now I really appreciate Sage's coercion system. By consequence, I make extensive use of it --- hopefully not too much...

I introduced a construction functor for infinite polynomial rings. This functor, together with a ring, is used as the unique key of an infinite polynomial ring (as unique parent structure. I don't know if the use of construction functors for providing unique parents is common --- but I can recommend it!

sage: InfinitePolynomialRing.create_key(QQ, ('y1',))
(InfPoly{[y1], "lex", "dense"}(FractionField(...)), Integer Ring)
sage: InfinitePolynomialRing.create_key(QQ, names=['beta'], order='deglex', implementation='sparse')
(InfPoly{[beta], "deglex", "sparse"}(FractionField(...)), Integer Ring)
sage: InfinitePolynomialRing.create_key(QQ, names=['x','y'], implementation='dense')
(InfPoly{[x,y], "lex", "dense"}(FractionField(...)), Integer Ring)

As you can see, the given base ring is generally not used in the unique key. The reason is explained in the next paragraph.

In a way, an infinite polynomial ring X is just an upgrade of a usual polynomial ring P: The former has finitely many generators x, y and infinitely many variables x_0, x_1,..., y_0,y_1,..., while the latter may have finitely many variables x_0,x_1,x_2.

Now, imagine what happens if you define X = InfinitePolynomialRing(P,['x','y'])? We can't simply take P as the base ring of X, since there is a name conflict. But since P can be considered a sub-structure of X: Why shouldn't one merge it into X?

In fact, this is what I do, still with unique parent structures:

sage: P.<a,b,x_2,x_0,y_3,y_2> = QQ[]
sage: X.<x,y> = InfinitePolynomialRing(P, order='degrevlex')
sage: X
Infinite polynomial ring in x, y over Multivariate Polynomial Ring in a, b over Rational Field
sage: P2.<a,b> = QQ[]
sage: X2.<x,y> = InfinitePolynomialRing(P2, order='degrevlex')
sage: X2 is X
True

However, one has to be cautious: Infinite Polynomial Rings are ordered rings. Therefore, we only merge P into X if it is not only isomorphic to a sub-ring of X, but isomorphic to an ordered sub-ring of X. If this is not the case, an error will be raised:

sage: X3.<x,y> = InfinitePolynomialRing(P) # the standard order is lex
---------------------------------------------------------------------------
CoercionException                         Traceback (most recent call last)
...
CoercionException: Incompatible term orders lex, degrevlex
sage: X3.<y,x> = InfinitePolynomialRing(P, order='degrevlex')
---------------------------------------------------------------------------
CoercionException                         Traceback (most recent call last)
...
CoercionException: Overlapping variables (('y', 'x'),['x_2', 'x_0', 'y_3', 'y_2']) are incompatible

Note: We attempted to make y_* greater than x_* in X, but x_* is greater than y_* in P.

sage: P.<a,b,x_0,x_2,y_3,y_2> = QQ[]
sage: X3.<x,y> = InfinitePolynomialRing(P, order='degrevlex')
---------------------------------------------------------------------------
CoercionException                         Traceback (most recent call last)
...
CoercionException: Overlapping variables (('x', 'y'),['x_0', 'x_2', 'y_3', 'y_2']) are incompatible

Note: In any infinite polynomial ring holds x_2>x_0, but the order in P is opposite.

The 'magical merging' is based on the multiplication of construction functors, combined with the fact that functors are used as unique keys for parent structures.

Remark

What I do here could also be a model for polynomial rings. After all, I think it is a bug that the following does not raise an error:

sage: QQ['t']['t']
Univariate Polynomial Ring in t over Univariate Polynomial Ring in t over Rational Field

The original purpose of the coercion machinery is probably to allow for flexible use of arithmetic with elements of different rings. There you are:

sage: 1/2*x_2+z[3]-a/((3*z[2]+2*z[1]+3)^2).lc()
z_3 - 1/9*a + 1/2*x_2
sage: _.parent()
Infinite polynomial ring in z over Multivariate Polynomial Ring in a, b, x_2, x_0, y_3, y_2 over Rational Field

or

sage: P.<a,b,x_2,x_0,y_3,y_2> = ZZ[]
sage: X.<y,z> = InfinitePolynomialRing(ZZ,order='degrevlex')
sage: 1/2*x_2+z[3]-a/((3*z[2]+2*z[1]+3)^2).lc()
z_3 - 1/9*a + 1/2*x_2
sage: _.parent()
Infinite polynomial ring in y, z over Multivariate Polynomial Ring in a, b, x_2, x_0 over Rational Field

Note that the last example only works since P and X both have order 'degrevlex'; otherwise we couldn't fit both P and X into a common ring.

Self-critical comments

• The closed ticket Tab completion for elements of InfinitePolynomialRing #6854 provides tab completion for elements of infinite polynomial rings. Here I provide a slightly simpler implementation. But I wouldn't mind if the implementation from Tab completion for elements of InfinitePolynomialRing #6854 would be used instead.
• The patch contains the changes that I suggested on Inconsistent ordering when composing functors #7620. It is essential that these changes are done. So, Inconsistent ordering when composing functors #7620 may be considered a duplicate (or sub-ticket).
• The new InfinitePolynomialFunctor has rank 9.5; this is since PolynomialFunctor has rank 9 and should be applied before InfinitePolynomialFunctor --- but rank 10 is taken by MatrixFunctor. I hope that fine tuning is ok.
• The doc tests of devel/sage/sage/numerical/mip.pyx will break, since the name scheme for variables of infinite polynomial rings has changed. However, Replaces InfinitePolynomialRing in MixedIntegerLinearProgram by 'var', and bug fixing in constraints() #7561 suggests to remove infinite polynomial rings from mip.pyx. So, I can live with these broken doc tests...

Question to the Reviewer

Can you please test on a 32 bit machine as well? I know that the hash code on 64 bit has changed, but I have no access to 32 bit and don't know what hash value to expect.

I hope that you enjoy that patch bomb...

Cheers,

Simon

[simon-king-jena]

Author: Simon King

[williamstein]

comment:11

"The variable names can be any alphanumeric string. The base ring can be any commutative ring. Note the rhyme..."

The bugs in your code can really sting.
But the speed will really zing!

[simon-king-jena]

comment:12

Replying to @williamstein:

The bugs in your code can really sting.
But the speed will really zing!

:)

If there is a speed improvement then it is very likely due to the recent improvements of conversions in MPolynomialRing_libsingular (in that case I don't use sage_eval) and in MPolynomial_libsingular.exponent() (I use regular expressions to determine the exponents only if MPolynomial_polydict occurs).

And if there are bugs -- well, of course there are (as in any non-trivial program), but I did my best to hide them.

Cheers,
Simon

[williamstein]

comment:13

Here are the doctest failures on 32-bit Ubuntu:

sage -t  "devel/sage/sage/rings/polynomial/infinite_polynomial_element.py"
**********************************************************************
File "/tmp/wstein/farm/sage-4.3.alpha1/devel/sage/sage/rings/polynomial/infinite_polynomial_element.py", line 177:
    sage: InfinitePolynomial(X,alpha_2)
Expected:
    alpha_0
Got:
    alpha_1
**********************************************************************
File "/tmp/wstein/farm/sage-4.3.alpha1/devel/sage/sage/rings/polynomial/infinite_polynomial_element.py", line 264:
    sage: hash(a)
Expected:
    233743571
Got:
    -957478897
**********************************************************************
2 items had failures:
   1 of  23 in __main__.example_1
   1 of   5 in __main__.example_5
***Test Failed*** 2 failures.

[simon-king-jena]

comment:29

Replying to @JohnCremona:

Maybe my 4.3.1.alpha1 build is messed up, but the new patch would not apply for me!Essentiall every hunk failed, which made me suspicious that I have messed up. But I tried it on two different machines, so maybe I did not!

What????

Even parts of the old patch would apply to sage-4.3.1.alpha1.

Anyway. What I did to produce the patch was:

• Build sage-4.3.1.alpha1 on sage.math
• Copy the relevant files to my laptop
• Merge them with my changes
• Put them back to sage.math
• Commit and produce a patch

So, I am really puzzled. Can other people confirm that it fails to apply?

Cheers,

Simon

[simon-king-jena]

comment:30

Has anybody tried yet whether the patch really fails to apply?

[JohnCremona]

comment:31

I'm building a new 4.3.1.alpha1 (for another reason) and when that's finished I'll try again.

[wjp]

comment:32

The patch has DOS/Windows endlines, so maybe doing a

dos2unix 7580_fixes_and_extensions.patch

will make it apply cleanly.

[simon-king-jena]

Attachment: 7580_fixes_and_extensions.patch.gz

Major bug fixes and extensions for infinite polynomial rings

[simon-king-jena]

comment:33

Replying to @wjp:

The patch has DOS/Windows endlines, so maybe doing a

dos2unix 7580_fixes_and_extensions.patch

will make it apply cleanly.

Thank you for your hint! I changed the attachment accordingly.

The problem is that at home I only have a tiny little Eee PC that came with Windows. I thought that xemacs on Windows would be good enough, but apparently it isn't. The patch was made on sage.math, though.

So, let us hope that it now works!

Best regards,
Simon

[JohnCremona]

comment:34

The new patch applies fine to 4.3.1, and almost all tests pass. (I tested the whole Sage library):

sage -t  sage/structure/sage_object.pyx
**********************************************************************
File "/home/john/sage-4.3.1/devel/sage-tests/sage/structure/sage_object.pyx", line 986:
    sage: print "x"; sage.structure.sage_object.unpickle_all(std)
Expected:
    x...
    Successfully unpickled ... objects.
    Failed to unpickle 0 objects.
Got:
    x
    doctest:1: DeprecationWarning: Your word object is saved in an old file format since FiniteWord_over_OrderedAlphabet is deprecated and will be deleted in a future version of Sage (you can use FiniteWord_list instead). You can re-save your word by typing "word.save(filename)" to ensure that it will load in future versions of Sage.
    doctest:1: DeprecationWarning: Your word object is saved in an old file format since AbstractWord is deprecated and will be deleted in a future version of Sage (you can use FiniteWord_list instead). You can re-save your word by typing "word.save(filename)" to ensure that it will load in future versions of Sage.
    doctest:1: DeprecationWarning: Your word object is saved in an old file format since Word_over_Alphabet is deprecated and will be deleted in a future version of Sage (you can use FiniteWord_list instead). You can re-save your word by typing "word.save(filename)" to ensure that it will load in future versions of Sage.
    doctest:1: DeprecationWarning: Your word object is saved in an old file format since Word_over_OrderedAlphabet is deprecated and will be deleted in a future version of Sage (you can use FiniteWord_list instead). You can re-save your word by typing "word.save(filename)" to ensure that it will load in future versions of Sage.
    doctest:1: DeprecationWarning: ChristoffelWord_Lower is deprecated, use LowerChristoffelWord instead
    ** failed:  _class__sage_rings_polynomial_infinite_polynomial_element_InfinitePolynomial_dense__.sobj
    ** failed:  _class__sage_rings_polynomial_infinite_polynomial_ring_InfinitePolynomialGen__.sobj
    ** failed:  _class__sage_rings_polynomial_infinite_polynomial_ring_InfinitePolynomialRing_dense__.sobj
    ** failed:  _class__sage_rings_polynomial_infinite_polynomial_ring_InfinitePolynomialRing_sparse__.sobj
    ** failed:  _class__sage_rings_polynomial_symmetric_ideal_SymmetricIdeal__.sobj
    ** failed:  _type__sage_rings_polynomial_symmetric_reduction_SymmetricReductionStrategy__.sobj
    Failed:
    _class__sage_rings_polynomial_infinite_polynomial_element_InfinitePolynomial_dense__.sobj
    _class__sage_rings_polynomial_infinite_polynomial_ring_InfinitePolynomialGen__.sobj
    _class__sage_rings_polynomial_infinite_polynomial_ring_InfinitePolynomialRing_dense__.sobj
    _class__sage_rings_polynomial_infinite_polynomial_ring_InfinitePolynomialRing_sparse__.sobj
    _class__sage_rings_polynomial_symmetric_ideal_SymmetricIdeal__.sobj
    _type__sage_rings_polynomial_symmetric_reduction_SymmetricReductionStrategy__.sobj
    Successfully unpickled 565 objects.
    Failed to unpickle 6 objects.
**********************************************************************

If this pickling problem can be sorted out, this can pass!

[simon-king-jena]

comment:35

Replying to @JohnCremona:

The new patch applies fine to 4.3.1, and almost all tests pass. (I tested the whole Sage library):

As I explained above, the "unique key" in the ring constructor has completely changed: It used to be a base ring plus the list of variable names plus a descriptor of the monomial order and of the implementation (dense vs. sparse); now, it is a ring plus a construction functor. I guess this explains the error.

But there is a version number passed to the construction factory, in addition to the unique key. Probably that allows to transform old pickles into shiny new rings.

I did not know that there existed old pickles. Thank you for pointing it out!

Best regards,

Simon

[simon-king-jena]

comment:36

Replying to @simon-king-jena:

But there is a version number passed to the construction factory, in addition to the unique key. Probably that allows to transform old pickles into shiny new rings.

There is a very clear difference between new and old "unique keys" (which are used for pickling): New keys are pairs, old keys are longer tuples. I guess it is robuster to discriminate by the length of the key rather than by version number.

I am now running sage -testall and (if it works) will provide another patch later.

Cheers,

Simon

[simon-king-jena]

Attachment: 7580_unpickling.patch.gz

Allows to read old pickles of infinite polynomial rings

[simon-king-jena]

comment:37

The patch 7580_unpickling.patch is to be applied after 7580_fixes_and_extensions.patc (disregard the third patch). With the patch, sage -testall worked perfectly for me. Hence, I think it is ready to review.

To summarize the content of the patch bomb, I refer to my comments 10 and 20.

[JohnCremona]

comment:38

Patch problem: I tried applying 7580_fixes_and_extensions.patch to both 4.3.1 and 4.3.2.alpha0 and in both cases there were many hunks which failed.

Could you list by name which of the three patches should be applied and in which order? I seem to have this confused...

[simon-king-jena]

comment:39

Replying to @JohnCremona:

Patch problem: I tried applying 7580_fixes_and_extensions.patch to both 4.3.1 and 4.3.2.alpha0 and in both cases there were many hunks which failed. Could you list by name which of the three patches should be applied and in which order? I seem to have this confused...

Very strange. It should at least apply to 4.3.1, since this is what I started with. And according to your comment 34, you had been able to apply it once. Perhaps you did not revert it?

Anyway. One should first apply 7580_fixes_and_extensions.patch, then 7580_unpickling.patch, and that's all.

Cheers,

Simon

[JohnCremona]

comment:40

I must have messed something up, since I made a new clone from the main branch in each case and applied the correct patch first, which I had previously applied with no problem. Perhaps I had made changes to the main branch by mistake. But that would not affect the attempt on 4.3.2.alpha0, since I had not made any clones or applied any patches to that before trying this.

I am currently building 4.3.2.alpha1 from source; when that is done I'll have another go -- might as well, since that will be what these patches have to apply towhen merged in any case!

[JohnCremona]

comment:41

On a new clone of a new build of 4.3.2.alpha1, I cannot apply the first patch (i.e. 7580_fixes_and_extensions.patch).

I think someone else had better try!

[simon-king-jena]

comment:42

Replying to @JohnCremona:

On a new clone of a new build of 4.3.2.alpha1, I cannot apply the first patch (i.e. 7580_fixes_and_extensions.patch). I think someone else had better try!

OK, then I'll rebase it and post a single patch that unifies the two old patches.

However, it'll take a few hours until 4.3.2.alpha1 will be available.

[JohnCremona]

comment:43

OK, so this is partly my fault: I had not realized that the patch named 7580_fixes_and_extensions.patch had been updated (the old one was 172079 bytes, the new one is 168016 bytes -- something about line-ends).

I had been applying the older one. So I tried the new one and got this (fresh clone of 4.3.1.alpha1):

sage: hg_sage.apply("/home/jec/patches/7580_fixes_and_extensions.patch")
cd "/home/jec/sage-4.3.2.alpha1/devel/sage" && hg status
cd "/home/jec/sage-4.3.2.alpha1/devel/sage" && hg status
cd "/home/jec/sage-4.3.2.alpha1/devel/sage" && hg import   "/home/jec/patches/7580_fixes_and_extensions.patch"
applying /home/jec/patches/7580_fixes_and_extensions.patch
patching file sage/rings/polynomial/infinite_polynomial_element.py
Hunk #10 succeeded at 333 with fuzz 2 (offset 0 lines).
Hunk #11 FAILED at 353
1 out of 41 hunks FAILED -- saving rejects to file sage/rings/polynomial/infinite_polynomial_element.py.rej
abort: patch failed to apply

which still needs a little attention, but only a little!

[simon-king-jena]

Stand-alone patch relative to sage-4.3.2.alpha1

[simon-king-jena]

comment:44

Attachment: 7580_fixes_and_extensions_total.patch.gz

I produced a new patch relative to sage-4.3.2.alpha1, that summarizes all other patches. So, just apply 7580_fixes_and_extensions_total.patch.

Note that I merged the code of sage-4.3.2.alpha1 with my new code on a Windows laptop. But I transferred it to a Linux PC, used dos2unix, and all further edits happened there. Then, I created a patch, copied it to my Windows laptop, and there you are. I hope that in that way I avoided Windows EOL.

Note that there is one additional change. It seems that the "dir" mechanism has changed in sage-4.3.2: Before, the documentation of dir stated that it would use a method !dir! if available, but in fact it ignored such method. Instead, it used the attributes !members! and !methods! or so.

This has now changed (as I noticed when a doc test failed), and by consequence I now provide a !dir! method in addition to the old form of tab completion.

Concerning tests: I did not do sage -testall. But I did test the files that I have changed: pushout.py, symmetric_ideal.py, symmetric_reduction.pyx, infinite_polynomial_ring.py, and infinite_polynomial_element.py

Hopefully it works now...

[JohnCremona]

comment:45

The latest patch applies fine to 4.3.2.alpha1, and all tests pass! I tested the whole library (but not with long).

[qed777]

Reviewer: John Cremona

[qed777]

Merged: sage-4.3.3.alpha0