#19821: Increase speed for Coxeter groups, Weyl groups, and quantum Bruhat graph
-------------------------------------+-------------------------------------
Reporter: tscrim | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.0
Component: combinatorics | Resolution:
Keywords: quantum bruhat | Merged in:
graph | Reviewers:
Authors: Travis Scrimshaw | Work issues:
Report Upstream: N/A | Commit:
Branch: | 1129ab7725b584d019902863ae6949d6996fdbc6
public/combinat/speedup_coxeter_weyl_matrix_groups-19821| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by tscrim):
Replying to [comment:14 nthiery]:
> Replying to [comment:11 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`.
--
Ticket URL: <http://trac.sagemath.org/ticket/19821#comment:16>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
