Opened 7 years ago

Closed 7 years ago

#14516 closed enhancement (fixed)

Refactoring of crystals for speedup

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-5.12
Component: combinatorics Keywords: crystals speedup, days49
Cc: sage-combinat, bsalisbury1, aschilling, nthiery Merged in: sage-5.12.beta1
Authors: Travis Scrimshaw Reviewers: Anne Schilling
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #2023, #14402, #14413, #14143, #12940 Stopgaps:

Description (last modified by 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:

Attachments (3)

trac_14516-crystals_speedup-ts.2.patch (163.0 KB) - added by tscrim 7 years ago.
Forgot to qrefresh…
trac_14516-review-as.patch (1.2 KB) - added by aschilling 7 years ago.
trac_14516-crystals_speedup-ts.patch (165.0 KB) - added by tscrim 7 years ago.

Download all attachments as: .zip

Change History (29)

comment:1 Changed 7 years ago by tscrim

  • Dependencies changed from #14402 #2023 to #14402 #14413 #14143 #2023

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

comment:2 Changed 7 years ago by tscrim

  • Description modified (diff)
  • Status changed from new to needs_review

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]

comment:3 Changed 7 years ago by tscrim

  • Dependencies changed from #14402 #14413 #14143 #2023 to #2023 #14402 #14413 #14143 #14573

comment:4 Changed 7 years ago by tscrim

  • Description modified (diff)

comment:5 Changed 7 years ago by tscrim

  • Dependencies changed from #2023 #14402 #14413 #14143 #14573 to #2023 #14402 #14413 #14143
  • Status changed from needs_review to needs_work

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

comment:6 Changed 7 years ago by tscrim

  • Dependencies changed from #2023 #14402 #14413 #14143 to #2023 #14402 #14413
  • Status changed from needs_work to needs_review

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

comment:7 follow-up: Changed 7 years ago by 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.

Last edited 7 years ago by tscrim (previous) (diff)

comment:8 in reply to: ↑ 7 Changed 7 years ago by aschilling

Hi Travis,

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

Anne

comment:9 Changed 7 years ago by tscrim

  • Dependencies changed from #2023 #14402 #14413 to #2023 #14402 #14413 #14143

@Anne There was some omissions.

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

comment:10 Changed 7 years ago by aschilling

  • Reviewers set to Anne Schilling

comment:11 follow-up: Changed 7 years ago by aschilling

  • Keywords days49 added

comment:12 in reply to: ↑ 11 Changed 7 years ago by 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

comment:13 Changed 7 years ago by tscrim

Done.

comment:14 Changed 7 years ago by aschilling

  • Status changed from needs_review to positive_review

Changed 7 years ago by tscrim

Forgot to qrefresh...

comment:15 Changed 7 years ago by tscrim

  • Description modified (diff)

Forgot to qrefresh.

Apply: trac_14516-crystals_speedup-ts.2.patch

comment:16 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:17 Changed 7 years ago by jferreira

  • Status changed from positive_review to needs_work

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

comment:18 Changed 7 years ago by tscrim

  • Description modified (diff)
  • Status changed from needs_work to positive_review

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

comment:19 Changed 7 years ago by jdemeyer

  • Dependencies changed from #2023 #14402 #14413 #14143 to #2023, #14402, #14413, #14143, #12940
  • Status changed from positive_review to needs_work

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

comment:20 Changed 7 years ago by tscrim

  • Status changed from needs_work to needs_review

Fixed:

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

For patchbot:

Apply: trac_14516-crystals_speedup-ts.patch

comment:21 follow-up: Changed 7 years ago by tscrim

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

comment:22 in reply to: ↑ 21 Changed 7 years ago by 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

Changed 7 years ago by aschilling

comment:23 Changed 7 years ago by aschilling

  • Description modified (diff)
  • Status changed from needs_review to positive_review

Changed 7 years ago by tscrim

comment:24 follow-up: Changed 7 years ago by tscrim

  • Description modified (diff)

Here's the fixed patch.

For patchbot:

Apply: trac_14516-crystals_speedup-ts.patch

comment:25 in reply to: ↑ 24 Changed 7 years ago by aschilling

Ok, looks good now!

Anne

comment:26 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.12.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.