Let singular_function expect "attributes" not as a dict

[SimonKing]

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

• trac12977_singular_function_attributes.patch
• trac_12977-fix_doctest.patch

[SimonKing]

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

[SimonKing]

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.

[SimonKing]

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

[SimonKing]

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

[SimonKing]

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

[mhansen]

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

[robertwb]

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

[SimonKing]

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.

[SimonKing]

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]

Replying to SimonKing:

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.

[SimonKing]

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