Implement crystal morphisms, subcrystals, and virtual crystals #15463

tscrim · 2013-11-28T07:47:43Z

This implements:

Crystal morphisms (usual, twisted, and virtual).
Subcrystals, so we no long have to do the subset workaround in digraph().
Virtual crystals, so we can now view the elements in the virtual crystal as a crystal graph.

This also reworks DirectSumOfCrystals and TensorProductOfCrystals to make them associative as constructions.

After this, we will be able to do coercions between crystals.

Depends on #15462
Depends on #15882
Depends on #16001
Depends on #18453
Depends on #18722

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

Component: combinatorics

Keywords: crystals, morphisms, subcrystals

Author: Travis Scrimshaw

Branch/Commit: 9f3b7e7

Reviewer: Anne Schilling

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

The text was updated successfully, but these errors were encountered:

sagetrac-git · 2013-11-28T07:49:03Z

Changed commit from 8ad6517 to 5ee50cd

sagetrac-git · 2013-11-28T07:49:03Z

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

`[5ee50cd](https://github.com/sagemath/sagetrac-mirror/commit/5ee50cd)`	`Added trac number to (possible) deprecation.`

tscrim · 2013-11-28T07:50:38Z

comment:2

Also, I'd like to deprecate the method crystal_morphism in place of morphism, but the KR crystals currently use them. In an ideal world, I'd just do a straight replacement of the method, but this might be too drastic of a change...

tscrim · 2013-11-28T07:51:45Z

Dependencies: #15462

nthiery · 2013-11-28T09:10:14Z

comment:5

Replying to @tscrim:

Also, I'd like to deprecate the method crystal_morphism in place of morphism,

I am not sure to have all elements of context for the case at hand, but the name crystal_morphism is a priori better than morphim. For the same reason, we have module_morphism, algebra_morphism etc else where. The point is that if a set has several structures this naming convention avoids conflicts.

anneschilling · 2013-11-28T16:59:48Z

comment:6

You definitely need to give references for similarity techniques and virtual crystals!

tscrim · 2013-11-28T21:11:29Z

comment:7

Replying to @nthiery:

Replying to @tscrim:

Also, I'd like to deprecate the method crystal_morphism in place of morphism,

I am not sure to have all elements of context for the case at hand, but the name crystal_morphism is a priori better than morphim. For the same reason, we have module_morphism, algebra_morphism etc else where. The point is that if a set has several structures this naming convention avoids conflicts.

What would you recommend doing? The output/behavior of the method would radically change, but is that okay? Then should we then move the old functionality into KR crystals to avoid rewriting the promotion functionality there? Thanks.

tscrim · 2014-03-08T17:21:57Z

comment:10

Okay, so I've changed KR crystals to return honest crystal morphisms and made DirectSumOfCrystals into a proper facade parent (when requested). I've also changed morphism() to crystal_morphism() and moved the old function to kirillov_reshetikhin.py in case we want to revive it. I also added references to virtual_crystal.py and had Subcrystal redirect to VirtualCrystal depending on parameters so we could have in the future a more uniform interface with the subcrystal() method.

Here's some timing tests for KR crystals.

The test I ran:

def test_KR(ct, r, s):
    print "construction:"
    %time B = KirillovReshetikhinCrystal(ct, r, s)
    print "TestSuite:"
    %time TestSuite(B).run()
    print "Digraph:"
    %time G = B.digraph()

With the branch:

sage: test_KR(['A',4,1], 3, 2)
construction:
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.04 s
TestSuite:
CPU times: user 2.61 s, sys: 0.09 s, total: 2.70 s
Wall time: 3.21 s
Digraph:
CPU times: user 0.23 s, sys: 0.01 s, total: 0.24 s
Wall time: 0.26 s

sage: test_KR(['D',4,1], 2, 1)
construction:
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s
TestSuite:
CPU times: user 2.07 s, sys: 0.00 s, total: 2.08 s
Wall time: 2.33 s
Digraph:
CPU times: user 0.23 s, sys: 0.01 s, total: 0.24 s
Wall time: 0.27 s

sage: test_KR(['E',6,1], 1, 1)
construction:
CPU times: user 0.19 s, sys: 0.00 s, total: 0.19 s
Wall time: 0.31 s
TestSuite:
CPU times: user 0.57 s, sys: 0.00 s, total: 0.57 s
Wall time: 0.70 s
Digraph:
CPU times: user 0.12 s, sys: 0.02 s, total: 0.14 s
Wall time: 0.16 s

sage: test_KR(['A',6,2], 2, 1)
construction:
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.02 s
TestSuite:
CPU times: user 2.23 s, sys: 0.01 s, total: 2.24 s
Wall time: 2.71 s
Digraph:
CPU times: user 0.24 s, sys: 0.00 s, total: 0.24 s
Wall time: 0.27 s

sage: test_KR(['D',4,2], 2, 1)
construction:
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s
TestSuite:
CPU times: user 2.91 s, sys: 0.02 s, total: 2.92 s
Wall time: 3.36 s
Digraph:
CPU times: user 0.27 s, sys: 0.01 s, total: 0.28 s
Wall time: 0.38 s

sage: K = KirillovReshetikhinCrystal(['D',4,1], 2,2)
sage: %time TestSuite(K).run()
CPU times: user 58.50 s, sys: 0.10 s, total: 58.60 s
Wall time: 70.46 s

Develop:

sage: test_KR(['A',4,1], 3, 2)
construction:
CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 s
Wall time: 0.18 s
TestSuite:
CPU times: user 2.59 s, sys: 0.06 s, total: 2.65 s
Wall time: 3.97 s
Digraph:
CPU times: user 0.23 s, sys: 0.01 s, total: 0.24 s
Wall time: 0.33 s

sage: test_KR(['D',4,1], 2, 1)
construction:
CPU times: user 0.01 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.07 s
TestSuite:
CPU times: user 0.52 s, sys: 0.02 s, total: 0.54 s
Wall time: 0.75 s
Digraph:
CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s
Wall time: 0.12 s

sage: test_KR(['E',6,1], 1, 1)
construction:
CPU times: user 0.01 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.07 s
TestSuite:
CPU times: user 0.45 s, sys: 0.00 s, total: 0.45 s
Wall time: 0.58 s
Digraph:
CPU times: user 0.10 s, sys: 0.01 s, total: 0.11 s
Wall time: 0.12 s

sage: test_KR(['A',6,2], 2, 1)
construction:
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.09 s
TestSuite:
CPU times: user 0.64 s, sys: 0.02 s, total: 0.65 s
Wall time: 0.86 s
Digraph:
CPU times: user 0.21 s, sys: 0.00 s, total: 0.21 s
Wall time: 0.28 s

sage: test_KR(['D',4,2], 2, 1)
construction:
CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s
TestSuite:
CPU times: user 0.38 s, sys: 0.01 s, total: 0.39 s
Wall time: 0.50 s
Digraph:
CPU times: user 0.12 s, sys: 0.01 s, total: 0.13 s
Wall time: 0.28 s

sage: K = KirillovReshetikhinCrystal(['D',4,1], 2,2)
sage: %time TestSuite(K).run()
CPU times: user 5.30 s, sys: 0.02 s, total: 5.32 s
Wall time: 6.30 s

So there's a major speed penality with using promotion as a crystal morphism directly. My guess is caused from the fact we are no longer caching things. On develop we have:

sage: K = KirillovReshetikhinCrystal(['D',4,1], 2,2)
sage: K.promotion()
Cached version of <function morphism at 0xc77133c>

So I have a the following questions:

1 - The code and the documentation for the old crystal_morphism() did not match as the default was to not cache (i.e. cache = False but the code did return a cached function when the cache argument was False. Do we want to cache the output of the promotion (or something else that's related)?

2 - Do we want to use honest crystal morphisms or use the old function returned from the old crystal_morphism()?

3 - Do we want to have an option to cache the output of a crystal morphism, or morphisms in general?

sagetrac-git · 2014-03-08T17:22:25Z

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

`f7d7f4f`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`
`ba6ceaa`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`
`853c787`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`
`7f006e8`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`
`9d8c0f5`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`
`3d3b27c`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`
`52b6524`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`
`16e367f`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`
`6473b13`	`Finalizing patch for review.`

sagetrac-git · 2014-03-08T17:22:25Z

Changed commit from 5ee50cd to 6473b13

sagetrac-git · 2014-04-02T01:31:15Z

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

`bef4b96`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`
`f28634e`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`
`a8314d9`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`

sagetrac-git · 2014-04-02T01:31:15Z

Changed commit from 6473b13 to a8314d9

sagetrac-git · 2014-04-09T02:05:00Z

Changed commit from a8314d9 to c264447

sagetrac-git · 2014-04-09T02:05:00Z

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

`c264447`	`Merge branch 'develop' into public/combinat/crystals/crystal_morphisms`

sagetrac-git · 2014-04-12T14:33:42Z

Changed commit from c264447 to 639ea0f

sagetrac-git · 2014-04-12T14:33:42Z

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

`dc1200f`	`Implemented promotion morphism.`
`639ea0f`	`Added specialized promotion map for KR crystals.`

tscrim · 2014-04-13T04:27:29Z

Changed dependencies from #15462 to #15462 #15882

tscrim · 2014-04-13T04:27:29Z

comment:15

With the new custom promotion map, I actually get a speedup when running the test suite except with the twisted types -- most likely from the maps to/from the ambient type which aren't cached as well:

sage: test_KR(['A',4,1], 3, 2)
construction
CPU times: user 36 ms, sys: 4 ms, total: 40 ms
Wall time: 40.1 ms
TestSuite:
CPU times: user 1.1 s, sys: 36 ms, total: 1.13 s
Wall time: 1.15 s
Digraph:
CPU times: user 144 ms, sys: 4 ms, total: 148 ms
Wall time: 164 ms
sage: test_KR(['A',4,1], 3, 2)
construction
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 240 µs
TestSuite:
CPU times: user 708 ms, sys: 24 ms, total: 732 ms
Wall time: 712 ms
Digraph:
CPU times: user 180 ms, sys: 4 ms, total: 184 ms
Wall time: 207 ms
sage: test_KR(['D',4,1], 2, 1)
construction
CPU times: user 24 ms, sys: 4 ms, total: 28 ms
Wall time: 26.5 ms
TestSuite:
CPU times: user 412 ms, sys: 0 ns, total: 412 ms
Wall time: 421 ms
Digraph:
CPU times: user 112 ms, sys: 4 ms, total: 116 ms
Wall time: 126 ms
sage: test_KR(['E',6,1], 1, 1)
construction
CPU times: user 124 ms, sys: 8 ms, total: 132 ms
Wall time: 132 ms
TestSuite:
CPU times: user 232 ms, sys: 0 ns, total: 232 ms
Wall time: 234 ms
Digraph:
CPU times: user 104 ms, sys: 8 ms, total: 112 ms
Wall time: 124 ms
sage: test_KR(['A',6,2], 2, 1)
construction
CPU times: user 12 ms, sys: 4 ms, total: 16 ms
Wall time: 15.3 ms
TestSuite:
CPU times: user 1.2 s, sys: 8 ms, total: 1.2 s
Wall time: 1.23 s
Digraph:
CPU times: user 184 ms, sys: 4 ms, total: 188 ms
Wall time: 200 ms
sage: test_KR(['D',4,2], 2, 1)
construction
CPU times: user 8 ms, sys: 4 ms, total: 12 ms
Wall time: 11 ms
TestSuite:
CPU times: user 1.02 s, sys: 8 ms, total: 1.03 s
Wall time: 1.05 s
Digraph:
CPU times: user 164 ms, sys: 4 ms, total: 168 ms
Wall time: 176 ms
sage: test_KR(['D',4,1], 2, 2)
construction
CPU times: user 20 ms, sys: 0 ns, total: 20 ms
Wall time: 17.7 ms
TestSuite:
CPU times: user 4.07 s, sys: 4 ms, total: 4.07 s
Wall time: 4.08 s
Digraph:
CPU times: user 328 ms, sys: 4 ms, total: 332 ms
Wall time: 344 ms

Before:

sage: test_KR(['A',4,1], 3, 2)
construction
CPU times: user 32 ms, sys: 0 ns, total: 32 ms
Wall time: 128 ms
TestSuite:
CPU times: user 2.88 s, sys: 72 ms, total: 2.95 s
Wall time: 3.54 s
Digraph:
CPU times: user 236 ms, sys: 8 ms, total: 244 ms
Wall time: 253 ms

sage: test_KR(['D',4,1], 2, 1)
construction
CPU times: user 20 ms, sys: 4 ms, total: 24 ms
Wall time: 58.2 ms
TestSuite:
CPU times: user 528 ms, sys: 12 ms, total: 540 ms
Wall time: 602 ms
Digraph:
CPU times: user 104 ms, sys: 4 ms, total: 108 ms
Wall time: 121 ms

sage: test_KR(['E',6,1], 1, 1)
construction
CPU times: user 28 ms, sys: 8 ms, total: 36 ms
Wall time: 47.7 ms
TestSuite:
CPU times: user 424 ms, sys: 16 ms, total: 440 ms
Wall time: 445 ms
Digraph:
CPU times: user 96 ms, sys: 24 ms, total: 120 ms
Wall time: 128 ms

sage: test_KR(['A',6,2], 2, 1)
construction
CPU times: user 20 ms, sys: 0 ns, total: 20 ms
Wall time: 97.4 ms
TestSuite:
CPU times: user 716 ms, sys: 16 ms, total: 732 ms
Wall time: 762 ms
Digraph:
CPU times: user 168 ms, sys: 8 ms, total: 176 ms
Wall time: 189 ms

sage: test_KR(['D',4,2], 2, 1)
construction
CPU times: user 12 ms, sys: 0 ns, total: 12 ms
Wall time: 11.3 ms
TestSuite:
CPU times: user 404 ms, sys: 28 ms, total: 432 ms
Wall time: 480 ms
Digraph:
CPU times: user 124 ms, sys: 8 ms, total: 132 ms
Wall time: 170 ms

sage: test_KR(['D',4,1], 2, 2)
construction
CPU times: user 16 ms, sys: 4 ms, total: 20 ms
Wall time: 18 ms
TestSuite:
CPU times: user 5.08 s, sys: 12 ms, total: 5.1 s
Wall time: 5.13 s
Digraph:
CPU times: user 312 ms, sys: 4 ms, total: 316 ms
Wall time: 328 ms

Now to merge with #15882 and do some work on the doc and make all tests pass.

sagetrac-git · 2014-04-13T06:47:15Z

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`6328bf0`	`Reworked the entry points to KR crystals.`
`a7f2e1e`	`Moved the KR RiggedConfigurations to rigged_configurations.py.`
`8120e16`	`Merge branch 'public/combinat/crystals/catalog' of trac.sagemath.org:sage into public/combinat/crystals/catalog-15882`
`e67176e`	`More changes to the catalog.`
`482ca9c`	`Fixed last bad link.`
`6402c54`	`fixed some documentation issues`
`a596cdd`	`Merge branch 'public/combinat/crystals/catalog' of trac.sagemath.org:sage into public/combinat/crystals/catalog-15882`
`698ae7e`	`some small changes to the documentation`
`dd7b2c5`	`Merge branch 'public/combinat/crystals/catalog' into public/combinat/crystals/crystal_morphisms`
`8608c8f`	`Fixes from the merge.`

sagetrac-git · 2014-04-13T06:47:15Z

Changed commit from 639ea0f to 8608c8f

sagetrac-git · 2015-07-13T11:48:05Z

Changed commit from 2841c18 to cb16f86

anneschilling · 2015-07-13T11:54:01Z

comment:74

Ok, looks good now!

anneschilling · 2015-07-13T11:54:31Z

Reviewer: Anne Schilling

tscrim · 2015-07-13T11:55:04Z

comment:76

Thank you!

vbraun · 2015-07-13T20:59:26Z

comment:77

Tests fail

sagetrac-git · 2015-07-13T23:22:43Z

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

`c0a522b`	Fixing trivial failing doctests due to added `__lt__` for subcrystal elements.
`f35e708`	`Merge branch 'public/combinat/crystals/crystal_morphisms' of trac.sagemath.org:sage into public/combinat/crystals/crystal_morphisms`

sagetrac-git · 2015-07-13T23:22:43Z

Changed commit from cb16f86 to f35e708

tscrim · 2015-07-13T23:27:16Z

comment:79

Trivial failures because the elements for subcrystals are now ordered by the __lt__ added.

vbraun · 2015-07-14T22:37:31Z

comment:80

Some # long time tests still fail

tscrim · 2015-07-14T23:32:05Z

comment:81

So the issue is in rigged_configurations/bij_infinity.py where we test elements in a subcrystal, whose elements are no longer elements in the crystal and there is no coercion map from the subcrystal to the ambient crystal. I'm working on implementing the coercion.

sagetrac-git · 2015-07-15T00:19:49Z

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

`9f3b7e7`	`Fixing doctests and minor tweak to subcrystal construction.`

sagetrac-git · 2015-07-15T00:19:49Z

Changed commit from f35e708 to 9f3b7e7

tscrim · 2015-07-15T00:21:13Z

comment:83

So implementing the coercion and getting those tests to work seems to be a minor can of worms. Instead I just changed the tests to work (and they are still testing what they should be).

anneschilling · 2015-07-15T01:29:07Z

comment:85

Tests pass for me now!

anneschilling · 2015-07-15T01:29:26Z

comment:86

Tests pass for me now!

vbraun · 2015-07-27T15:15:58Z

Changed branch from public/combinat/crystals/crystal_morphisms to 9f3b7e7

tscrim added this to the sage-6.0 milestone Nov 28, 2013

tscrim added c: combinatorics labels Nov 28, 2013

tscrim assigned sagetrac-sage-combinat Nov 28, 2013

tscrim added the s: needs review label Nov 28, 2013

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.0, sage-6.1 Dec 17, 2013

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

anneschilling added s: positive review and removed s: needs review labels Jul 13, 2015

vbraun added s: needs work and removed s: positive review labels Jul 13, 2015

tscrim added s: positive review and removed s: needs work labels Jul 13, 2015

vbraun added s: needs work and removed s: positive review labels Jul 14, 2015

tscrim added s: needs review and removed s: needs work labels Jul 15, 2015

anneschilling added s: positive review and removed s: needs review labels Jul 15, 2015

vbraun removed the s: positive review label Jul 27, 2015

vbraun closed this as completed in f1e2907 Jul 27, 2015

Implement crystal morphisms, subcrystals, and virtual crystals #15463

Implement crystal morphisms, subcrystals, and virtual crystals #15463

Comments

tscrim commented Nov 28, 2013

sagetrac-git mannequin commented Nov 28, 2013

sagetrac-git mannequin commented Nov 28, 2013

tscrim commented Nov 28, 2013

tscrim commented Nov 28, 2013

nthiery commented Nov 28, 2013

anneschilling commented Nov 28, 2013

tscrim commented Nov 28, 2013

tscrim commented Mar 8, 2014

sagetrac-git mannequin commented Mar 8, 2014

sagetrac-git mannequin commented Mar 8, 2014

sagetrac-git mannequin commented Apr 2, 2014

sagetrac-git mannequin commented Apr 2, 2014

sagetrac-git mannequin commented Apr 9, 2014

sagetrac-git mannequin commented Apr 9, 2014

sagetrac-git mannequin commented Apr 12, 2014

sagetrac-git mannequin commented Apr 12, 2014

tscrim commented Apr 13, 2014

tscrim commented Apr 13, 2014

sagetrac-git mannequin commented Apr 13, 2014

sagetrac-git mannequin commented Apr 13, 2014

sagetrac-git mannequin commented Jul 13, 2015

anneschilling commented Jul 13, 2015

anneschilling commented Jul 13, 2015

tscrim commented Jul 13, 2015

vbraun commented Jul 13, 2015

sagetrac-git mannequin commented Jul 13, 2015

sagetrac-git mannequin commented Jul 13, 2015

tscrim commented Jul 13, 2015

vbraun commented Jul 14, 2015

tscrim commented Jul 14, 2015

sagetrac-git mannequin commented Jul 15, 2015

sagetrac-git mannequin commented Jul 15, 2015

tscrim commented Jul 15, 2015

anneschilling commented Jul 15, 2015

anneschilling commented Jul 15, 2015

vbraun commented Jul 27, 2015