Let singular_function expect "attributes" not as a dict

[simon-king-jena]

Here is how attributes are passed to libsingular when calling a singular function:

sage: from sage.libs.singular import singular_function
sage: P.<x,y>=QQ[]
sage: J = P*[P.random_element() for _ in range(100)]
sage: NF = singular_function('reduce')
sage: _ = NF(J.groebner_basis(),J,attributes={J:{'isSB':1}})

Hence, a dictionary is expected, where the keys are arguments to the function. Now, that's bad: The hash of ideals is broken and is slow (see #12976).

Moreover, the attribute is supposed to be applied to a particular object, but not to an object that is only equal (but not identical).

Suggestion

Make it so that

sage: _ = NF(J.groebner_basis(),J,attributes=(None,{'isSB':1}))

works: attributes is a tuple or list of things that are to be interpreted as attribute of the different arguments of the singular function, in the given order.

Apply

• attachment: trac12977_singular_function_attributes.patch

CC: @malb @sagetrac-PolyBoRi @burcin

Component: commutative algebra

Keywords: sd40.5

Author: Simon King

Reviewer: Mike Hansen

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

[simon-king-jena]

comment:1

I think the suggestion in the new ticket description is better than the old one.

[simon-king-jena]

Description changed:

--- 
+++ 
@@ -17,6 +17,6 @@
 Make it so that

-sage: _ = NF(J.groebnerbasis(),J,attributes=((J,{'isSB':1}),)) +sage: = NF(J.groebner_basis(),J,attributes=({'isSB':1},))

-works, where inside `NF.__call__` the items in the attributes tuple/list are compared by identity.
+works: attributes is a tuple or list of things that are to be interpreted as attribute of the different arguments of the singular function, in the given order.

[simon-king-jena]

Description changed:

--- 
+++ 
@@ -17,6 +17,6 @@
 Make it so that

-sage: _ = NF(J.groebnerbasis(),J,attributes=({'isSB':1},)) +sage: = NF(J.groebner_basis(),J,attributes=(None,{'isSB':1}))

 works: attributes is a tuple or list of things that are to be interpreted as attribute of the different arguments of the singular function, in the given order.

[simon-king-jena]

comment:4

Alternative idea of Burcin:

sage: _ = NF(J.groebner_basis(),set_singular_attribute(J,isSB=1))

set_singular_attribute (or a shorter name) would create some auxiliary object that stores J and its attribute, so that the singular function can retrieve the necessary data from it.

Alternative idea of Simon:

sage: _ = NF(J.groebner_basis(),J,attributes=((J,{'isSB':1})))

where the first part of the tuple items is compared by identity (not by equality, since that would involve GB computation.

[simon-king-jena]

comment:5

The attached patch still supports the current way of providing the attributes to a singular_function, but also supports a new one that does not involve a GB computation but compares ideals by identity, and is thus faster. Example:

sage: P.<x,y> = QQ[]
sage: J = P*[P.random_element(4,5)^2 for _ in range(4)]
sage: J
Ideal (x^4*y^4 + 2*x^2*y^5 + y^6 - 2/3*x^2*y^2 - 2/3*y^3 + 1/9, 9/16*y^6 - x^2*y^3 + 3/2*x*y^4 + 1/2*y^5 + 4/9*x^4 - 4/3*x^3*y + 5/9*x^2*y^2 + 2/3*x*y^3 + 1/9*y^4 + 12*y^3 - 32/3*x^2 + 16*x*y + 16/3*y^2 + 64, y^8 - 2/5*x^3*y^4 + 1/25*x^6 - 4/11*x*y^4 + 6*y^5 + 4/55*x^4 - 6/5*x^3*y + 10*y^4 - 2*x^3 + 4/121*x^2 - 12/11*x*y + 9*y^2 - 20/11*x + 30*y + 25, 1/400*x^4*y^4 - 1/5*x^5*y^2 - 1/20*x^4*y^3 + 4*x^6 + 2*x^5*y + 11/20*x^4*y^2 - 12*x^5 - 3*x^4*y + 9*x^4) of Multivariate Polynomial Ring in x, y over Rational Field
sage: J2 = J.gens()*P
sage: J.groebner_basis()
[1]

So, we consider here the trivial ideal. As it happens, the GB computation takes a noticeable time.

Let us define a singular library function:

sage: isSB = {'isSB':1}
sage: from sage.libs.singular import singular_function
sage: NF = singular_function('reduce')

Old syntax:

sage: sage: %timeit q = NF(J,J, attributes={J:isSB})
625 loops, best of 3: 1.42 ms per loop
sage: %timeit q = NF(J2,J, attributes={J:isSB})
125 loops, best of 3: 5.62 ms per loop
sage: %timeit q = NF(J2,J2, attributes={J2:isSB})
25 loops, best of 3: 14 ms per loop

As you observe, the timings differ widely when one takes copies of the same ideal. I thought the reason is that the Gröbner basis of J has been computed, but that of J2 has not. Thus, comparing J2 with another ideal involves computing the Gröbner basis of a copy of J2. But I could be mistaken, see below.

Here is the same with the new syntax:

sage: %timeit q = NF(J,J, attributes=((J,isSB),))
625 loops, best of 3: 279 µs per loop
sage: %timeit q = NF(J2,J, attributes=((J,isSB),))
625 loops, best of 3: 654 µs per loop
sage: %timeit q = NF(J2,J2, attributes=((J2,isSB),))
125 loops, best of 3: 1.69 ms per loop

I am actually surprised that the timings differ. Anyway, the timings in the new syntax are a lot faster than with the old syntax.

And here is why I think that my statement on computation of Gröbner bases in the old syntax may be wrong. Namely, the timings for comparison are a long way slower:

sage: J2 = J.gens()*P
sage: %timeit J==J2
5 loops, best of 3: 645 ms per loop
sage: J2.groebner_basis.is_in_cache()
False

Hence, even though J and J2 belong to the same ring, a Gröbner basis of a copy of J2 is computed, which is thus not cached. That should be changed on a different ticket.

Conclusion

The problem was different than I originally thought, but the new (optional) syntax provided by my patch makes things faster. Needs review, although I should change the text in the documentation (because apparently Gröbner bases aren't involved).

[simon-king-jena]

comment:6

The problem of avoiding needless GB computations in comparison of ideals is now #12987.

[mwhansen]

Author: Simon King

[mwhansen]

Description changed:

--- 
+++ 
@@ -20,3 +20,8 @@
 sage: _ = NF(J.groebner_basis(),J,attributes=(None,{'isSB':1}))

works: attributes is a tuple or list of things that are to be interpreted as attribute of the different arguments of the singular function, in the given order. + +Apply + + attachment: trac12977_singular_function_attributes.patch + attachment: trac_12977-fix_doctest.patch

[mwhansen]

comment:7

Attachment: trac_12977-fix_doctest.patch.gz

Simon, your patch looks good, but I had to make a change to the doctest to get it to pass. Are you okay with this change? If so, you can mark this as positive review.

For the patchbot:

Apply trac12977_singular_function_attributes.patch and trac_12977-fix_doctest.patch

[mwhansen]

Reviewer: Mike Hansen

[mwhansen]

Changed keywords from none to sd40.5

[robertwb]

comment:9

a_attrib will be defined after any non-empty loop even if it doesn't break with a match

I think that this interface is rather subtle, I'd rather have a compare_using_identiy=[True|False] keyword in the function (which will iterate over the dictionary rather than indexing into it). On that note, is indexing ever safe (do equal ideals always hash the same?)

[simon-king-jena]

comment:10

Replying to @robertwb:

a_attrib will be defined after any non-empty loop even if it doesn't break with a match

I don't understand that comment. a_attrib is used only in the few lines that I changed. And what loop are you talking about? The outer loop for a in args: (line 559)? But a_attrib is set to None at each round of the outer loop: See the new line 630.

I think that this interface is rather subtle, I'd rather have a compare_using_identiy=[True|False] keyword in the function (which will iterate over the dictionary rather than indexing into it).

One could argue that by using the dictionary (i.e., the old syntax) you declare that you want comparison by equality rather than identity. And also note that in Singular you assign an attribute to an individual ideal; hence, I find it wrong that in Sage we assign the attributes to an equivalence class of ideal.

On that note, is indexing ever safe (do equal ideals always hash the same?)

No, as mentioned in the ticket description, the hash is totally broken (#12976). Two polynomial ideals are equal if they have the same reduced Gröbner basis (computed in degrevlex order, if the GB for the "real" order ist not in the cache), but the hash relies on the given generators. That's why I support the old syntax only for backwards compatibility.

[simon-king-jena]

comment:11

I am changing back to "needs review", as I think a_attrib is correctly used in the code, and I think I have addressed the other questions of Robert as well.

[robertwb]

comment:12

Replying to @simon-king-jena:

Replying to @robertwb:

a_attrib will be defined after any non-empty loop even if it doesn't break with a match

I don't understand that comment. a_attrib is used only in the few lines that I changed. And what loop are you talking about? The outer loop for a in args: (line 559)? But a_attrib is set to None at each round of the outer loop: See the new line 630.

    634                     for a_,a_attrib in attributes: 
    635                         if a_ is a: 
    636                             break 

If the a_ is a clause is never executed, the loop will run to completion and a_attrib will have the value attributes[-1][1] unless attributes happens to be empty.

I think that this interface is rather subtle, I'd rather have a compare_using_identiy=[True|False] keyword in the function (which will iterate over the dictionary rather than indexing into it).

One could argue that by using the dictionary (i.e., the old syntax) you declare that you want comparison by equality rather than identity.

But this is equivalently subtle, I'd never guess that in seeing the two versions. In any case it's certainly not

sage: import this
The Zen of Python, by Tim Peters
...
Explicit is better than implicit.

Are you against having an explicit flag?

And also note that in Singular you assign an attribute to an individual ideal; hence, I find it wrong that in Sage we assign the attributes to an equivalence class of ideal.

I'm with you here, but that's orthogonal.

[simon-king-jena]

Work Issues: Do not set a_attrib accidentally. Provide a flag for "comparison by equality"

[simon-king-jena]

comment:13

Replying to @robertwb:

  634                     for a_,a_attrib in attributes: 
  635                         if a_ is a: 
  636                             break 

If the a_ is a clause is never executed, the loop will run to completion and a_attrib will have the value attributes[-1][1] unless attributes happens to be empty.

I see. Right, that has to be fixed.

Are you against having an explicit flag?

I think the default should be "comparison by identity", because I am sure that this is how the attributes argument is intended to be used.

I also think that (for backwards compatibility) one should still support the old syntax, for which "comparison by Gröbner basis computation and broken hash" is implicit.

And I think that there is no harm in providing an explicit flag if one wants the new syntax with a "comparison by Gröbner bass computation but without broken hash involved since there is a list and not a dictionary of ideal-attribute pairs".

[simon-king-jena]

An alternative way of passing attributes to singular_function that won't involve GB computations

[simon-king-jena]

comment:14

Attachment: trac12977_singular_function_attributes.patch.gz

Sorry for not finishing it earlier.

I hope I did address the two complaints successfully. In particular, a_attrib will now only be non-none, if it actually applies to one of the arguments. And I provide an optional argument by which one can choose whether one wants comparison by identity or by equality.

If the attributes are passed as a dict, then there is no change w.r.t old behaviour: The broken hash will be used, and comparison by equality. In particular, this will not break things that were not broken before.

If the attributes are passed as a tuple or list, then the default is a comparison by identity---I can not imagine a use case in which one would like to compare by equality. But if one really wants equality, one can set an optional parameter accordingly.

Further changes: I tried to make the new syntax more visible in the docs. The second patch is not needed. Hence:

Apply trac12977_singular_function_attributes.patch

[simon-king-jena]

Description changed:

--- 
+++ 
@@ -24,4 +24,3 @@
 Apply

 * [attachment: trac12977_singular_function_attributes.patch](https://github.com/sagemath/sage-prod/files/10655566/trac12977_singular_function_attributes.patch.gz)
-* [attachment: trac_12977-fix_doctest.patch](https://github.com/sagemath/sage-prod/files/10655565/trac_12977-fix_doctest.patch.gz)

[simon-king-jena]

Changed work issues from Do not set a_attrib accidentally. Provide a flag for "comparison by equality" to none

[simon-king-jena]

comment:16

Is there any reviewer? I still think it is a good idea to not use multivariate polynomial ideals as dictionary keys, given the fact that their hash is broken (or used to be broken until recently) and comparison can be extremely slow due to Gröbner basis computations.

[malb]

comment:17

Sorry for being late to the party.

I am wondering, though, whether we every want to compare not by identit as we are talking about attributes of objects here.

We could keep the dict notation but write our own little loop (similar to your tuple loop) which compares keys. These dicts will be small, so the overhead is okay, I'd say.

[simon-king-jena]

comment:18

Replying to @malb:

Sorry for being late to the party.

I am wondering, though, whether we every want to compare not by identit as we are talking about attributes of objects here.

I wonder as well. From my perspective, comparing by identity is fine.

We could keep the dict notation but write our own little loop (similar to your tuple loop) which compares keys. These dicts will be small, so the overhead is okay, I'd say.

Is this really so easy? If the dictionary contains at least two ideals, then the creation of this dictionary might be problematic, due to broken hash and slow comparison.

[malb]

comment:19

Ah, crap, yes, you're right. We shouldn't create dictionaries. How about we deprecate dicts and use your tuple construction instead?

[simon-king-jena]

comment:24

Replying to @malb:

Ah, crap, yes, you're right. We shouldn't create dictionaries. How about we deprecate dicts and use your tuple construction instead?

Why not?

Let's get this fixed!