On Mon, Sep 01, 2014 at 09:33:24AM +0200, Christian Stump wrote:
> > - Can GAP iterate through the elements of a finite matrix group (at
> > this point this is all GAP know about the group) without storing
> > them all in memory.
>
> according to the user manual of Chevie
> (https://www.imj-prg.fr/~jean.michel/gap3/htm/chap069.htm#SECT024) it
> is possible to iterate through a finite Coxeter group there. I haven't
> figured out if that is as well possible for permutation groups or
> matrix groups in gap3 or gap4 in general though.
Thanks Christian and Jean-Michel for your insight! By curiosity, I
looked at the code of __iter__ for Weyl groups (it actually comes from
matrix groups), and found it informative:
sage: W = WeylGroup(["A",3])
sage: W.__iter__??
if not self.is_finite():
# use implementation from category framework
for g in super(Group, self).__iter__():
yield g
return
# Use the standard GAP iterator for small groups
if self.cardinality() < 1000:
for g in super(MatrixGroup_gap, self).__iter__():
yield g
return
# Override for large but finite groups
iso = self.gap().IsomorphismPermGroup()
P = iso.Image()
iterator = P.Iterator()
while not iterator.IsDoneIterator().sage():
p = iterator.NextIterator()
g = iso.PreImageElm(p)
yield self(g, check=False)
So, for infinite Coxeter groups, it's the generic iterator provided by
the CoxeterGroups category that is used. And in the case at end (E8),
Sage asks gap to build an isomorphic permutation group, and an
iterator over it. The next question to investigate is why this
actually fills GAP memory.
Note: to call directly the generic implementation, one can do:
sage: W = WeylGroup(["E",6])
sage: for w in CoxeterGroups().parent_class.__iter__(W):
....: pass
It would deserve some optimization though, as it's quite slower than
the native implementation in e.g. Coxeter 3:
sage: W = CoxeterGroup(["E",6], implementation="coxeter3")
sage: %time for w in CoxeterGroups().parent_class.__iter__(W): pass
CPU times: user 31.1 s, sys: 31.4 ms, total: 31.1 s
Wall time: 31.1 s
sage: %time for w in W: pass
CPU times: user 1.61 s, sys: 24.1 ms, total: 1.63 s
Wall time: 1.61 s
I have added some data points to the following ticket:
#9285: Challenge: iterating through E8 in 5 minutes
Anybody to take one this challenge?
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel.
For more options, visit https://groups.google.com/d/optout.
