Speedup creation of Kleber tree

[tscrim]

Currently, generating the first level of the Kleber tree grows poorly as the rank and the complexity of the root system increases. This is due to the fact that it uses all positive roots. Instead we use integral points (when expressed as simple roots) in the intersection of the negative root cone and a shifted positive weight cone.

Also due to the number of operations involved, this ticket changes all lower levels to use the polytope enumeration for small rank unless normaliz is available.

Depends on #22938

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

Component: combinatorics

Keywords: rigged configurations, kleber tree

Author: Travis Scrimshaw

Branch/Commit: 5aafe4e

Reviewer: Ben Salisbury

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

[tscrim]

Commit: f9da27b

[tscrim]

Branch: public/rigged_configurations/speedup_kleber_tree-19075

[tscrim]

comment:1

With the branch, we have (on SMC):

sage: %time RiggedConfigurations(['E',8,1], [[8,1]]).module_generators
CPU times: user 384 ms, sys: 80 ms, total: 464 ms
Wall time: 430 ms

whereas previously this took

sage: %time RiggedConfigurations(['E',8,1], [[8,1]]).module_generators
CPU times: user 23.9 s, sys: 72 ms, total: 24 s
Wall time: 24.5 s

As an added benefit, this allows us to combine the children iterators into a single method.

---

New commits:

f9da27b

Generate the Kleber tree by using integral points in a polytope.

[tscrim]

comment:2

To note, from looking over the profiling data, the majority of time is devoted to doing arithmetic using combinatorial free modules and just taking so long due to the sheer number of calculations.

It seems like on small rank, this is slower change is ~3-5x slower:

sage: RC = RiggedConfigurations(['D',4,1], [[4,2], [1,3], [2,4]])
sage: %time len(RC.module_generators)
CPU times: user 928 ms, sys: 84 ms, total: 1.01 s
Wall time: 1.47 s
586

vs the current version:

sage: %time len(RC.module_generators)
CPU times: user 340 ms, sys: 4 ms, total: 344 ms
Wall time: 348 ms
586

But for larger rank, it still is faster:

sage: RC = RiggedConfigurations(['D',8,1], [[4,2], [1,3], [2,4]])
sage: %time len(RC.module_generators)
CPU times: user 38.4 s, sys: 148 ms, total: 38.6 s
Wall time: 40.7 s
19234

vs I didn't have the patience to wait.

More data:

sage: RC = RiggedConfigurations(['D',6,1], [[4,6]])
sage: %time len(RC.module_generators)
CPU times: user 392 ms, sys: 56 ms, total: 448 ms
Wall time: 648 ms
28

previous:

sage: %time len(RC.module_generators)
CPU times: user 1.46 s, sys: 0 ns, total: 1.46 s
Wall time: 1.52 s
28

For F₄⁽¹⁾, I get the new version is 2-20x faster for B^i,1, where i = 1,2,3,4.

The question then becomes should we deal with the slowdown in small ranks, or keep both algorithms and have a heuristic which chooses between the two?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f9da27b to 05c24f3

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ecdaf6c	Initial ground work and \delta map.
0b0ccde	Added reverse bijection for B^{1,1} of E_6^{(1)}.
6298f70	Fixing type B bijection.
52140d4	Fixing all of the problems from the refactoring of RC -> KRT bijection.
135648e	Doing some more refactoring and doing some work for E_{6,7}.
3166a99	Finalizing E_{6,7}^{(1)} bijection and fixing a doctest from the refactoring.
05c24f3	Merge branch 'public/rigged_configurations/speedup_kleber_tree-19075' of trac.sagemath.org:sage into public/rigged_configurations/speedup_kleber_tree-19075

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 05c24f3 to 7de002b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7de002b

Generate the Kleber tree by using integral points in a polytope.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0f28d76	Merge branch 'public/rigged_configurations/speedup_kleber_tree-19075' of trac.sagemath.org:sage into public/rigged_configurations/speedup_kleber_tree-19075
98a0406	Converting to weight/root lattice and using the old method for types A and D.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7de002b to 98a0406

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 98a0406 to 33af86e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

33af86e

Tweak the conditions for switching between algorithms just in terms of the rank.

[tscrim]

comment:8

From doing some more testing, as soon as the rank hits 7, the children iterator by using integer points of polytopes is faster than going over all possible up roots. I'm fairly certain this will hold true for all cases as this was true for even small examples in type A (the use_uproot was just an extra parameter I added for testing):

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree
sage: %time K = KleberTree(['A',7,1], [[1,6],[1,1]], use_uproot=True)
CPU times: user 51.3 ms, sys: 8.19 ms, total: 59.5 ms
Wall time: 56.4 ms
sage: %time K = KleberTree(['A',7,1], [[1,6],[1,1]], use_uproot=False)
CPU times: user 14.6 ms, sys: 695 µs, total: 15.3 ms
Wall time: 13.4 ms
sage: %time K = KleberTree(['A',7,1], [[1,3],[1,1]], use_uproot=True)
CPU times: user 12.6 ms, sys: 139 µs, total: 12.8 ms
Wall time: 11.2 ms
sage: %time K = KleberTree(['A',7,1], [[1,3],[1,1]], use_uproot=False)
CPU times: user 8.66 ms, sys: 182 µs, total: 8.84 ms
Wall time: 8.12 ms

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

99c26b0	Merge branch 'public/rigged_configurations/speedup_kleber_tree-19075' of trac.sagemath.org:sage into public/rigged_configurations/speedup_kleber_tree-19075
1f333b8	Use normaliz when available.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 33af86e to 1f333b8

[tscrim]

comment:10

This is blazingly fast with normaliz (i.e. with the optional spkg pynormaliz):

sage: %time [len(RiggedConfigurations(['E',8,1], [[r,1]]).module_generators) for r in [1,.
....: .,8]]
CPU times: user 16.4 s, sys: 32 ms, total: 16.4 s
Wall time: 3.37 s
[3, 7, 24, 368, 75, 18, 5, 2]

Without it, the B^4,1 takes longer than I want to wait for it (and nearly impossible without this branch).

[tscrim]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 Currently, generating the first level of the Kleber tree grows poorly as the rank and the complexity of the root system increases. This is due to the fact that it uses all positive roots. Instead we use integral points (when expressed as simple roots) in the intersection of the negative root cone and a shifted positive weight cone.

-Also due to the number of operations involved, this ticket changes all lower levels to use the polytope enumeration as well.
+Also due to the number of operations involved, this ticket changes all lower levels to use the polytope enumeration for small rank unless normaliz is available.

[bsalisbury1]

comment:11

I'm getting doctest errors in a few places:

----------------------------------------------------------------------
sage -t --long src/sage/misc/sagedoc.py  # 3 doctests failed
sage -t --long src/sage/combinat/rigged_configurations/rigged_configurations.py  # 1 doctest failed
sage -t --long src/sage/combinat/posets/posets.py  # 1 doctest failed
sage -t --long src/sage/combinat/rigged_configurations/kleber_tree.py  # 13 doctests failed
sage -t --long src/sage/combinat/crystals/tensor_product.py  # 1 doctest failed
sage -t --long src/sage/combinat/rigged_configurations/tensor_product_kr_tableaux_element.py  # 3 doctests failed
----------------------------------------------------------------------
Total time for all tests: 3348.8 seconds
    cpu time: 20669.5 seconds
    cumulative wall time: 26249.8 seconds

Note this is after the merge with the latest develop branch.

[bsalisbury1]

Reviewer: Ben Salisbury

[tscrim]

comment:12

So the problem is with the normaliz interface. This is now #22938.

[tscrim]

Dependencies: #22938

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1f333b8 to 5aafe4e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a7d8f40	Merge branch 'public/rigged_configurations/speedup_kleber_tree-19075' of git://trac.sagemath.org/sage into public/rigged_configurations/speedup_kleber_tree-19075
aa9f258	Fixing integral points for a non-empty polytope with trivial integral hull.
5aafe4e	Merge branch 'public/geometry/integral_points_empty_hull_normaliz-22938' into public/rigged_configurations/speedup_kleber_tree-19075

[tscrim]

comment:14

Try it with this.

[bsalisbury1]

comment:15

HTML and PDF docs build and all tests passed on my machine.

One question/comment before giving a positive review: Should the following tests have the #long time tag removed?

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree
sage: KT = KleberTree(['E', 6, 1], [[4, 2]])  # long time (9s on sage.math, 2012)
sage: KT.cardinality()  # long time
12

Both of these calculations are now immediate with this update.

[tscrim]

comment:16

I think they are only immediate when using normaliz, so I'm not yet ready to remove them.

[vbraun]

Changed branch from public/rigged_configurations/speedup_kleber_tree-19075 to 5aafe4e