#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: | 8509534a8900501aca69724f27920c064dc7e618
public/combinat/speedup_coxeter_weyl_matrix_groups-19821| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by tscrim):
So that dropped my `%prun` iteration down to ~6.5 seconds. However, there
is a somewhat disturbing amount of overhead with recomputing initializing
data (nearly 1s):
{{{
Timer unit: 1e-06 s
Total time: 2.32224 s
File: /home/travis/sage/local/lib/python2.7/site-
packages/sage/groups/matrix_gps/coxeter_group.py
Function: first_descent at line 483
Line # Hits Time Per Hit % Time Line Contents
==============================================================
483 def
first_descent(self, side = 'right', index_set=None, positive=False):
484 """
...
491 """
492 155520 177504 1.1 7.6 M =
self.matrix()
493 155520 106485 0.7 4.6 if side !=
'right':
494 M = ~M
495 155520 244268 1.6 10.5 I =
self.parent().index_set()
496 155520 115970 0.7 5.0 n = len(I)
497 155520 133044 0.9 5.7 zero =
M.base_ring().zero()
498 155520 98536 0.6 4.2 if index_set
is None:
499 155520 145872 0.9 6.3 index_set
= range(n)
500 else:
501 index_set
= [I.index(i) for i in index_set]
502 155520 96996 0.6 4.2 if positive:
503 for i in
index_set:
504 if
any(M[j,i] > zero for j in range(n)):
505
return I[i]
506 else:
507 263735 183335 0.7 7.9 for i in
index_set:
508 263735 902137 3.4 38.8 if
all(M[j,i] <= zero for j in range(n)):
509 155520 118092 0.8 5.1
return I[i]
510 return None
}}}
So if we really wanted to go a bit crazy with things, we should implement
some kind of custom iterator that subclasses `SearchForest`, as well as
avoid converting to/from the index set and use `{0,1,...,n}`. Although I
would say the next step would be the cythonization of the matrix group
element classes if we wanted to try and squeeze more out of it right now.
--
Ticket URL: <http://trac.sagemath.org/ticket/19821#comment:18>
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.
