listing SemistandardTableaux with large max_entry crashes sage

[saliola]

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 8.0, Release Date: 2017-07-21                     │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
sage: SemistandardTableaux([1], max_entry=102).list()
*** Error in `python': double free or corruption (!prev): 0x00000000054cd8b0 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7fb16f3fd7e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x8037a)[0x7fb16f40637a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7fb16f40a53c]
/home/saliola/Applications/sage/local/lib/python2.7/site-packages/sage/libs/symmetrica/symmetrica.so(SYM_free+0x27)[0x7fa19357f037]
/home/saliola/Applications/sage/local/lib/python2.7/site-packages/sage/libs/symmetrica/symmetrica.so(kostka_tab+0xa33)[0x7fa1935ee4c3]
/home/saliola/Applications/sage/local/lib/python2.7/site-packages/sage/libs/symmetrica/symmetrica.so(+0x6d059)[0x7fa193517059]
/home/saliola/Applications/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x82be)[0x7fb16fa7d9be]
/home/saliola/Applications/sage/local/lib/libpython2.7.so.1.0(+0x7b6c3)[0x7fb16f9e86c3]
...

The full output can be found in the attached file.

Note that the output should be a list of 102 tableaux, each of the form [[i]] with i between 1 and 102, inclusive. I.e., the output is not a very big list!

CC: @sagetrac-sage-combinat @tscrim @anneschilling @zabrocki @nthiery @asbuch @hivert

Component: combinatorics

Keywords: days88

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

[saliola]

full output of the error

[saliola]

comment:1

Attachment: output.txt

I do not know how to go about debugging this. Suggestions?

[tscrim]

Changed author from sage-combinat, tscrim, aschilling, zabrocki, nthiery to none

[tscrim]

comment:2

It is calling symmetrica:

for t in symmetrica.kostka_tab(self.shape, self.weight):
    yield self.element_class(self, t)

from

sage: SST = SemistandardTableaux([1], eval=[0]*120+[1])
sage: SST.__iter__??

So a more MWE is

sage: from sage.libs.symmetrica.all import kostka_tab
sage: la = Partition([1])
sage: mu = Compositions()([0]*105+[1])
sage: kostka_tab(la, mu)

Ugg...that means I have to go digging through the symmetrica code again (#23403). I guess I have been the most recent person to do so, which means I will go through that code tomorrow after I get some sleep to see what is breaking.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:3

I was able to trigger this bug at max_entry=100 but 99 seemed fine:

sage: for T in SemistandardTableaux([1], max_entry=100):
....:     print T
[[4]]
[[7]]
[[8]]
[[9]]
[[31]]
[[34]]
[[66]]
[[71]]
[[87]]
[[91]]
[[93]]

Second time I run this I get a seg fault.

I tried to identify if the symmetric function code was calling this in order to calculate coefficients (e.g. m(s([2]+[1]*100))) and fortunately it doesn't seem to be.

I've run into symmetrica implicit limits before: #15407 #15397

[tscrim]

comment:4

Okay, I suspect this has to do with the fact that there are magic constants defining maximum values to be 100 (specifically, RH_MAX in ko.c (and PR_RH_MAX in pr.c). Basically, my assessment is symmetrica is really bad on memory management by just using things of a fixed length of 100.

My conclusion, short of rewriting parts (all?) of symmetrica, I think we might want to raise a NotImplementedError when someone uses a larger length composition going through this code.

[tscrim]

comment:5

Another option would be a native (and probably naïve) implementation when the size is too large.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:6

I think that the native implementation is a good idea or write something similar to lrcalc for semi-standard tableaux. Switching to lrcalc was how we avoided some errors with Schur products. The limits its hitting here are not that big for reasonable choices of partitions.

I think a long term goal should be to replace symmetrica completely. It has known bugs, the main author is no longer alive, and the c code is littered with fairly cryptic abbreviations.

[tscrim]

comment:7

So currently we have the following places where symmetrica is used:

1. Symmetric functions: a. monomial * monomial in Sym b. Qp Hall-Littlewood polynomials c. expanding into a set of variables
2. Schubert polynomials
3. iterating over SSYT of fixed shape and weight

All others are unneeded imports and cleaned up by #23702. Here is the current state of things.

---

Franco and I looked into 1a, and our implementations of what we could find behaved horribly compared to Symmetrica. Franco took a much closer look than I did into trying to understand the Symmetrica code and understand their algorithm. However, at present, I do not understand what they are doing and why it is so much faster. For 1b, we can also use rigged configurations. For 1c, this should be straightforward to implement and may even be faster as Symmetrica just uses the definitions AFAIK.

For 2, see #23403, #23423, #6629.

I don't know about 3. I suspect they are using some sort of backtracking algorithm using recursion, but I am not 100% sure about that.

---

So IMO the low hanging fruit is 1b and 1c. This would be a good place to start. The only other key functionality we depend on is 3, and I think we need to keep that as fast as possible.

[nthiery]

comment:8

Replying to @tscrim:

c. expanding into a set of variables

For 1c, this should be straightforward to implement and may even be faster as Symmetrica just uses the definitions AFAIK.

Beside this would finally enable expanding a Symmetric function f on any finite alphabet whose values belong to some algebra over the base ring of f, as in:

S = SymmetricFunctions(Q)
f = S.s().an_element()
q = QQ['q'].gen()
f([1,q,q<sup>2,q</sup>3])

So ++1 to that one!

Thanks for investigating the others too. For 3, this could be some natural feature to add to lrcalc; maybe Anders (@asbuch) would be willing to add it?

Alternatively, Florent @hivert: is this feature close enough from your certified why3-generated lrcalc-style code that it could be integrated there? Just throwing ideas in the air.

Cheers, Nicolas

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:9

Replying to @tscrim:

So currently we have the following places where symmetrica is used:

1. Symmetric functions: a. monomial * monomial in Sym b. Qp Hall-Littlewood polynomials c. expanding into a set of variables
2. Schubert polynomials
3. iterating over SSYT of fixed shape and weight

I agree with your ordering of priority but add to this list

1. d. 20 transition functions of the classical bases (elementary, complete, power, monomial and Schur).

[tscrim]

comment:10

@asbuch, @hivert see comment:8