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:

• attachment: trac_14516-crystals_speedup-ts.patch

Depends on #2023
Depends on #14402
Depends on #14413
Depends on #14143
Depends on #12940

CC: @sagetrac-sage-combinat @bsalisbury1 @anneschilling @nthiery

Component: combinatorics

Keywords: crystals speedup, days49

Author: Travis Scrimshaw

Reviewer: Anne Schilling

Merged: sage-5.12.beta1

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

[tscrim]

Changed dependencies from #14402 #2023 to #14402 #14413 #14143 #2023

[tscrim]

comment:1

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]

comment:2

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]

Changed dependencies from #14402 #14413 #14143 #2023 to #2023 #14402 #14413 #14143 #14573

[tscrim]

comment:5

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

[tscrim]

Changed dependencies from #2023 #14402 #14413 #14143 #14573 to #2023 #14402 #14413 #14143

[tscrim]

Changed dependencies from #2023 #14402 #14413 #14143 to #2023 #14402 #14413

[tscrim]

comment:6

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]

comment:7

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.

[anneschilling]

comment:8

Hi Travis,

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

Anne

[tscrim]

Changed dependencies from #2023 #14402 #14413 to #2023 #14402 #14413 #14143

[tscrim]

comment:9

@anneschilling There was some omissions.

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

[anneschilling]

Reviewer: Anne Schilling

[anneschilling]

Changed keywords from crystals speedup to crystals speedup, days49

[anneschilling]

comment:12

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]

comment:13

Done.

[jdemeyer]

Changed dependencies from #2023 #14402 #14413 #14143 to #2023, #14402, #14413, #14143, #12940

[jdemeyer]

comment:19

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]

comment:20

Fixed:

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

For patchbot:

Apply: trac_14516-crystals_speedup-ts.patch

[tscrim]

comment:21

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

[anneschilling]

comment:22

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

[anneschilling]

Attachment: trac_14516-review-as.patch.gz

[tscrim]

comment:24

Attachment: trac_14516-crystals_speedup-ts.patch.gz

Here's the fixed patch.

For patchbot:

Apply: trac_14516-crystals_speedup-ts.patch

[anneschilling]

comment:25

Ok, looks good now!

Anne

[jdemeyer]

Merged: sage-5.12.beta1