On Thursday, June 14, 2012 12:21:22 AM UTC+2, Aleksandar Makelov wrote:
>
>
>
>
> I tried both versions of orbit, stabilizer, orbit_transversal ( I
> renamed it from orbit_traversal to orbit_transversal to keep with the
> accepted terminology) on large symmetric/alternating/dihedral groups
> and the backtrack searches were easily seen to perform worse. However,
> there is some probability that they're more efficient on some other
> types of groups, I don't know (I'll soon try to get some database of
> known groups going, by the way). Could you provide some information on
> their complexity, or some references about these algorithms? Or indeed
> any literature related to computational group theory :) I've only been
> using "Handbook of computational group theory" by Holt, and
> "Permutation Groups" by Seress.
>
> The orbit_traversal I wrote is depth-first, yours is breadth-first; to
avoid problems
of incompatibility it would be better to use always the same.
I did not make a benchmark comparison, but I like yours better because it
is shorter.
orbit_transversal seems a strange name to me; I believe that in search one
talks of depth- and breadth-first traversals. About using a database, in
testing I used a script to read from Atlas the generators, without saving
them in a file; I attach it.
The Handbook by Holt is great; Seress seems more difficult; there is the
book
by Butler; I found useful as an introduction
Kreher, Stinson "Combinatorial algorithms", which gives an overview to
permutations,
partitions, graphs, but it is less advanced.
> > In the near future I do not plan to work on permutation groups, though I
> > will follow with interest
> > Aleksandar's work, apart possibly from the following topic.
> >
> > @Aleksandar Makelov do you plan to work on the intersection of groups?
> > That is somehow related to canonicalization, since the Butler algorithm
> > for finding the
> > double coset representative is based on the intersection algorithm.
>
> There is an algorithm for finding the intersection of two subgroups of
> a permutation group that uses some sort of backtracking, and it's
> described in the "Handbook...", pp. 124-125. As far as I can see now,
> Seress has only special cases of group intersections. Other than that,
> I'm clueless. Do you have any resources on what algorithms for group
> intersections might be efficient (I guess the one in the "Handbook..."
> is not going to be terrible) ? I can go over it and implement it at
> some point, how soon do you need it?
>
> I do not know which implementation is efficient;
I read that it is non-polynomial, but that in practice it is fast.
It is great if you implement it; it would be useful to me now :) but take
your time.
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/sympy/-/h_WpRuJJjE8J.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sympy?hl=en.
from time import time
from sympy.combinatorics.perm_groups import PermutationGroup
from sympy.combinatorics.permutations import Permutation, perm_af_muln
import urllib2
def read_gens(fn):
f = urllib2.urlopen(fn)
s = f.read()
a = s.split('\n')
n = int(a[0].split()[2])
a = [int(x)-1 for x in a[1:] if x and not x.isspace()]
assert len(a) == n
return a
fnbase = 'http://brauer.maths.qmul.ac.uk/Atlas/'
# sporadic groups
m11 = 'spor/M11/mtx/M11G1-p11B0.'
m12 = 'spor/M12/mtx/M12G1-p12aB0.'
m22 = 'spor/M22/mtx/M22G1-p22B0.'
m23 = 'spor/M23/mtx/M23G1-p23B0.'
m24 = 'spor/M24/mtx/M24G1-p24B0.'
hs = 'spor/HS/mtx/HSG1-p100B0.'
mcl = 'spor/McL/mtx/McLG1-p275B0.'
co2 = 'spor/Co2/mtx/Co2G1-p2300B0.' # nostore
co3 = 'spor/Co3/mtx/Co3G1-p276B0.'
co1 = 'spor/Co1/mtx/Co1G1-p98280B0.' # stopped because RAM full
j2 = 'spor/J2/mtx/J2G1-p100B0.'
suz = 'spor/Suz/mtx/SuzG1-p1782B0.'
f22 = 'spor/F22/mtx/F22G1-p3510B0.' # nostore
f23 = 'spor/F23/mtx/F23G1-p31671B0.' # stopped because RAM full
# Fi24' skipped
he = 'spor/He/mtx/HeG1-p2058B0.' # nostore
# HN skipped
# Th no representation on permutations available
# B no representation on permutations available
# M no representation available
j1 = 'spor/J1/mtx/J1G1-p266B0.'
# ON skipped
# Ly no representation on permutations available
j3 = 'spor/J3/mtx/J3G1-p6156B0.'
# jn4 skipped
ru = 'spor/Ru/mtx/RuG1-p4060B0.'
tf42 = 'exc/TF42/mtx/TF42G1-p1600B0.'
# alternating groups alt[i] for i=5,...,23
alt = [None]*5 + ['alt/A%d/mtx/A%dG1-p%dB0.' %(i,i,i) for i in range(5,24)]
alt[6] = 'alt/A6/mtx/A6G1-p6aB0.'
l24 = 'lin/L24/mtx/A5G1-p5B0.'
l25 = 'lin/L25/mtx/A5G1-p5B0.'
l27 = 'lin/L27/mtx/L27G1-p7aB0.'
l28 = 'lin/L28/mtx/L28G1-p9B0.'
l29 = 'lin/L29/mtx/A6G1-p6aB0.'
l211 = 'lin/L211/mtx/L211G1-p11aB0.'
l213 = 'lin/L213/mtx/L213G1-p14B0.'
l217 = 'lin/L217/mtx/L217G1-p18B0.'
l219 = 'lin/L219/mtx/L219G1-p20B0.'
l223 = 'lin/L223/mtx/L223G1-p24B0.'
l229 = 'lin/L229/mtx/L229G1-p30B0.'
l231 = 'lin/L231/mtx/L231G1-p32B0.'
l232 = 'lin/L232/mtx/L232G1-p33B0.'
l249 = 'lin/L249/mtx/L249G1-p50B0.'
l32 = 'lin/L32/mtx/L27G1-p7aB0.'
l33 = 'lin/L33/mtx/L33G1-p13aB0.'
l35 = 'lin/L35/mtx/L35G1-p31aB0.'
l37 = 'lin/L37/mtx/L37G1-p57B0.'
l311 = 'lin/L311/mtx/L311G1-p133B0.'
l313 = 'lin/L313/mtx/L313G1-p183aB0.'
l42 = 'lin/L42/mtx/A8G1-p8B0.'
l44 = 'lin/L44/mtx/L44G1-p85aB0.'
l45 = 'lin/L45/mtx/L45G1-p156aB0.'
l52 = 'lin/L52/mtx/L52G1-p31aB0.'
l62 = 'lin/L62/mtx/L62G1-p63aB0.'
l72 = 'lin/L72/mtx/L72G1-p127aB0.'
# L2(p) for larger primes p only in cyclic notation
u33 = 'clas/U33/mtx/U33G1-p28B0.'
u34 = 'clas/U34/mtx/U34G1-p65B0.'
u35 = 'clas/U35/mtx/U35d2G1-p50B0.' # used c,d; different order from Atlas
# but same order as in sage
u37 = 'clas/U37/mtx/U37G1-p344B0.'
u38 = 'clas/U38/mtx/U38G1-p513B0.'
u39 = 'clas/U39/mtx/U39G1-p730B0.'
u311 = 'clas/U311/mtx/U311G1-p1332B0.'
u313 = 'clas/U313/mtx/U313G1-p2198B0.'
u316 = 'clas/U316/mtx/U316G1-p4097B0.'
fnb = alt[5]
print 'path=', fnbase + fnb + 'm1'
store = 0
full = 1
gens = [read_gens(fnbase + fnb + x) for x in ['m1', 'm2']]
print gens
gens = [Permutation(p) for p in gens]
G = PermutationGroup(gens, gens[0].size)
t0 = time()
G.schreier_sims()
#G.schreier_sims(full)
#G.schreier_sims(store)
t1 = time()
print 'order=', G.order()
print '%.2f' %(t1-t0)
