Skip to content

Improve CayleyDigraph performance #750

@reiniscirpons

Description

@reiniscirpons

The current CayleyDigraph method is rather inefficient, see excerpt below:

set := AsSet(G);
D := Digraph(IsImmutableDigraph,
             G,
             set,
             OnLeftInverse,
             {x, y} -> LeftQuotient(x, y) in gens);

The issue comes from using the Digraph method for this. In the current form, the check LeftQuotient(x, y) in gens is run for each element x, y in the group G. This means the final algorithm has complexity O(|G|^2). On the other hand, using something like the Todd-Coxeter or maybe even Froidure-Pin would have complexity O(|G|*|gens|) where gens is the set of generators of G that we are constructing the group with. So it would be quite useful to improve the CayleyDigraph method to use one of these algorithms instead.

Metadata

Metadata

Assignees

No one assigned

    Labels

    difficulty: 1A label for feature requests of moderate difficultygood-second-issueA label for issues that are good second time contributorsperformanceA label for issues or PR related to performance

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions