Speed improvements in affine crystals and fix of optional doctest failure

[anneschilling]

This patch caches all methods in KirillovReshetikhin crystals that compute crystal morphisms. This yields a significant speed-up of all methods involving the affine crystal operators.

With the patch applied:

sage: K = KirillovReshetikhinCrystal(['C',3,1],1,1)
sage: L = KirillovReshetikhinCrystal(['C',3,1],2,2)
sage: %timeit f = K.R_matrix(L)
5 loops, best of 3: 3.86 s per loop

Without the patch applied:

Loading Sage library. Current Mercurial branch is: combinat
sage: K = KirillovReshetikhinCrystal(['C',3,1],1,1)
sage: sage: L = KirillovReshetikhinCrystal(['C',3,1],2,2)
sage: sage: %timeit f = K.R_matrix(L)
5 loops, best of 3: 96.2 s per loop

It also fixes a doctest failure in /category/crystals.py

sage -t --optional crystals.py
sage -t --optional "devel/sage-combinat/sage/categories/crystals.py"
**********************************************************************
File "/Applications/sage-5.6/devel/sage-combinat/sage/categories/crystals.py", line 603:
    sage: T._latex_()   #optional - dot2tex
Expected nothing
Got:
    '\n\\begin{tikzpicture}[>=latex,line join=bevel,]\n%%\n\\node (1) at (8bp,162bp) [draw,draw=none] {${\\def\\lr#1{\\multicolumn{1}{|@{\\hspace{.6ex}}c@{\\hspace{.6ex}}|}{\\raisebox{-.3ex}{$#1$}}}\\raisebox{-.6ex}{$\\begin{array}[b]{c}\\cline{1-1}\\lr{1}\\\\\\cline{1-1}\\end{array}$}}$};\n  \\node (3) at (8bp,10bp) [draw,draw=none] {${\\def\\lr#1{\\multicolumn{1}{|@{\\hspace{.6ex}}c@{\\hspace{.6ex}}|}{\\raisebox{-.3ex}{$#1$}}}\\raisebox{-.6ex}{$\\begin{array}[b]{c}\\cline{1-1}\\lr{3}\\\\\\cline{1-1}\\end{array}$}}$};\n  \\node (2) at (8bp,86bp) [draw,draw=none] {${\\def\\lr#1{\\multicolumn{1}{|@{\\hspace{.6ex}}c@{\\hspace{.6ex}}|}{\\raisebox{-.3ex}{$#1$}}}\\raisebox{-.6ex}{$\\begin{array}[b]{c}\\cline{1-1}\\lr{2}\\\\\\cline{1-1}\\end{array}$}}$};\n  \\draw [blue,->] (1) ..controls (8bp,140.79bp) and (8bp,121.03bp)  .. (2);\n  \\definecolor{strokecol}{rgb}{0.0,0.0,0.0};\n  \\pgfsetstrokecolor{strokecol}\n  \\draw (17bp,124bp) node {$1$};\n  \\draw [red,->] (2) ..controls (8bp,64.789bp) and (8bp,45.027bp)  .. (3);\n  \\draw (17bp,48bp) node {$2$};\n%\n\\end{tikzpicture}\n'
**********************************************************************
File "/Applications/sage-5.6/devel/sage-combinat/sage/categories/crystals.py", line 610:
    sage: T._latex_(color_by_label = {0:"black", 1:"red", 2:"blue"})   #optional - dot2tex graphviz
Expected nothing
Got:
    '\n\\begin{tikzpicture}[>=latex,line join=bevel,]\n%%\n\\node (1) at (8bp,162bp) [draw,draw=none] {${\\def\\lr#1{\\multicolumn{1}{|@{\\hspace{.6ex}}c@{\\hspace{.6ex}}|}{\\raisebox{-.3ex}{$#1$}}}\\raisebox{-.6ex}{$\\begin{array}[b]{c}\\cline{1-1}\\lr{1}\\\\\\cline{1-1}\\end{array}$}}$};\n  \\node (3) at (8bp,10bp) [draw,draw=none] {${\\def\\lr#1{\\multicolumn{1}{|@{\\hspace{.6ex}}c@{\\hspace{.6ex}}|}{\\raisebox{-.3ex}{$#1$}}}\\raisebox{-.6ex}{$\\begin{array}[b]{c}\\cline{1-1}\\lr{3}\\\\\\cline{1-1}\\end{array}$}}$};\n  \\node (2) at (8bp,86bp) [draw,draw=none] {${\\def\\lr#1{\\multicolumn{1}{|@{\\hspace{.6ex}}c@{\\hspace{.6ex}}|}{\\raisebox{-.3ex}{$#1$}}}\\raisebox{-.6ex}{$\\begin{array}[b]{c}\\cline{1-1}\\lr{2}\\\\\\cline{1-1}\\end{array}$}}$};\n  \\draw [red,->] (1) ..controls (8bp,140.79bp) and (8bp,121.03bp)  .. (2);\n  \\definecolor{strokecol}{rgb}{0.0,0.0,0.0};\n  \\pgfsetstrokecolor{strokecol}\n  \\draw (17bp,124bp) node {$1$};\n  \\draw [blue,->] (2) ..controls (8bp,64.789bp) and (8bp,45.027bp)  .. (3);\n  \\draw (17bp,48bp) node {$2$};\n%\n\\end{tikzpicture}\n'

Depends on #14052

CC: @sagetrac-sage-combinat @nthiery @tscrim

Component: combinatorics

Keywords: crystals, days45

Author: Anne Schilling

Reviewer: Nicolas M. Thiery, Travis Scrimshaw

Merged: sage-5.8.beta0

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

[anneschilling]

comment:2

Attachment: trac_14089-crystal-speed-up-as.patch.gz

[tscrim]

comment:3

Does this also speed up the type ['D', n, 1] spin KR crystals (right now they take a long time because promotion_on_highest_weight_vectors() iterates over the entire crystal and is called 3 times)?

Also, for the index_set() method in categories/crystals.py, could we change it so that it returns self._cartan_type.index_set()? It seems that CrystalOfTableaux is the only crystal which directly implements cartan_matrix() and does not have the _cartan_matrix attribute. This seems to drop the number of function calls when iterating over crystals by about 10%.

Thanks,

Travis

[anneschilling]

comment:4

Replying to @tscrim:

Does this also speed up the type ['D', n, 1] spin KR crystals (right now they take a long time because promotion_on_highest_weight_vectors() iterates over the entire crystal and is called 3 times)?

Yes, they should all be faster now. Before the patch

sage: K = KirillovReshetikhinCrystal(['D',4,1],4,1)
sage: L = KirillovReshetikhinCrystal(['D',4,1],3,1)
sage: %timeit L.R_matrix(K)
5 loops, best of 3: 186 ms per loop
sage: L = KirillovReshetikhinCrystal(['D',4,1],3,3)
sage: %timeit L.R_matrix(K)
5 loops, best of 3: 8.54 s per loop

After the patch

sage: K = KirillovReshetikhinCrystal(['D',4,1],4,1)
sage: L = KirillovReshetikhinCrystal(['D',4,1],3,1)
sage: %timeit L.R_matrix(K)
5 loops, best of 3: 763 ns per loop
sage: L = KirillovReshetikhinCrystal(['D',4,1],3,3)
sage: %timeit L.R_matrix(K)
5 loops, best of 3: 811 ns per loop

Also, for the index_set() method in categories/crystals.py, could we change it so that it returns self._cartan_type.index_set()? It seems that CrystalOfTableaux is the only crystal which directly implements cartan_matrix() and does not have the _cartan_matrix attribute. This seems to drop the number of function calls when iterating over crystals by about 10%.

I can cache index_set, which should make it faster.

Best,

Anne

[anneschilling]

comment:5

Also, for the index_set() method in categories/crystals.py, could we change it so that it returns self._cartan_type.index_set()? It seems that CrystalOfTableaux is the only crystal which directly implements cartan_matrix() and does not have the _cartan_matrix attribute. This seems to drop the number of function calls when iterating over crystals by about 10%.

I can cache index_set, which should make it faster.

In fact, this breaks some doc tests since caching an object that is not immutable is dangerous. Unless there is really a significant speedup, I won't make this change for now.

Anne

[tscrim]

comment:6

Sorry, I wasn't specific enough. I meant their creation. I did some tests now that I have the patch (I wrote that comment last night before you had posted the patch).

Before patch:

sage: %time C = KirillovReshetikhinCrystal(['D',4,1], 3,3)
CPU times: user 4.89 s, sys: 0.41 s, total: 5.30 s
Wall time: 5.90 s

After patch:

sage: %time C = KirillovReshetikhinCrystal(['D',4,1], 3,3)
CPU times: user 2.11 s, sys: 0.28 s, total: 2.39 s
Wall time: 4.27 s

So it does help, but they still take a long time to initialize compared to their counterparts. However this can be an issue for another ticket.

As for the caching of the index_set(), the problem is (as you stated) this returns a mutable list rather than an immutable tuple. I tried doing this once and from what I recall, the rigged configurations code broke because it does something like

I = self.index_set()
I.pop(0)

which would have to be tweaked to

I = self.index_set()[1:]

but IDK if this behavior occurs anywhere else.

Thanks,

Travis

[anneschilling]

comment:7

So it does help, but they still take a long time to initialize compared to their counterparts. However this can be an issue for another ticket.

Unless you have a specific suggestion on how to improve this, I would leave it for another ticket.

As for the caching of the index_set(), the problem is (as you stated) this returns a mutable list rather than an immutable tuple. I tried doing this once and from what I recall, the rigged configurations code broke because it does something like

I = self.index_set()
I.pop(0)

which would have to be tweaked to

I = self.index_set()[1:]

but IDK if this behavior occurs anywhere else.

Yes, this also occurs in tensor_product in /combinat/crystals

Anne

[nthiery]

comment:8

As for the caching of the index_set(), the problem is (as you stated) this returns a mutable list rather than an immutable tuple. I tried doing this once and from what I recall, the rigged configurations code broke because it does something like

I = self.index_set()
I.pop(0)

which would have to be tweaked to

I = self.index_set()[1:]

Or just: self.cartan_type().classical().index_set() (which would
by the way be safer w.r.t. affine types where the special node would
not be 0).

[tscrim]

comment:9

Replying to @anneschilling:

So it does help, but they still take a long time to initialize compared to their counterparts. However this can be an issue for another ticket.

Unless you have a specific suggestion on how to improve this, I would leave it for another ticket.

Not at present.

Replying to @nthiery:

Or just: self.cartan_type().classical().index_set() (which would by the way be safer w.r.t. affine types where the special node would not be 0).

Yes, that does seem safer.

Best,

Travis

[tscrim]

comment:10

Looks good to me as well.

[tscrim]

Changed reviewer from Nicolas M. Thiery to Nicolas M. Thiery, Travis Scrimshaw

[anneschilling]

comment:11

Replying to @tscrim:

Looks good to me as well.

Thank you!

Anne

[anneschilling]

Changed keywords from crystals to crystals, days45

[jdemeyer]

Merged: sage-5.8.beta0