Increase speed for Coxeter groups, Weyl groups, and quantum Bruhat graph #19821

tscrim · 2016-01-02T09:23:10Z

The primary goal of this ticket is to improve the creation speed for the quantum Bruhat graph. We do this in a number of ways:

Better management of data associated to lattice.nonparabolic_positive_roots.
Implement a (temporary) cache of the lengths of elements.

In addition, we also provide some general speedups to all matrix groups and Coxeter groups that came from looking into the above improvements. The net result is over 12x speedup of the creation of the quantum Bruhat graph:

sage: W = WeylGroup(['D',5], prefix='s')
sage: %time G = W.quantum_bruhat_graph()
CPU times: user 14 s, sys: 60.6 ms, total: 14 s
Wall time: 14 s

whereas previously this took over 3 minutes to compute. The downside is this has a larger memory footprint because of the temporary cache, but repeatedly computing the lengths of the elements was far too expensive.

This also includes a speedup of iterating over the entire Coxeter/Weyl group.

CC: @sagetrac-sage-combinat @anneschilling @sagetrac-mshimo @nthiery @darijgr @fchapoton @stumpc5 @jplab

Component: combinatorics

Keywords: quantum bruhat graph

Author: Travis Scrimshaw

Branch/Commit: 0ce02a6

Reviewer: Frédéric Chapoton

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

The text was updated successfully, but these errors were encountered:

tscrim · 2016-01-02T09:23:54Z

New commits:

`0b4069c`	`Speedup has_right_descent() for Coxeter groups.`
`c2c3f17`	`Speedup quantum_bruhat_graph by doing some things locally.`
`2b1a117`	`Changed libs.gap.element.GapElement.matrix() to avoid matrix constructor.`
`2426155`	`Use a specialized version of GapElement.matrix() to avoid some overhead.`
`4caa2bf`	`Don't store matrix() of Weyl group elements and some cleanup.`
`fcf0e35`	`Added length cache to quantum_bruhat_graph().`
`0b5fcec`	`Get a little more speed by using the matrices as keys for the length cache.`

tscrim · 2016-01-02T09:23:54Z

Branch: public/combinat/speedup_coxeter_weyl_matrix_groups-19821

tscrim · 2016-01-02T09:23:54Z

Commit: 0b5fcec

tscrim · 2016-01-02T09:31:53Z

comment:2

Also, _finite_recognition was no longer needed since we now have Coxeter types. One question I have for CoxeterGroup is should the default ring for simply-laced types be ZZ? The code which compares elements in the universal cyclotomic field to 0 is horribly slow and is the main reason why iteration over an instance of CoxeterGroup (over the UCF) takes so long. Compare:

sage: WC = CoxeterGroup(['D',4], base_ring=ZZ)
sage: %timeit L = [x for x in WC]
100 loops, best of 3: 12.1 ms per loop
sage: WC = CoxeterGroup(['D',4]) # base_ring=UniversalCyclotomicField()
sage: %timeit L = [x for x in WC]
1 loops, best of 3: 224 ms per loop

sage: WC = CoxeterGroup(['D',5], base_ring=ZZ)
sage: %timeit L = [x for x in WC]
10 loops, best of 3: 152 ms per loop
sage: WC = CoxeterGroup(['D',5]) # base_ring=UniversalCyclotomicField()
sage: %timeit L = [x for x in WC]
1 loops, best of 3: 3.97 s per loop

sagetrac-git · 2016-01-02T10:22:01Z

Changed commit from 0b5fcec to f673aec

sagetrac-git · 2016-01-02T10:22:01Z

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

`f673aec`	`A better method to find the minimal length coset representatives.`

darijgr · 2016-01-02T15:48:03Z

comment:4

A few questions:

What is a quantum Bruhat graph, and where can I read about it?
Have the indirect doctests from _finite_recognition been salvaged?

Also, when changing DiGraph, can you please add the right format in analogy to sagemath/sagetrac-mirror@6cb47c0 ? Thank you!

tscrim · 2016-01-02T16:21:18Z

comment:5

Replying to @darijgr:

What is a quantum Bruhat graph, and where can I read about it?

It is the usual Bruhat poset but with added "quantum" edges that are used for many purposes. One particular use in Sage is for specializations of Macdonald polynomials at t=0. See, e.g.,

Have the indirect doctests from _finite_recognition been salvaged?

Not exactly, but essentially the same tests in recognize_coxeter_type_from_matrix in sage.combinat.root_system.coxeter_matrix. So I would say everything is covered.

Also, when changing DiGraph, can you please add the right format in analogy to sagemath/sagetrac-mirror@6cb47c0 ? Thank you!

Technically I didn't change the input for the digraph, but I can add it in if you're not going to make other additions.

darijgr · 2016-01-02T16:39:16Z

comment:6

I'm not making any additions today, as I'd have to learn this stuff first (and I don't know if I have time for that) and even then I wouldn't be sure of the thinking behind the removal of __matrix. (This will be so much easier once I'm in Minneapolis...)

Thanks for the references!

videlec · 2016-01-02T20:23:41Z

comment:7

For UCF comparison, it will be faster after #19825 (it avoids QQbar usage).

sagetrac-git · 2016-01-02T23:31:15Z

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

`af33acf`	`Added explicit format indicator for DiGraph constructor for Darij.`

sagetrac-git · 2016-01-02T23:31:15Z

Changed commit from f673aec to af33acf

sagetrac-git · 2016-01-03T00:34:15Z

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

`e014037`	`Making some additional improvements.`

sagetrac-git · 2016-01-03T00:34:15Z

Changed commit from af33acf to e014037

sagetrac-git · 2016-01-03T00:38:27Z

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

`1129ab7`	`Removing comment about bottlenecks.`

sagetrac-git · 2016-01-03T00:38:27Z

Changed commit from e014037 to 1129ab7

tscrim · 2016-01-03T00:46:33Z

comment:11

Replying to @darijgr:

I'm not making any additions today, as I'd have to learn this stuff first (and I don't know if I have time for that) and even then I wouldn't be sure of the thinking behind the removal of __matrix. (This will be so much easier once I'm in Minneapolis...)

Added. The __matrix was just duplicating what matrix() already does and resulted in quite a big speedup to iteration (it cut it in half IIRC).

Replying to @videlec:

For UCF comparison, it will be faster after #19825 (it avoids QQbar usage).

With #19825 and my recent changes, it just takes 4 seconds on my laptop to iterate over D₅. Now the biggest speed gain (about 2.5s) will be in improving matrix multiplication over the UCF, as opposed to speeding up the comparisons (about 1.5s)

One takeaway message: if you are working in a simply-laced type for CoxeterGroup, use ZZ.

tscrim · 2016-01-03T00:59:19Z

comment:13

See #16116 for a discussion on speeding up matrices over (universal) cyclotomic fields.

nthiery · 2016-01-03T08:32:06Z

comment:14

Replying to @tscrim:

One takeaway message: if you are working in a simply-laced type for CoxeterGroup, use ZZ.

Or more generally a crystalographic type, I assume?

Thanks for the hard work btw!

nthiery · 2016-01-03T08:36:29Z

comment:15

Also: you may want to add a datapoint on #9285 after this.

tscrim · 2016-01-03T10:53:22Z

comment:16

Replying to @nthiery:

Replying to @tscrim:

One takeaway message: if you are working in a simply-laced type for CoxeterGroup, use ZZ.

Or more generally a crystalographic type, I assume?

No, it only works for simply-laced types as the cos(\pi / m) needs to be rational:

sage: W = CoxeterGroup(['B',2])
sage: W.gens()
(
[           -1 E(8) - E(8)^3]  [            1             0]
[            0             1], [E(8) - E(8)^3            -1]
)

I also added my datapoint for #9285, but it seems infeasible at this point using CoxeterGroup. The majority of the time is spent looking through the descents, which has to be done for keeping the constant memory iteration.

         16341032 function calls in 8.912 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   155520    2.187    0.000    3.494    0.000 group_element.py:308(_mul_)
   574775    1.657    0.000    3.515    0.000 coxeter_group.py:483(has_right_descent)
  2997405    0.621    0.000    0.621    0.000 coxeter_group.py:513(<genexpr>)
   574775    0.434    0.000    4.002    0.000 coxeter_groups.py:782(has_descent)
  1356910    0.418    0.000    0.568    0.000 coxeter_group.py:294(index_set)
   155520    0.357    0.000    0.357    0.000 matrix_space.py:142(__classcall__)
   155520    0.343    0.000    0.356    0.000 group_element.py:241(__init__)
   574775    0.298    0.000    0.881    0.000 {all}
   155520    0.254    0.000    0.294    0.000 {method '__copy__' of 'sage.matrix.matrix_integer_dense.Matrix_integer_dense' objects}
   155520    0.241    0.000    3.781    0.000 coxeter_groups.py:1498(apply_simple_reflection_right)
   155520    0.224    0.000    2.264    0.000 coxeter_groups.py:860(first_descent)
   103679    0.210    0.000    8.548    0.000 coxeter_groups.py:282(succ)
    51841    0.198    0.000    8.841    0.000 backtrack.py:139(search_forest_iterator)
  1356910    0.150    0.000    0.150    0.000 coxeter_matrix.py:779(index_set)
   155520    0.145    0.000    0.457    0.000 matrix_space.py:1247(matrix)
    51840    0.143    0.000    2.223    0.000 coxeter_groups.py:888(descents)
   574775    0.107    0.000    0.107    0.000 {method 'index' of 'tuple' objects}
   574775    0.106    0.000    0.106    0.000 {range}
  1667950    0.104    0.000    0.104    0.000 {method 'parent' of 'sage.structure.element.Element' objects}
   574775    0.076    0.000    0.076    0.000 group_element.py:282(matrix)
   155520    0.075    0.000    0.532    0.000 matrix_space.py:423(__call__)
   730298    0.072    0.000    0.072    0.000 {isinstance}
        1    0.071    0.071    8.912    8.912 <string>:1(<module>)
   155520    0.070    0.000    3.851    0.000 coxeter_groups.py:1526(apply_simple_reflection)

Moreover, a non-trivial amount of time is spent gathering the information to run the check for descents:

Timer unit: 1e-06 s

Total time: 4.06995 s
File: /home/travis/sage/local/lib/python2.7/site-packages/sage/groups/matrix_gps/coxeter_group.py
Function: has_right_descent at line 483

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
...
   509    574775       805826      1.4     19.8              i = self.parent().index_set().index(i)
   510    574775       668970      1.2     16.4              n = len(self.parent().index_set())
   511    574775       436368      0.8     10.7              M = self.matrix()
   512    574775       314255      0.5      7.7              zero = M.base_ring().zero()
   513    574775      1844527      3.2     45.3              return all(M[j,i] <= zero for j in range(n))

So there is definite room for optimization, but it would likely lead to some code duplication. I think Florent's parallelization of SearchForest and its move to the cython file will help a fair amount. Similarly, we could cythonize MatrixGroupElement_generic and its superclass MatrixGroupElement_base. We also get a bit of a penalty for the indirection (I implemented has_right_descent instead of has_descent).

However, this data will be rendered obsolete in a moment because I will be pushing a specialized version of descents and first_descent.

sagetrac-git · 2016-01-03T11:04:28Z

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

`8509534`	`Implementing custon first_descent() and descent() methods for CoxeterGroup.`

stumpc5 · 2016-01-03T13:16:04Z

comment:21

(Indeed, I just wanted to start some comparisons, but ran into the problem fixed in #19795. I now have to first rebuild Sage to 7.0.beta2 which will take a another day or two before I can start doing the testing...)

tscrim · 2016-01-03T16:19:20Z

comment:22

@fchapoton I haven't looked too closely at the changes to #11010, but I do suspect it will improve things there.

@stumpc5 In case you didn't catch it, Jeoren had mentioned on sage-release that you will need to run make distclean && make for the version bump to 7.0.beta2 (which is why I haven't bumped yet from 7.0.beta1).

@all At some point we should all sit down and port everything that we need from GAP3 to GAP4/sage/separate-library. Although that could likely be quite a project for any one particular package...

stumpc5 · 2016-01-03T16:31:28Z

comment:23

Jeoren had mentioned on sage-release that you will need to run make distclean && make for the version bump to 7.0.beta2

Yep, realized that after compiling for a few hours.

At some point we should all sit down and port everything that we need from GAP3 to GAP4/sage/separate-library. Although that could likely be quite a project for any one particular package...

This seems like an infeasible project for anyone not having many months spare time doing nothing but this while sitting next to someone knowing about the needs of the particular packages. (In short: this seems like an infeasible project.) Nevertheless, it needs to be started at some point anyway...

sagetrac-git · 2016-01-03T23:53:19Z

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

`2fdaef4`	`Forgot the doctests for first_descent.`

sagetrac-git · 2016-01-03T23:53:19Z

Changed commit from 8509534 to 2fdaef4

tscrim · 2016-01-12T10:47:50Z

Dependencies: #19870

tscrim · 2016-01-12T10:47:50Z

comment:25

The cythonization of matrix group elements is now #19870. I pulled the changes to the matrix group elements to #19870, so that is why it is set as a dependency (but I did not merge that branch in yet). However, it is simple enough to swap the dependencies if this gets a positive review first.

sagetrac-git · 2016-01-21T17:21:24Z

Changed commit from 2fdaef4 to 2e9535a

sagetrac-git · 2016-01-21T17:21:24Z

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

`0e04e0d`	`Merge branch 'develop' into public/combinat/speedup_coxeter_weyl_matrix_groups-19821`
`83c6b8d`	`Merge branch 'develop' into public/combinat/speedup_coxeter_weyl_matrix_groups-19821`
`2e9535a`	`Make the generators of CoxeterGroup dense.`

tscrim · 2016-01-21T17:26:36Z

comment:27

I have now merged in #19870. I also made the generators to CoxeterGroup be dense matrices for the following reason. The one() element is dense because the matrix_space() is dense. By making the generators dense, it means the generators are not converted to dense matrices upon multiplication, resulting in over a 2x speedup to iteration and sparse matrix multiplication is 3x slower in rank 6. Moreover, on average there are 11/18 non-zero entries in E₆, so IMO they are not really sparse matrices.

sagetrac-git · 2016-01-21T17:27:24Z

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

`989b6ea`	`Adding changes from #19821.`
`6358d53`	`Cythonized matrix_gp/group_element.py and simplified the class structure.`
`65ce465`	`Fixing modform_hecketriangle due to changes.`
`1110926`	`Fixing last doctests.`
`3efe9b6`	`Merge branch 'develop' into public/groups/cythonize_matrix_group_element-19870`
`29f7253`	`Special case for dense matrices over ZZ and making sure the inverse is in the base ring.`
`9582f28`	`Merge branch 'public/combinat/speedup_coxeter_weyl_matrix_groups-19821' into public/groups/cythonize_matrix_group_element-19870`
`525c753`	`Merge branch 'public/groups/cythonize_matrix_group_element-19870' into public/combinat/speedup_coxeter_weyl_matrix_groups-19821`

sagetrac-git · 2016-01-21T17:27:24Z

Changed commit from 2e9535a to 525c753

sagetrac-git · 2016-03-08T23:50:15Z

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

`8cac13c`	`Merge branch 'public/combinat/speedup_coxeter_weyl_matrix_groups-19821' of trac.sagemath.org:sage into public/combinat/speedup_coxeter_weyl_matrix_groups-19821`
`5333b0f`	`Implementing reviewer comments.`
`274f662`	`Merge branch 'public/groups/cythonize_matrix_group_element-19870' of trac.sagemath.org:sage into public/combinat/speedup_coxeter_weyl_matrix_groups-19821`
`9250e99`	`Fixing doctest and adding is_one.`

sagetrac-git · 2016-03-08T23:50:15Z

Changed commit from 525c753 to 9250e99

sagetrac-git · 2016-03-09T00:00:49Z

Changed commit from 9250e99 to bea6b3c

sagetrac-git · 2016-03-09T00:00:49Z

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

`bea6b3c`	`Even better is_one by avoiding unnecessary coercions for matrices.`

tscrim · 2016-03-09T00:01:12Z

comment:31

I fixed a trivial failing doctest and implemented a custom is_one(), which is much faster (~30 microseconds to a little over 1) with the changes to the matrices (in particular, avoiding the coercion calls).

sagetrac-git · 2016-03-10T23:02:08Z

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

`f38620a`	`Check identity rather than equality from coset_representative.`
`df18b13`	`Merge branch 'public/groups/cythonize_matrix_group_element-19870' of trac.sagemath.org:sage into public/groups/cythonize_matrix_group_element-19870`
`0ce02a6`	`Merge branch 'public/groups/cythonize_matrix_group_element-19870' into public/combinat/speedup_coxeter_weyl_matrix_groups-19821`

sagetrac-git · 2016-03-10T23:02:08Z

Changed commit from bea6b3c to 0ce02a6

fchapoton · 2016-03-21T12:30:47Z

Changed dependencies from #19870 to none

fchapoton · 2016-03-25T21:21:00Z

Reviewer: Frédéric Chapoton

fchapoton · 2016-03-25T21:21:00Z

comment:34

ok, looks good enough to me. Let it be

vbraun · 2016-03-27T07:44:30Z

Changed branch from public/combinat/speedup_coxeter_weyl_matrix_groups-19821 to 0ce02a6

tscrim added this to the sage-7.0 milestone Jan 2, 2016

tscrim added c: combinatorics labels Jan 2, 2016

tscrim assigned sagetrac-sage-combinat Jan 2, 2016

tscrim added the s: needs review label Jan 2, 2016

This comment has been minimized.

Sign in to view

fchapoton modified the milestones: sage-7.0, sage-7.2 Mar 21, 2016

fchapoton added s: positive review and removed s: needs review labels Mar 25, 2016

vbraun removed the s: positive review label Mar 27, 2016

vbraun closed this as completed in 453a37d Mar 27, 2016

tscrim mentioned this issue Jan 3, 2016

Multiplication of dense cyclotomic matrices should be faster #16116

Open

Increase speed for Coxeter groups, Weyl groups, and quantum Bruhat graph #19821

Increase speed for Coxeter groups, Weyl groups, and quantum Bruhat graph #19821

Comments

tscrim commented Jan 2, 2016

tscrim commented Jan 2, 2016

tscrim commented Jan 2, 2016

tscrim commented Jan 2, 2016

tscrim commented Jan 2, 2016

This comment has been minimized.

sagetrac-git mannequin commented Jan 2, 2016

sagetrac-git mannequin commented Jan 2, 2016

darijgr commented Jan 2, 2016

tscrim commented Jan 2, 2016

darijgr commented Jan 2, 2016

videlec commented Jan 2, 2016

sagetrac-git mannequin commented Jan 2, 2016

sagetrac-git mannequin commented Jan 2, 2016

sagetrac-git mannequin commented Jan 3, 2016

sagetrac-git mannequin commented Jan 3, 2016

sagetrac-git mannequin commented Jan 3, 2016

sagetrac-git mannequin commented Jan 3, 2016

tscrim commented Jan 3, 2016

tscrim commented Jan 3, 2016

nthiery commented Jan 3, 2016

nthiery commented Jan 3, 2016

tscrim commented Jan 3, 2016

sagetrac-git mannequin commented Jan 3, 2016

stumpc5 commented Jan 3, 2016

tscrim commented Jan 3, 2016

stumpc5 commented Jan 3, 2016

sagetrac-git mannequin commented Jan 3, 2016

sagetrac-git mannequin commented Jan 3, 2016

tscrim commented Jan 12, 2016

tscrim commented Jan 12, 2016

sagetrac-git mannequin commented Jan 21, 2016

sagetrac-git mannequin commented Jan 21, 2016

tscrim commented Jan 21, 2016

sagetrac-git mannequin commented Jan 21, 2016

sagetrac-git mannequin commented Jan 21, 2016

sagetrac-git mannequin commented Mar 8, 2016

sagetrac-git mannequin commented Mar 8, 2016

sagetrac-git mannequin commented Mar 9, 2016

sagetrac-git mannequin commented Mar 9, 2016

tscrim commented Mar 9, 2016

sagetrac-git mannequin commented Mar 10, 2016

sagetrac-git mannequin commented Mar 10, 2016

fchapoton commented Mar 21, 2016

fchapoton commented Mar 25, 2016

fchapoton commented Mar 25, 2016

vbraun commented Mar 27, 2016