Martin Baker wrote:
>
> On 01/23/2017 05:37 AM, Waldek Hebisch wrote:
> > Martin Baker wrote:
> >> Patch is here:
> >> https://github.com/martinbaker/fricasAlgTop/blob/master/permgrps1.patch
> > I have tried it now. AFAICS it is _extremally_ inefficient:
> > coerce(symmetricGroup(4))@GroupPresentation crashes due to
> > running out of memory (tested on sbcl with default 1GB limit),
> > coerce(dihedralGroup(7))@GroupPresentation works but takes
> > a lot of time and produces large presentation.
>
> Waldek,
>
> Thank you for looking at this. I did not find a published algorithm for
> this so I just worked out a simple algorithm myself, I did not think
> much about efficiency I was just happy to hit on a method that worked.
>
> The main issue is finding the relations. It seems to me that each
> relation corresponds to a loop in the Cayley graph.
Yes.
> So I just wrote an algorithm that found all the relations (loops) by
> doing a tree search of the Cayley graph. Obviously this finds a lot of
> redundant rules (loops).
>
> Am I correct in thinking that the algorithm that you are proposing is
> more efficient because it uses a stabilizer chain (sequence of
> subgroups, each containing the next and each stabilizing one more
> point). So when we work out the loops in the subgroup we implicitly
> encode information about the loops in the cosets so we consider less loops?
Yes. Within coset we get a lot of implied relations (loops). We
only need to add a single loop for each pair (generator, coset representative).
In fact, for some pairs (generator, coset representative) we need
no relation as in example from another message.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" 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/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
