Opened 7 years ago
Closed 6 years ago
#19075 closed enhancement (fixed)
Speedup creation of Kleber tree
Reported by:  Travis Scrimshaw  Owned by:  Sage Combinat CC user 

Priority:  major  Milestone:  sage8.0 
Component:  combinatorics  Keywords:  rigged configurations, kleber tree 
Cc:  Sage Combinat CC user, Anne Schilling, Ben Salisbury  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Ben Salisbury 
Report Upstream:  N/A  Work issues:  
Branch:  5aafe4e (Commits, GitHub, GitLab)  Commit:  5aafe4e2daf41f9bfc464c69098d71f849ffd41a 
Dependencies:  #22938  Stopgaps: 
Description (last modified by )
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.
Change History (18)
comment:1 Changed 7 years ago by
Branch:  → public/rigged_configurations/speedup_kleber_tree19075 

Commit:  → f9da27b2e6e3a5ecf891001c184d4201532c3d01 
Status:  new → needs_review 
comment:2 Changed 7 years ago by
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 ~35x 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_{4}^{(1)}, I get the new version is 220x 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?
comment:3 Changed 7 years ago by
Commit:  f9da27b2e6e3a5ecf891001c184d4201532c3d01 → 05c24f30ee469274039f95ca59d4f7232d339134 

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_tree19075' of trac.sagemath.org:sage into public/rigged_configurations/speedup_kleber_tree19075

comment:4 Changed 7 years ago by
Commit:  05c24f30ee469274039f95ca59d4f7232d339134 → 7de002b3f7026fefca92a48cfc32c963a8ec38f7 

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.

comment:5 Changed 7 years ago by
Cc:  Ben Salisbury added 

Milestone:  sage6.9 → sage6.10 
comment:6 Changed 7 years ago by
Commit:  7de002b3f7026fefca92a48cfc32c963a8ec38f7 → 98a04064d53d4bacf209b8d7380f7e9bb2e539f1 

Branch pushed to git repo; I updated commit sha1. New commits:
0f28d76  Merge branch 'public/rigged_configurations/speedup_kleber_tree19075' of trac.sagemath.org:sage into public/rigged_configurations/speedup_kleber_tree19075

98a0406  Converting to weight/root lattice and using the old method for types A and D.

comment:7 Changed 7 years ago by
Commit:  98a04064d53d4bacf209b8d7380f7e9bb2e539f1 → 33af86e92c739daf4adfce96c3bb3752974bb1e6 

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.

comment:8 Changed 7 years ago by
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
comment:9 Changed 6 years ago by
Commit:  33af86e92c739daf4adfce96c3bb3752974bb1e6 → 1f333b872f56f34d7f126104bc1d95fc4142967b 

comment:10 Changed 6 years ago by
Description:  modified (diff) 

Milestone:  sage6.10 → sage7.6 
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).
comment:11 Changed 6 years ago by
Milestone:  sage7.6 → sage8.0 

Reviewers:  → Ben Salisbury 
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.
comment:12 Changed 6 years ago by
Dependencies:  → #22938 

So the problem is with the normaliz interface. This is now #22938.
comment:13 Changed 6 years ago by
Commit:  1f333b872f56f34d7f126104bc1d95fc4142967b → 5aafe4e2daf41f9bfc464c69098d71f849ffd41a 

Branch pushed to git repo; I updated commit sha1. New commits:
a7d8f40  Merge branch 'public/rigged_configurations/speedup_kleber_tree19075' of git://trac.sagemath.org/sage into public/rigged_configurations/speedup_kleber_tree19075

aa9f258  Fixing integral points for a nonempty polytope with trivial integral hull.

5aafe4e  Merge branch 'public/geometry/integral_points_empty_hull_normaliz22938' into public/rigged_configurations/speedup_kleber_tree19075

comment:15 Changed 6 years ago by
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.
comment:16 Changed 6 years ago by
I think they are only immediate when using normaliz
, so I'm not yet ready to remove them.
comment:17 Changed 6 years ago by
Status:  needs_review → positive_review 

comment:18 Changed 6 years ago by
Branch:  public/rigged_configurations/speedup_kleber_tree19075 → 5aafe4e2daf41f9bfc464c69098d71f849ffd41a 

Resolution:  → fixed 
Status:  positive_review → closed 
With the branch, we have (on SMC):
whereas previously this took
As an added benefit, this allows us to combine the children iterators into a single method.
New commits:
Generate the Kleber tree by using integral points in a polytope.