Refactoring of crystals for speedup

[tscrim]

In order to speed up many of the crystals computations, I'm proposing the following:

• Cythonize CrystalOfLetters
• Make index_set() a cached method. Subsequently this requires it to be returned as a tuple instead of a list
• Make different letters classes, one for integers (classical types), one for tuples (exceptional/spin)
• Store by caching result of _element_constructor_() the elements of CrystalOfLetters.

See #14686 for a followup.

Apply:

• trac_14516-crystals_speedup-ts.patch​

[tscrim]

Here are some timings.

With the patch:

sage: B = InfinityCrystalOfTableaux(['B',3])
sage: S = B.subcrystal(max_depth=4)
sage: %time G = B.digraph(subset=S)
CPU times: user 19.55 s, sys: 0.62 s, total: 20.17 s
Wall time: 21.80 s

sage: C = CrystalOfTableaux(['D',4], shape=[2,1])
sage: %time G = C.digraph()
CPU times: user 0.30 s, sys: 0.06 s, total: 0.36 s
Wall time: 0.45 s

Before:

sage: B = InfinityCrystalOfTableaux(['B',3])
sage: S = B.subcrystal(max_depth=4)
sage: %time G = B.digraph(subset=S)
CPU times: user 48.83 s, sys: 1.42 s, total: 50.24 s
Wall time: 58.49 s

sage: C = CrystalOfTableaux(['D',4], shape=[2,1])
sage: %time G = C.digraph()        
CPU times: user 0.50 s, sys: 0.05 s, total: 0.54 s
Wall time: 0.66 s

[tscrim]

I'm also getting significant speedups now in creating CrystalOfLetters and doctests for tensor_product.py and kirillov_reshetikhin.py:

sage: %time C = CrystalOfLetters(['D',100])
CPU times: user 0.84 s, sys: 0.24 s, total: 1.08 s
Wall time: 1.67 s

sage -t tensor_product.py
    [349 tests, 13.05 s]
sage -t kirillov_reshetikhin.py
    [653 tests, 30.51 s]

Before:

sage: %time C = CrystalOfLetters(['D',100])
CPU times: user 2.33 s, sys: 0.42 s, total: 2.76 s
Wall time: 3.58 s

sage -t tensor_product.py
    [349 tests, 14.60 s]
sage -t kirillov_reshetikhin.py
    [653 tests, 47.96 s]

[tscrim]

I'll upload the split patch shortly and check to see if it can commute pass #14143.

[tscrim]

New patch which does not change the functions and does not depend on #14143. The functions are changed in #14686. Timings to come shortly.

[tscrim]

With patch:

sage: %time C = CrystalOfLetters(['D',100])
CPU times: user 1.54 s, sys: 0.03 s, total: 1.56 s
Wall time: 1.72 s

sage: B = InfinityCrystalOfTableaux(['B',3])
sage: S = B.subcrystal(max_depth=4)
sage: %time G = B.digraph(subset=S)
CPU times: user 28.20 s, sys: 0.03 s, total: 28.23 s
Wall time: 28.62 s

sage: C = CrystalOfTableaux(['D',4], shape=[2,1])
sage: %time G = C.digraph()                
CPU times: user 0.33 s, sys: 0.00 s, total: 0.34 s
Wall time: 0.34 s

Before:

sage: %time C = CrystalOfLetters(['D',100])
CPU times: user 1.84 s, sys: 0.02 s, total: 1.86 s
Wall time: 2.00 s

sage: B = InfinityCrystalOfTableaux(['B',3])
sage: S = B.subcrystal(max_depth=4)
sage: sage: %time G = B.digraph(subset=S)
CPU times: user 28.96 s, sys: 0.03 s, total: 28.99 s
Wall time: 29.94 s

sage: C = CrystalOfTableaux(['D',4], shape=[2,1])
sage: %time G = C.digraph()
CPU times: user 0.39 s, sys: 0.01 s, total: 0.40 s
Wall time: 0.39 s

So currently I'm seeing small performance gains, the bigger ones are likely going to come from #14686.

[aschilling]

Hi Travis,

The two tests (with and without patch) do not seem to be the same!

Anne

[tscrim]

@Anne There was some omissions.

New version which fixes the pickling issues and should pass all doctests. #14143 does fix some of the doctests.

[aschilling]

Hi Travis,

The patch looks good (I put a reviewed patch on the sage-combinat queue). I am not so happy about the huge doc tests for setstate. As we discussed, perhaps just put a loads/dumps test?

Best,

Anne

[tscrim]

Done.

[tscrim]

Forgot to qrefresh...

[tscrim]

Forgot to qrefresh.

Apply: trac_14516-crystals_speedup-ts.2.patch

[jferreira]

I get a warning when building the doc:

[combinat ] docstring of sage.combinat.crystals.letters.CrystalOfLetters:21: WARNING: duplicate citation KN94, other instance in /Applications/sage/devel/sage/doc/en/reference/combinat/sage/combinat/crystals/infinity_crystals.rst

[tscrim]

Fixed. Thanks for catching that Jeff (I wish duplicate references would always show up every time you rebuild the doc instead of just the first time).

For patchbot:

Apply: trac_14516-crystals_speedup-ts.patch

[jdemeyer]

There are doctest failures with #12940, please rebase:

sage -t devel/sage/sage/combinat/affine_permutation.py
**********************************************************************
File "devel/sage/sage/combinat/affine_permutation.py", line 241, in sage.combinat.affine_permutation.AffinePermutation.index_set
Failed example:
    A.index_set()
Expected:
    [0, 1, 2, 3, 4, 5, 6, 7]
Got:
    (0, 1, 2, 3, 4, 5, 6, 7)
**********************************************************************
File "devel/sage/sage/combinat/affine_permutation.py", line 2077, in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.index_set
Failed example:
    AffinePermutationGroup(['A',7,1]).index_set()
Expected:
    [0, 1, 2, 3, 4, 5, 6, 7]
Got:
    (0, 1, 2, 3, 4, 5, 6, 7)
**********************************************************************
File "devel/sage/sage/combinat/affine_permutation.py", line 2088, in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.reflection_index_set
Failed example:
    AffinePermutationGroup(['A',7,1]).index_set()
Expected:
    [0, 1, 2, 3, 4, 5, 6, 7]
Got:
    (0, 1, 2, 3, 4, 5, 6, 7)
**********************************************************************

[tscrim]

Fixed:

sage -t affine_permutation.py
    [335 tests, 28.87 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------

For patchbot:

Apply: trac_14516-crystals_speedup-ts.patch

[tscrim]

Anne, could you do a double-check to make sure everything is consistent and works for you? Thanks.

[aschilling]

Replying to tscrim:

Anne, could you do a double-check to make sure everything is consistent and works for you? Thanks.

I still get the above mentioned errors:

sage -t affine_permutation.py
**********************************************************************
File "affine_permutation.py", line 241, in sage.combinat.affine_permutation.AffinePermutation.index_set
Failed example:
    A.index_set()
Expected:
    [0, 1, 2, 3, 4, 5, 6, 7]
Got:
    (0, 1, 2, 3, 4, 5, 6, 7)
**********************************************************************
File "affine_permutation.py", line 2077, in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.index_set
Failed example:
    AffinePermutationGroup(['A',7,1]).index_set()
Expected:
    [0, 1, 2, 3, 4, 5, 6, 7]
Got:
    (0, 1, 2, 3, 4, 5, 6, 7)
**********************************************************************
File "affine_permutation.py", line 2088, in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.reflection_index_set
Failed example:
    AffinePermutationGroup(['A',7,1]).index_set()
Expected:
    [0, 1, 2, 3, 4, 5, 6, 7]
Got:
    (0, 1, 2, 3, 4, 5, 6, 7)
**********************************************************************
3 items had failures:
   1 of   3 in sage.combinat.affine_permutation.AffinePermutation.index_set
   1 of   2 in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.index_set
   1 of   2 in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.reflection_index_set
    [335 tests, 3 failures, 6.17 s]

Did you post an updated patch? I cannot see any mention of affine_permutation in your patch.

Anne

[tscrim]

Here's the fixed patch.

For patchbot:

Apply: trac_14516-crystals_speedup-ts.patch

[aschilling]

Ok, looks good now!

Anne