Opened 6 years ago

Closed 4 years ago

#19075 closed enhancement (fixed)

Speedup creation of Kleber tree

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-8.0
Component: combinatorics Keywords: rigged configurations, kleber tree
Cc: sage-combinat, aschilling, bsalisbury1 Merged in:
Authors: Travis Scrimshaw Reviewers: Ben Salisbury
Report Upstream: N/A Work issues:
Branch: 5aafe4e (Commits, GitHub, GitLab) Commit: 5aafe4e2daf41f9bfc464c69098d71f849ffd41a
Dependencies: #22938 Stopgaps:

Status badges

Description (last modified by 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.

Change History (18)

comment:1 Changed 6 years ago by tscrim

  • Branch set to public/rigged_configurations/speedup_kleber_tree-19075
  • Commit set to f9da27b2e6e3a5ecf891001c184d4201532c3d01
  • Status changed from new to needs_review

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:

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

comment:2 Changed 6 years ago by tscrim

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 F4(1), I get the new version is 2-20x faster for Bi,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 6 years ago by git

  • Commit changed from f9da27b2e6e3a5ecf891001c184d4201532c3d01 to 05c24f30ee469274039f95ca59d4f7232d339134

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

ecdaf6cInitial ground work and \delta map.
0b0ccdeAdded reverse bijection for B^{1,1} of E_6^{(1)}.
6298f70Fixing type B bijection.
52140d4Fixing all of the problems from the refactoring of RC -> KRT bijection.
135648eDoing some more refactoring and doing some work for E_{6,7}.
3166a99Finalizing E_{6,7}^{(1)} bijection and fixing a doctest from the refactoring.
05c24f3Merge branch 'public/rigged_configurations/speedup_kleber_tree-19075' of trac.sagemath.org:sage into public/rigged_configurations/speedup_kleber_tree-19075

comment:4 Changed 6 years ago by git

  • Commit changed from 05c24f30ee469274039f95ca59d4f7232d339134 to 7de002b3f7026fefca92a48cfc32c963a8ec38f7

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

7de002bGenerate the Kleber tree by using integral points in a polytope.

comment:5 Changed 6 years ago by tscrim

  • Cc bsalisbury1 added
  • Milestone changed from sage-6.9 to sage-6.10

comment:6 Changed 6 years ago by git

  • Commit changed from 7de002b3f7026fefca92a48cfc32c963a8ec38f7 to 98a04064d53d4bacf209b8d7380f7e9bb2e539f1

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

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

comment:7 Changed 6 years ago by git

  • Commit changed from 98a04064d53d4bacf209b8d7380f7e9bb2e539f1 to 33af86e92c739daf4adfce96c3bb3752974bb1e6

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

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

comment:8 Changed 6 years ago by tscrim

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 5 years ago by git

  • Commit changed from 33af86e92c739daf4adfce96c3bb3752974bb1e6 to 1f333b872f56f34d7f126104bc1d95fc4142967b

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

99c26b0Merge branch 'public/rigged_configurations/speedup_kleber_tree-19075' of trac.sagemath.org:sage into public/rigged_configurations/speedup_kleber_tree-19075
1f333b8Use normaliz when available.

comment:10 Changed 5 years ago by tscrim

  • Description modified (diff)
  • Milestone changed from sage-6.10 to sage-7.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 B4,1 takes longer than I want to wait for it (and nearly impossible without this branch).

comment:11 Changed 4 years ago by bsalisbury1

  • Milestone changed from sage-7.6 to sage-8.0
  • Reviewers set to 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 4 years ago by tscrim

  • Dependencies set to #22938

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

comment:13 Changed 4 years ago by git

  • Commit changed from 1f333b872f56f34d7f126104bc1d95fc4142967b to 5aafe4e2daf41f9bfc464c69098d71f849ffd41a

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

a7d8f40Merge branch 'public/rigged_configurations/speedup_kleber_tree-19075' of git://trac.sagemath.org/sage into public/rigged_configurations/speedup_kleber_tree-19075
aa9f258Fixing integral points for a non-empty polytope with trivial integral hull.
5aafe4eMerge branch 'public/geometry/integral_points_empty_hull_normaliz-22938' into public/rigged_configurations/speedup_kleber_tree-19075

comment:14 Changed 4 years ago by tscrim

Try it with this.

comment:15 Changed 4 years ago by bsalisbury1

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 4 years ago by tscrim

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

comment:17 Changed 4 years ago by bsalisbury1

  • Status changed from needs_review to positive_review

comment:18 Changed 4 years ago by vbraun

  • Branch changed from public/rigged_configurations/speedup_kleber_tree-19075 to 5aafe4e2daf41f9bfc464c69098d71f849ffd41a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.