Use permutation implementation of Weyl groups to compute LS path energy

[tscrim]

Basically all of the time is spent creating the parabolic quantum Bruhat graph.

This is an implementation detail, so let's use the fastest version of the Weyl group to compute the parabolic quantum Bruhat graph.

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

Component: combinatorics

Keywords: crystals, energy function

Author: Travis Scrimshaw

Branch/Commit: 8ae3722

Reviewer: Ben Salisbury

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

[tscrim]

Branch: public/crystals/faster_ls_path_energy-22994

[tscrim]

Commit: c71c40d

[tscrim]

comment:1

With branch:

sage: %time [mg.energy_function() for mg in B.module_generators]
CPU times: user 72 ms, sys: 4 ms, total: 76 ms
Wall time: 71.2 ms
[0]
sage: La = RootSystem(['E',6,1]).weight_space().fundamental_weights()
sage: B = crystals.ProjectedLevelZeroLSPaths(La[3])
sage: %time [mg.energy_function() for mg in B.module_generators]
CPU times: user 288 ms, sys: 16 ms, total: 304 ms
Wall time: 281 ms
[0]

Before:

sage: La = RootSystem(['D',5,1]).weight_space().fundamental_weights()
sage: B = crystals.ProjectedLevelZeroLSPaths(La[3])
sage: %time [mg.energy_function() for mg in B.module_generators]
CPU times: user 1.5 s, sys: 60 ms, total: 1.56 s
Wall time: 1.61 s
[0]
sage: La = RootSystem(['E',6,1]).weight_space().fundamental_weights()
sage: B = crystals.ProjectedLevelZeroLSPaths(La[3])
sage: %time [mg.energy_function() for mg in B.module_generators]
CPU times: user 16.9 s, sys: 20 ms, total: 16.9 s
Wall time: 16.9 s
[0]

(Be warned, you might also have the GAP startup time in the initial computation.)

---

New commits:

c71c40d

Using faster Weyl group implementation for energy in LS paths.

[sagetrac-git]

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

90cda5e

Iterate over the weight's orbit as we may not need the full list.

[sagetrac-git]

Changed commit from c71c40d to 90cda5e

[tscrim]

comment:3

I found some more speed by iterating over the weight orbit rather than building the full list:

sage: La = RootSystem(['E',7,1]).weight_space().fundamental_weights()
sage: B = crystals.ProjectedLevelZeroLSPaths(La[4])
sage: %time [mg.energy_function() for mg in B.module_generators]
CPU times: user 10.3 s, sys: 52 ms, total: 10.3 s
Wall time: 10.4 s
[0]

vs old:

sage: %time [mg.energy_function() for mg in B.module_generators]
CPU times: user 10.3 s, sys: 52 ms, total: 10.3 s
Wall time: 12.1 s
[0]

[bsalisbury1]

Reviewer: Ben Salisbury

[bsalisbury1]

comment:4

All documentation builds (both PDF and HTML) on my machine, but here is the output of make ptestalllong:

----------------------------------------------------------------------
sage -t --long --warn-long 41.4 src/sage/combinat/root_system/non_symmetric_macdonald_polynomials.py  # 7 doctests failed
sage -t --long --warn-long 41.4 src/sage/plot/plot.py  # 1 doctest failed
sage -t --long --warn-long 41.4 src/sage/plot/graphics.py  # 2 doctests failed
sage -t --long --warn-long 41.4 src/sage/combinat/root_system/root_lattice_realizations.py  # 13 doctests failed
sage -t --long --warn-long 41.4 src/sage/tests/book_schilling_zabrocki_kschur_primer.py  # 5 doctests failed
sage -t --long --warn-long 41.4 src/sage/tests/cmdline.py  # 9 doctests failed
sage -t --long --warn-long 41.4 src/sage/combinat/sf/k_dual.py  # 22 doctests failed
sage -t --long --warn-long 41.4 src/sage/combinat/root_system/pieri_factors.py  # 56 doctests failed
sage -t --long --warn-long 41.4 src/sage/combinat/crystals/affine_factorization.py  # 58 doctests failed
sage -t --long --warn-long 41.4 src/sage/categories/weyl_groups.py  # 26 doctests failed
sage -t --long --warn-long 41.4 src/sage/algebras/nil_coxeter_algebra.py  # 4 doctests failed
sage -t --long --warn-long 41.4 src/sage/combinat/sf/sf.py  # 1 doctest failed
sage -t --long --warn-long 41.4 src/sage/combinat/root_system/weyl_characters.py  # 9 doctests failed
sage -t --long --warn-long 41.4 src/sage/repl/rich_output/pretty_print.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 6648.5 seconds
    cpu time: 11823.2 seconds
    cumulative wall time: 25930.4 seconds

[sagetrac-git]

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

aaaa56d	I need to actually call the function...
d800645	Use the iterator in the other internal place orbit() is used.

[sagetrac-git]

Changed commit from 90cda5e to d800645

[tscrim]

comment:6

facepalm I need to actually call the iterator function. I also used it in two other places where I could.

[bsalisbury1]

comment:7

Everything looks good now (at least on my machine).

[fchapoton]

comment:8

"it as 6 elements" ?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

8ae3722

Fixing typo.

[sagetrac-git]

Changed commit from d800645 to 8ae3722

[tscrim]

comment:10

Didn't even notice it because I wasn't really reading it. Fixed, and I'm allowing myself to reset to positive review because it is a trivial change.

[vbraun]

Changed branch from public/crystals/faster_ls_path_energy-22994 to 8ae3722