Crash with applying divided_difference in SchubertPolynomialRing

[tscrim]

sage: X = SchubertPolynomialRing(ZZ)
sage: a = X([3,2,4,1])
sage: a.divided_difference(2)
python: : Unknown error -315708632

The error number is random every time. The result should be 0.

CC: @sagetrac-sage-combinat @nthiery @VivianePons @fchapoton @darijgr

Component: combinatorics

Keywords: Schubert, symmetrica

Author: Travis Scrimshaw

Branch: c3bfaaf

Reviewer: Darij Grinberg

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

[tscrim]

comment:1

Okay, I've traced the problem down to the fact that there might be no monomials in the Schubert polynomial. Yet it is still a pointer to a non-NULL Schubert polynomial, so the code does not translate it to 0.

[tscrim]

Branch: public/combinat/symmetrica_crash-23403

[tscrim]

Changed keywords from none to Schubert, symmetrica

[tscrim]

comment:2

So the 0 Schubert polynomial is initialized to an empty list, which behaves differently from, e.g., Schur functions. Because of this, the code tries to get the next pointer starting from a null pointer, resulting in a crash within Symmetrica in a way that is not done within a sig_on/sig_off block. I also fix up some other corner cases.

---

New commits:

2afcd0b

Fixing handling of objects for Schuberts.

[tscrim]

Commit: 2afcd0b

[tscrim]

Author: Travis Scrimshaw

[fchapoton]

comment:3

typos:

For convienence

This is compatibile

[sagetrac-git]

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

bd5629b

Fixing typos.

[sagetrac-git]

Changed commit from 2afcd0b to bd5629b

[darijgr]

comment:5

I still don't understand which divided difference operator is meant, and what i is. Is it the delta^i in DIFF.2.4 of http://www.math.ku.dk/~thorup/notes/sympol.pdf ?

[tscrim]

comment:6

Here is what the code gives:

sage: a = X([3,2,1])
sage: a.expand()
x0^2*x1
sage: for w in Permutations(3):
....:     if not w.reduced_word():
....:         continue
....:     print w.reduced_word(),
....:     print a.divided_difference(w).expand()
[2] x0^2
[1] x0*x1
[1, 2] x0
[2, 1] x0 + x1
[2, 1, 2] 1

You can tell that i acts on the i-th variable (although there is a 1-based to 0-based shift needed), and there does not seem to be any signs involved.

[fchapoton]

comment:7

For the definition of the difference operator, see section 2 of http://www.math.cornell.edu/~allenk/schubnotes.pdf

[darijgr]

comment:8

Thanks Frédéric. I'm pushing an improved doc.

However, I think the new behavior, raising errors when there are not enough variables, is wrong. The Schubert polynomial ring is in infinitely many variables by definition; a polynomial isn't "missing" a variable; it just happens to be degree-0 with respect to it.

sage: a = X([1,2,3,4,5])
sage: a.divided_difference(4)

This should yield 0, not an exception!

[sagetrac-git]

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

799527d	Merge branch 'public/combinat/symmetrica_crash-23403' of git://trac.sagemath.org/sage into schub
7f0ee90	document divided difference operators

[sagetrac-git]

Changed commit from bd5629b to 7f0ee90

[tscrim]

comment:10

Replying to @darijgr:

However, I think the new behavior, raising errors when there are not enough variables, is wrong. The Schubert polynomial ring is in infinitely many variables by definition; a polynomial isn't "missing" a variable; it just happens to be degree-0 with respect to it.

sage: a = X([1,2,3,4,5])
sage: a.divided_difference(4)

This should yield 0, not an exception!

That's not new behavior. The only change in behavior is for 0, which is a special case IMO. There is some reason to consider this an error by considering this as the restriction to a finite number of variables. So there is some room for debate, and as such, it should go on another ticket (there's enough "ticket creep" already).

I do not disagree with you that it is more natural for it to be 0, but you also need the same behavior to happen for permutation input. If you're not careful with that input and let symmetrica try to handle it, it can result in crashes or other strange behavior (I can find the ticket that talks about it if you want). So I don't see this as being a simple change either and is another reason to put it on a separate ticket.

[darijgr]

comment:11

Oh, I just realized that you didn't add the "if i > max_a" check. I'll open a new ticket for this.

[darijgr]

comment:12

Why are you using X.element_class(X, z_elt) instead of using something like sum_of_terms? Isn't X a CombinatorialFreeModule?

[darijgr]

comment:13

Created #23423 for the ValueError issue.

[tscrim]

comment:14

Replying to @darijgr:

Why are you using X.element_class(X, z_elt) instead of using something like sum_of_terms? Isn't X a CombinatorialFreeModule?

Yes, and I am taking advantage of that because z_elt is a dict with coefficients in the proper ring. The other way would be X._from_dict(z_elt, coerce=False, remove_zeros=False), but that just does exactly as above.

[sagetrac-git]

Changed commit from 7f0ee90 to 1aaca0f

[sagetrac-git]

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

1aaca0f

document a confusing notation

[tscrim]

comment:17

It definitely makes things no worse than before. There is not really any coercion but instead is just trying to make a corresponding element in Sage; it is referencing an external library (symmetrica) that does not implement a notion of parents. So I think the result could be a little loose with the parent it returns. Again, another ticket.

[tscrim]

comment:18

Oh, but zeros should be removed by symmetrica IIRC.

[darijgr]

comment:19

OK, I'm just seeing that the method plainly doesn't work over non-ZZ/QQ base rings. At least it's being honest about it:

ValueError: a must be a Schubert polynomial over ZZ or QQ

This is probably a BS restriction, and we should be using Symmetrica on monomials rather than on the whole polynomial.

I'm getting more and more confused the longer I stare at the Schubert code. What exactly does the following method (in libs/symmetrica/sb.pxi) do?

def divdiff_perm_schubert_symmetrica(perm, a):
    r"""
    Returns the result of applying the divided difference operator
    $\delta_i$ to $a$ where $a$ is either a permutation or a
    Schubert polynomial over QQ.

I'm pretty sure there is at least one typo in the docstring.

[tscrim]

comment:20

i to perm, but if a is a permutation, then it considered it to be the corresponding monomial in the X basis.

I do not know if lrcalc can do these computations or not (I simply haven't looked), but there is a goal of replacing symmetrica by lrcalc IIRC. However, that is again for later. At least for now, can not have Sage crash when trying to do a computation rather than trying to completely clean this code? I am willing to split this ticket just to focus on the big problem at hand: the crash.

[sagetrac-git]

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

9cadcdd

refactoring divided_difference

[sagetrac-git]

Changed commit from 1aaca0f to 9cadcdd

[darijgr]

comment:22

I have rewritten divided_difference natively in Sage. The resulting function is significantly faster (around factor 2 on the examples I have tried, which involve Schubert polynomials X(pi) with pi \in S_3, S_4, S_5) and free of the #23423 issue. There is more potential for optimization: the whole thing could be rewritten in Cython (not by me), and the remove_extra_fixed_points helper method on the Permutation class could be made into a standalone function that deals with lists (rather than permutations).

In the current commit, for the sake of reviewing, both the new and the old method can be used (the default is the new one; get the old one by setting the optional newm variable to False). I guess we'll want to get rid of the old one before merging.

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 9cadcdd to 1aaca0f

[tscrim]

comment:24

This is a great improvement and is faster on all of the examples I tested (including some relatively large permutations). However, it must go on another ticket as this ticket is about fixing the crash in symmetrica, which is independent of the divided difference functionality. I guess it is somewhat my fault for starting this. Yet, I will revert all of the other little changes if that is what it takes for us to focus on the problem of this ticket. I will review the followup tickets in exchange.

I reverted this branch to 1aaca0f as that is still in the general realm of the ticket, but I am considering a full rewrite. I put your current rewrite on the branch

public/combinat/improve_schubert_divided_difference

[darijgr]

comment:25

Is the crash actually independent from the divided difference functionality? I thought only the divided_difference method would crash. If not, this definitely should be a standalone ticket (but one I cannot reasonably review, sadly).

[tscrim]

comment:26

Yes, the crash occurs because symmetrica returns an empty-list object to represent 0 from the data type but the interpreter is expecting a null pointer for 0 (as is the case for, e.g., Schur functions). The main change is in symmetrica.pxi. I also made the extra change in sb.pxi to further protect against bad-input that leads to either grossly wrong results or a crash. All other changes are tangential.

[jdemeyer]

Replying to @tscrim:

sage: X = SchubertPolynomialRing(ZZ)
sage: a = X([3,2,4,1])
sage: a.divided_difference(2)
python: : Unknown error -315708632

Is that the exact (verbatim) output that you get? On which system is that?

I get

sage: SchubertPolynomialRing(ZZ)([3,2,4,1]).divided_difference(2)
python: ------------------------------------------------------------------------
/usr/local/src/sage-git/local/lib/python2.7/site-packages/cysignals/signals.so(+0x5f38)[0x7fcb98405f38]
/usr/local/src/sage-git/local/lib/python2.7/site-packages/cysignals/signals.so(+0x5fa5)[0x7fcb98405fa5]
/usr/local/src/sage-git/local/lib/python2.7/site-packages/cysignals/signals.so(+0x8db7)[0x7fcb98408db7]
/lib64/libpthread.so.0(+0x10860)[0x7fcba0a9e860]
/lib64/libc.so.6(strchrnul+0x23)[0x7fcba0085de3]
[...truncated a lot...]
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred.
This probably occurred because a *compiled* module has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Python will now terminate.
------------------------------------------------------------------------
Segmentation fault

[jdemeyer]

comment:28

Symmetrica code:

OP s_mo_k(a) OP a;
/* AK 100789 V1.0 */ /* AK 191289 V1.1 */ /* AK 200891 V1.3 */
{
    OBJECTSELF c;
    if (a == NULL)
        return error("s_mo_k:a == NULL"),(OP)NULL;
    if (S_O_K(a) != MONOM)
        return error("s_mo_k:a  != MONOM"),(OP)NULL;
    c = s_o_s(a);
    return(c.ob_monom->mo_koeff);
}

Yup, totally clear what it does :-)

[darijgr]

comment:29

Let me guess, 100789 means 10th July 1989?

That said, the English-German hodgepodge has probably not been up to standards even by the 80s standards...

[tscrim]

comment:30

Replying to @jdemeyer:

Replying to @tscrim:

sage: X = SchubertPolynomialRing(ZZ)
sage: a = X([3,2,4,1])
sage: a.divided_difference(2)
python: : Unknown error -315708632

Is that the exact (verbatim) output that you get?

Yes (other than the number that changes every time).

On which system is that?

Ubuntu 16.04 LTS (with 8.1.beta0)

The segfault is definitely the "correct" failure, but for some reason it seems Python is attempting to handle the error. shrugs

[sagetrac-git]

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

a725130	Merge branch 'public/combinat/symmetrica_crash-23403' of trac.sagemath.org:sage into public/combinat/symmetrica_crash-23403
c3bfaaf	Removing unneeded declaration.

[sagetrac-git]

Changed commit from 1aaca0f to c3bfaaf

[tscrim]

comment:32

Darij looked at this patch with me and gave a positive review.

[tscrim]

Reviewer: Darij Grinberg

[vbraun]

Changed branch from public/combinat/symmetrica_crash-23403 to c3bfaaf

[fchapoton]

Changed commit from c3bfaaf to none