changed 6 years ago  
Linked with GitHub

Notepad for GAP Days Spring 2019

Beware that the contents of this notepad can be read and modified by anyone with access to the URL, so you should not share any sensitive information here.

Table of contents:

Practical information

  • Wi-Fi: For those who cannot access eduroam or wired internet, we have a shared guest Wi-Fi account. Please ask for the login details.
  • Lunch: Most of us will eat at the university Mensa. The Mensa provides hot meals for around 5-6€. There are two nearby Mensas:
  • The Mensas are open from 11:30 until 13:30.
  • The Mensas serve meals that are different each day, and different from each other. The menus for the Mensas are available here (PDF version) –– please check the relevant box for the Mensa that you are interested in. The price that you will pay is the one in the column labelled “Gäste”.
    • Paying: in the Mensa, you must purchase a ticket, with cash, for the meal that you want, before going to collect your meal. One of the locals will help you with this if you are unsure or don't speak German.
  • There is a supermarket called Netto immediately to the north of the campus (click for location).
  • There is a bakery and coffee shop called Schäfer's next to Netto (click for location).

Main focus: Modern permutation group algorithms

List of functionality we would like for permutation groups: https://hackmd.io/ZeykRHurT46z1ybeiWyC9g#

Resources

Survey of existing permutation group code in GAP

  • What functionality is there already in GAP? (You might be surprised!)
  • Is there anything obvious that is missing, or at least not easy to find (especially as a new user)?
  • Can we identify places where there is room for improvement…
    • In performance?
    • In functionaltiy?
    • In clarity?
    • In documentation?
    • Elsewhere?

Provide simple functions for working with permutation groups

  • Build, extend and query Schreier vectors.
  • Build a stabilizer chain out of schreier vectors.
    • Add random elements
    • Implementation of Schreier's lemma
  • Maybe some inspiration: https://github.com/markuspf/BSGSKit

Provide simple documented examples of algorithms using these stabilizer chains

  • Strip permutations through a stabilizer chain.
  • Construct a random element of group.
  • Simple backtrack search for finding, for example, intersection and set stabilizer
    • Just using the stabilizer chain, no partition backtrack (yet)!

Easy implementations of some common algorithms

  • Find one / a maximal / all block structures in a group
  • Change of base

Possible slightly larger projects

  • Decide whether a permutation group given by a set of generators is a direct product
  • Computing the centre
  • Computing the commutator subgroup
  • Testing for solvability
  • Testing for nilpotence

Some performance issues (GAP vs. other implementations)

Examples of comparisons of conjugacy tests with GAP and other systems can be found here.

People: Thomas, …

Writing appropriate, useful, clear, and correct documentation is one of the hardest parts of software development, and that includes computational algebra systems like GAP.

  • Think about: how can we make the GAP documentation (let's focus on permutation groups) more user friendly?
    • see, for instance, GAP issue #3329, where, at the very least, the documentation is not sufficient to get someone inexperienced up and running with GAP at all.

Add black box recognition of S_n and A_n

There is finished code by Alice Niemeyer, Martin Leuner and Sebastian Jambor that decides whether a black box group with bounded degree is isomorphic to S_n or A_n. This should be integrated into the recog package. You can find the code here.

People: Dominik Bernhardt, …

Other project descriptions and reports

For each project, please maintain a short description of the project and its progress.

Implementing mutable digraphs in the Digraphs package

aka “Digraphs v1.0”. Currently, digraphs in Digraphs are immutable, so modifying one (such as adding or removing an edge) requires the creation of a new digraph in memory. This can be expensive. We wish to permit mutable digraphs, however this requires many new methods and adjustments to old methods.

There is a github project for this here.

People: James Mitchell, Finn Smith, Wilf Wilson,…

Writing up MatrixObj specification

Revising how matrices and vectors are implemented in GAP has been in the works for over a decade now. We had two GAP meetings on this in the past few years, but progress has been mostly stalled since then. A major blocker for this is that while we discussed how to go about things, we never finished writing up a specification for others to work with. The plan is to get that done this week to enable other people to contribute to this.

People: Max Horn, James Mitchell…

Metapackages for GAP

Metapackages should be a possibility to group several GAP packages into one, make releases for them in a single archive, and only have a single website. This can benefit homalg, CAP, recog, and probably many more. See here for the PR, here for previous discussions (issue), and here for a test package. See this HackMD notepad for more information.

People: Sebastian Gutsche, Max Horn…

New versions of the GRAPE and DESIGN packages

Finish off improvements in GRAPE and DESIGN code, tests and documentation, and release new versions of these packages.

James Mitchell: if it's of interest I can try to recover the GAPDoc version of the manual that we made some years ago.

People: Leonard Soicher, …

Reading in Syntax Trees

Currently, AST's of GAP functions can be encoded into a GAP readable
format using the SYNTAX_TREE function. We want to be able to read
those trees back into GAP functions, to actually execute them. There currently
is a first implementation here.

People: Sebastian Gutsche, …

Exploration of transitive permutation groups (for Galois groups)

We denote Sd the symmetric group on {1,...,d} (which is also the degree
of the polynomial we are playing with). Finding Galois groups lead to
the following permutation group problems:

  • given a transitive permutation group G c Sd compute the list of
    conjugacy classes of maximal transitive subgroups
    -> article by A. Hulpke from 2017

  • given transitive subgroups H < G < Sd compute the list of
    conjugacy classes of Sd that intersects G but not H
    See github issue #6.

  • given a list of graphs on {1,2,…,n} compute the intersection of their
    isomorphism group.

A resolvent for a pair H < G < Sd is an element of Sets(PartitionsSet([1..d]))
(in GAP notation) such that the orbit X^H is smaller than X^G.

  • given a transitive permutation group G < Sd find "small" resolvent
    for all the maximal transitive subgroups H < G. For now we use
    PartitionsSet([1..d]) but these are probably not the best.
    See github issue #6.

People: Vincent Delecroix

GAP discussion topics and outcomes

Please list any topics that you would like to be discussed, along with details about any decisions or resolutions that have been made about the topic. Meetings may be held to discuss these topics; please include details here of any planned meetings.

  • 10:00 Thursday – The management of issues and PRs on GitHub.
    • Chris Jefferson feels that the number of open issues is overwhelming and that we should close certain issues to make other issues easier to find:

      “I wonder if we need to do something hard-core, like move non-bugs to a wiki page or something, after 6 months.”

    • Max Horn feels that the careful use of labels might be sufficient; and disagrees that issues are "overwhelming"
    • Wilf is writing something up about this on a separate HackMD.
  • Robust hosting of the GAP website, and GAP and package releases.
    • The GAP website, and the files of GAP and package releases, are hosted on servers in St Andrews with no redundancy. These servers have proved to be unreliable, which is bad for several reasons. We need to move to a more robust setup.
    • Max prepared a proposal for this
  • Improve info warnings during package loading.

Programme

Day 1: Monday 18th

Organisational notes

Workshop dinner: House of India, 18:30.

Plans for the day

  • Wilf Wilson
    • Help people with technical problems.
    • Lead (with Markus and, later, Chris) discussions about GAP's support for computing with permutations and permutation groups.

Results and accomplishments

  • Wilf Wilson

    • I spoke to lots of people about GAP and related topics
      • I had a long discussion with Leonard, and later Markus, about backtrack search
    • I helped people with small GAP problems
    • I tried to make sure that there was a reasonable coffee supply

  • Max Horn:

    • worked on SyntaxTrees
    • answered questions, helped solve little problems
    • improve ReleaseTools

  • Michael Torpey

    • Learned a lot about Schreier vectors
    • Implemented a rough prototype in GAP

  • Sebastian Gutsche

    • Worked on SyntaxTrees
    • answered some questions

  • James Mitchell

    • mostly worked on mutable digraphs, we are nearly there.
    • implemented a generic C++ template version of the basic Schreier–Sims (admittedly not today).

  • Finn Smith

    • worked with James on mutable digraphs

  • Johannes Hahn

    • done some of exercises, including the schreier tree one.

  • Rebecca Waldecker

    • started to remember many things and implemented Schreier vector

  • Thomas Breuer

    • learned about Chris' BacktrackKit package,
      which should eventually be used as the framework for a reimplementation of GAP's matrix automorphism/isomorphism
      functionality (currently this does not use partition backtrack methods)

  • Sergio Siccha

    • listened to chris
    • talked to Mun See about Cartesian Decompositions and Direct Products of permutation groups
    • started to look into GAP stabilizer chains

  • Mun See Chang

    • listened to chris
    • talked to Sergio about Cartesian Decompositions and Direct Products of permutation groups
    • started on getting the "simple" Direct Products decomposition that Chris wants

  • Dominik Bernhardt

    • Listened to Chris a lot
    • Did technical work on the AnSn black box algorithm by Alice, Martin and Sebastian
    • Looked at the recog code for permutation groups

  • Justine Falque

    • reworked some old code and made it cleaner
    • also listened to people !

  • Anna Sucker

    • listened to chris
    • read about stabiliser chains and its current implementation in Alexander Hulpke's pdf and on the gap website
    • did some of the examples starting at the beginning

  • Paula Hähndel

    • implemented a simple version of SchreierVector

  • Lucas Wollenhaupt

    • listened to Chris
    • did some of the exercises
    • tried the examples to test Anna's and my conjugancy test implementation
    • learned about the backtrack kit
    • got some ideas for my bachelor thesis from Chris

  • Calin Borceanu

    • Much eavesdropping. Got some idea of what other people are working on
    • Talked to people and discovered that my idea of what 'Modern' should mean matches with Markus and some other people

Day 2: Tuesday 19th

Plans for the day

  • Johannes Hahn

    • Trying to understand the TwoClosure method in GAP.
    • if that fails: Re-implement a simpler, cleaner version, possibly using the digraph package

  • Wilf Wilson

    • I'd like to actually write some code today: I'll try some of the exercises related to Schreier vectors and working towards stabiliser chains.
    • James wants me to do some Digraphs
    • Make some PRs to BTKit

  • Sebastian Gutsche

    • Continue to work on syntax tree coder
    • Work on pragmas
    • Prepare metapackage work for tomorrow
    • Let Vincent fix my e-antic use

  • Markus Pfeiffer

    • Finish writing my exercise on implementing Sims backtrack method
    • Do some more of my exercises
    • Prepare exercises with accompagning material for publication (on my blog maybe)

Results and accomplishments

  • Anna Sucker

    • learned more about stabilizer chains
    • implemented some functions for stabilizer chains as an exercise
    • a pull request for a good first issue with Sergio

  • Johannes Hahn

    • Implemented a (new?) algorithm to compute the 2-closure / orbital-graph-closure of a permutation group.
    • A pull request for the OrbitalGraph package.

  • Thomas Breuer

    • created a pull request and two issues for GAP
    • tried to understand BacktrackKit

  • Paula Hähndel

    • I think I understood bits of where GAP is documented
    • was reminded and informed of the use of ApplicableMethod
    • listend to Max about the recog package
    • helped Johannes run his code

  • Dominik Bernhardt

    • Bought a new pair of pants
    • Got very helpful information from Max about the recog package
    • Started integration of SnAn Blackbox into recog with Sergio
    • Opened many issues on the SnAn BB recog code

  • Max Horn

    • worked on syntax trees with Sebastian
    • explained to Dominik how to integration code into recog package
    • helped Leonard to use ReleaseTools and release design
    • reviewed / merged / created a bunch of pull requests
    • no progress on MatrixObj :-(

  • Sergio Siccha

    • Instead of talking to Mun See I talked to Dominik, Max, Anna, Lucas and Paula
    • worked on Recog with Dominik
    • I almost wrote up something for my paper with Colva

  • Mun See Chang

    • Instead of talking to Sergio I talked to Calin and Chris
    • worked on the simple direct factors
    • running it on the automorphism of graphs (bottleneck is computing stab chain)

  • Rebecca Waldecker

    • I worked on some little functions related to fixed points (but really wanted to do something with minimal and canonical image, maybe tommorow?)

  • Markus Pfeiffer

    • Worked on some exercises for implementing backtrack search

    • Visited Imke

    • Incited Michael to take care of the GAP Jupyter kernel

    • Reviewed Johannes' pull request on OrbitalGraphs

      Katja Bercic from Erlangen writes

      ​​​​Dear all,

​​​​I am planning to organize a small workshop dedicated to math data in the summer, in Bled, Slovenia.  The tentative dates are between August 18th and 25th, 2019, but that might change if there is a strong interest in doing otherwise.

​​​​The workshop would ideally bring together interested users and authors of mathematical datasets, and data framework developers.
​​​​The underlying agenda is to make a push towards MathDataHub (recently described in https://kwarc.info/people/mkohlhase/submit/cicm19-MDH.pdf).

​​​​I would like to particularly extend the invitation to anyone
​​​​- with an insider knowledge of any of the larger existing math databases,
​​​​- who is interested in integrating math databases with computer algebra systems,
​​​​- who is interested in implementing web interfaces for math databases.

​​​​If you are tentatively interested in participating, please fill in the date poll before March 29th (next Friday):

https://framadate.org/3a5bWCYJMIfxGkE4
```

  • Michael Torpey

    • Implemented stabiliser chains (badly)
    • Talked to Chris about reading digraphs
    • Shamelessly plugged the package manager
    • Helped Johannes make a pull request
    • Ate a lot of schnitzel

  • Justine Falque

    • This morning worked on old code again
    • This afternoon, implemented some basic algorithms for permutation groups with Wilf.

  • Lucas Wollenhaupt

    • read more about stabilizer chains
    • fixed an issue with my GAP on OS X
    • added a pull request explaining the workaround
    • almost finished another pull request for a good first issue a

  • Christopher Jefferson

    • Tidied up BacktrackKit
    • Merged some PRs for BacktrackKit
    • Fixed some issues in 'Images'

  • Sebastian Gutsche

    • More work on syntax trees
    • Some work on pragmas

  • Wilf Wilson

    • Reviewed some Digraphs code concerning the addition of mutable digraphs to the package
    • Made pull requests to the BacktrackKit package
    • Worked through the beginning of Alexander Hulpke's notes, and implemented the algorithms, with Justine

  • Leonard Soicher

    • Gave talk concerning the GAP permutation group algorithms used in my graph colouring functionality in GRAPE.
    • Had interesting and useful conversation with Calin Borceanu on clique classification and backtrack search.
    • Released DESIGN 1.7 with Max Horn's excellent guidance and help.
    • Worked on the upcoming new release of GRAPE.

  • Markus Pfeiffer

    • Made some lists (and timings) of computing 2-closures of permutation groups, for example for transitive groups, and some primitive groups
    • Tried out examples with using edge-coloured graphs in Digraphs

Day 3: Wednesday 20th

Organisational points

  • 11:00: Finish up meta-packages (Max, Alex (remote via Skype), Sebastian) in one of the first floor rooms

Plans for the day

  • Wilf Wilson

    • Update PRs for BTKit.
    • Review cliques functionality for Digraphs, with respect to mutability of digraphs.
    • Talk to people.

  • Finn Smith

    • Finish edge coloured digraph automorphisms PR
    • Some more mutable digraph stuff

  • Dominik Bernhardt

    • Do some teaching stuff for a seminar
    • Work on SnAn BB recog integration

  • Markus Pfeiffer

    • Write a function for OrbitalGraphs to 2-closure using Finn's edge-coloured digraphs stuff and bliss
    • Continue the lightweight introduction to backtrack search

Results and accomplishments

  • Markus Pfeiffer

    • Told Sebastian that one can add emojis to slack
    • Trying out edge coloured digraphs and their automorphism groups
    • Made a long list of timings, subgroup indices, etc for computing 2-closure (OrbitalClosure) of groups

  • Sebastian Gutsche

    • Added "s**t's on fire, yo" emoji to slack
    • Discussed metapackages and fixed some code
    • Merged Py(Q)Normaliz into a single python module, tbr soon

  • Johannes Hahn

    • Installed Ubuntu into the Windows subsystem for Linux and GAP inside that in order to get the digraph package working under Windows. Ran into a lot of compile problems, took forever (That "shit's on fire, yo" emoji is really necessary, Sebastian!)
    • Tried to figure out how to actually implement the memory optimisations of the TwoClosure method I mentioned yesterday

  • Max Horn

    • reviewed / merged / created a bunch of pull requests
    • discussion on meta packages with Alexander, Sebastian, Wilf
    • discussion with Rebecca about recog
    • some minor work on recog; added a bunch of TODO issues
    • discussed spaces in paths with Johannes
    • helped Leonard with git and github stuff
    • started to convert the GAP website to use Jekyll
    • again no progress on MatrixObj :-(

  • Anna Sucker

    • worked on the pull request from yesterday since some checks didn't work
    • worked on another issue
    • read some of the code of the BacktrackKit with Lucas
    • read about permutation group algorithms in Alexander Hulpke's pdf

  • Dominik Bernhardt

    • Learned about camelCase
      Image Not Showing Possible Reasons
      • The image file may be corrupted
      • The server hosting the image is unavailable
      • The image path is incorrect
      • The image format is not supported
      Learn More →
    • Reviewed code from students in Aachen
    • Learned about the ACE package

  • Thomas Breuer

    • created two more issues
    • made progress in understanding partition backtrack

  • Wilf Wilson

    • Participated in meta-packages discussion. The plan seems reasonable
      Image Not Showing Possible Reasons
      • The image file may be corrupted
      • The server hosting the image is unavailable
      • The image path is incorrect
      • The image format is not supported
      Learn More →
    • Made the Digraphs cliques code work properly with mutable digraphs; made a PR for this
    • Helped various people
    • Enjoyed the sunshine and gossiped with Michael
    • Reviewed a couple of pull requests

  • Sergio Siccha

    • talked to Chris a lot and to other people a little
    • helped Anna and Lucas
    • added a test to the recog pkg
    • got a slot for my talk on "Normalisers of Primitive Groups in Quasipolynomial Time" Whop whop I like
    • prepared my talk

  • Paula Hähndel

    • made my first pull request with the help of Wilf
    • talked to Mun See and a bit to Chris
    • learned how to open and close the windows and the blinds
    • understood that I shouldn't use GAP functions for groups that don't fullfil the requirement in the documentation

  • Mun See Chang

    • sketched proof on the direct product stuff
    • talked to Paula
    • listened to Chris and Calin, still digesting some thoughts

  • Rebecca Waldecker

    • implemented functions related to minimal image (thanks Wilf and Chris)
    • had several interesting conversations
    • now has soooooo much appreciations for all the GAP code that is already there

  • Michael Torpey

    • Enjoyed the sunshine and gossiped with Wilf
    • Completed a recursive implementation of the Schreier–Sims algorithm
    • Ate camembert

  • Lucas Wollenhaupt

    • continued working on the pull request from yesterday
    • started looking into the BacktrackKit with Anna

Day 4: Thursday 21st

List of functionality we would like for permutation groups: https://hackmd.io/ZeykRHurT46z1ybeiWyC9g – please add to this :) Chris xx

Schedule

10:00 – Talk about issue and PR numbers
11:00 – Talk about GAP hosting / website design
14:00 – Sergio's talk, Calculating Normalisers of Primitive Groups (Room 1.02)
15:00 – Chris leading something about BacktrackKit (in Room 1.02)
20:00 – Dinner for those interested, at Osteria Da Salvatore, on Kleine Ulrichstraße.

Plans for the day

  • Sergio Siccha

    • investigate a crash of CVEC under HPC-GAP
    • give a talk

  • Dominik Bernhardt

    • Work on the SnAnBB integration (and hopefully get it to work).
    • Attend Sergios talk.
    • Attend discussions and learn more about GAP infrastructure

  • Wilf Wilson

    • Talk to James about some ideas that I’ve had for computing with semigroups
    • Review recent PRs and issues to GAP
    • Enjoy more sunshine
    • Encourage discussions amongst others, including: the management of issues and PRs on GAP’s GitHub repo
    • I want to be helpful to others
    • Try and make sure that

  • Sebastian Gutsche

    • Try to implement pragmas (second personal attempt, third attempt total)

  • Michael Torpey

    • Add some features to PackageManager
    • Maybe help with Digraphs

  • Calin Borceanu

    • Continue to take advantage of being on the same continent as GAP developers
    • Finish immutable stab chains?
    • Attend Sergio's talk

Results and accomplishments

  • Paula Hähndel

    • finished my first PullRequest (got merged)
    • joined the discussion about labels (and now I have the feeling that I slowly get sucked into gap (and can't escape any longer))

  • Rebecca Waldecker

    • continued writing stuff for minimal images
    • listened to interesting talks
    • had really nice conversations with various people
    • not an accomplishment: Sad that tomorrow is the last day!

  • Dominik Bernhardt

    • Joined discussions about labels and Issue management and learned a lot about it.
    • Labeled a few issues with flags.
    • Attended Sergio's and Chris' talk
    • Did only a little work on SnANBB
      • Tried to understand how I have to call the SLPs and set it correctly in the code and failed. :(
    • Tried out the ACE package

  • Wilf Wilson

    • This morning I had meetings with GAP colleagues and others. In addition to my duties in the maths department, I shall have further such meetings later today.
    • BacktrackKit: did a fiddly rebase and made a new PR from the result, adding lots of tweaks and comments to the BacktrackKit.gi file
    • Participated in discussions about issue and PR management on GAP
    • Reviewed PRs and responded to issues on gap-system/gap
    • Helped Paula to make changes to her first GAP pull request
    • Thought about the Digraphs package

  • Anna Sucker

    • finished a pull request from yesterday Yay!
    • got some insights in issue handling and labeling of gap
    • labeled a few old issues
    • attended Sergio's talk and listened to Chris
    • read some code of the BacktrackKit

  • Lucas Wollenhaupt

    • continued with the pull requests
    • listened to Sergios talk
    • learned about the BacktrackKit
    • participated in the discussion about handling of Issues\PRs
    • became a member of the GAP contributors :)

  • Sebastian Gutsche

    • Finished a first version of pragmas, based on ST implementation for checking
    • Currently a PR to Max repo, needs to be against gap-system of course
      but the ST PR is also still missing

  • Johannes Hahn

    • Attended both talks
    • Reviewed my code for Coxeter groups from years ago in order to make it into a proper package

  • Sergio Siccha

    • prepared my talk
    • attended my talk
    • got feedback by Rebecca that a running example would have been nice
    • attended Chris' talk

  • Michael Torpey

    • Worked on PackageManager
      • Support for .tar.bz2 archives
      • InstallRequiredPackages
      • Installing a specific git branch
    • Learned about partition backtrack
    • Made a pull request to GAPDoc (merged!)
    • Didn't help with Digraphs (sorry!)

  • Max Im Um Horn

    • Participated in various discussions on GitHub issues and other stuff
    • … pull requests …
    • some minor work on recog
    • a very little progress on MatrixObj
    • … more pull requests …

  • Mun See Chang

    • learned about BacktrackKit

  • Leonard Soicher

    • Released GRAPE 4.8.2
    • Learned more about normalisers and partition backtrack

Day 5: Friday 22nd

Dinner on Friday

A group of us will be meeting at 19:00 outside (/inside, if possible) Ahn Asia, 41 Große Ulrichstraße. If we are unable to be seated there (they don't take reservations), then we will eat at House of India instead (where we ate on Monday). If you're still in Halle, you're welcome to come along.

Plans for the day

  • Wilf Wilson

  • Rebecca Waldecker

    • Thank everyone, also the people who helped behind the scenes!
    • Should we have GAP days in Halle again sometimes?

  • Finn Smith

    • Investigate performance of edge-coloured digraph automorphisms encoding on real examples (thanks Markus!)

  • Chris Jefferson

    • Work on a new testing library, using random inputs

Results and accomplishments

  • Rebecca Waldecker

    • My functions work, now I'll improve them!
    • More interesting conversations today, thanks. :)

  • Anna Sucker

    • I got to know the AtlasRep package in gap
    • learned a bit about Automorphism groups

Summer School Matrix Group Recognition in Aachen

1.7.2019 – 5.7.2019

Webpage: https://lbfm-rwth.github.io/Summer-School-MGRP

Select a repo