## GAP on the Pi

GAP is a system for computational discrete algebra… but I probably should not spend too much time introducing it. Either you know it very well, or you can get all the information from here. I work with it and develop for it every day. One good thing about it that its kernel is written in standard C, so it is easy to get it working on many different systems.

Raspberry Pi is a little computer that invokes 10% of the feeling of the good old days in the 8-bit era. If you think 10% is a low value, well, today’s computers give 0.1% of the inspiration we experienced back then in 80’s early 90’s, so comparatively Raspberry Pi is doing very well. Again, no need to introduce it. In case you haven’t heard of it, then it is time to catch up. Here or here.

I ordered two of these without knowing what to do with them. One I gave away as a gift, the second one I tried it as a media center. Spectacular success, though my friends were not so excited. The general opinion was that it did not matter on what sort of gadget we watched the movie… Hm, I simply don’t understand people… 🙂

So as a next step I put Arch Linux on it. When I got to the command line (few seconds) I realized that GAP was missing. It takes 106 minutes to compile it form source (mainly because of the GMP library) but then, of course, it works nicely.

Later I got carried away and installed the GUI packages as well.

Here is the Raspberry Pi calculating the holonomy decomposition of the full transformation semigroup on 5 points. As a nontrivial but very simple exercise.

Yes, nontrivial calculations require all the processor power, but the chip does not get too hot. Without any cooling… It is not fast, but requires little power.

Why doing this? Certainly not for the performance gain. Heavy mathematical calculations are really slow on the Pi, but that is exactly the point. When testing new algorithms it is easier to detect performance bottlenecks on a slower machine. We get lazy on big rigs and don’t produce quality code, unlike in the 8-bit era, where lousy programming yielded no result at all. So, if your algorithm works on the Pi then it will not waste kilowatts on the research cluster.

Also, we develop mathematical software and produce mathematical results eventually used in proofs. Computer calculated results have to be checked carefully. Ideally, given an algorithm we would implement it on two different platforms, using different programming languages developed by two independent teams. That is a luxury we simply cannot afford. However, Raspberry Pi provides us the possibility to test the code on a different architecture at least.

Now I’m checking the availability of a C compiler for our washing machine… 😉

UPDATE: I sometimes use this system for software development. Due to its minimality, it is distraction-free.

## Computing Partition Monoids – 3 weeks down under

First of all, we have some name clashes, simply because now there are many persons named James in semigroup theory. So to get this right, here are the names appearing in this story, in alphabetical order:

- JE James East, University of Western Sydney
- ENA Attila Egri-Nagy, University of Western Sydney
- JDM James D. Mitchell, University of St Andrews

Pictorially:

This is a story of the latest development of the Semigroups package, but let’s put things into perspective.

In 2004 JDM inherited the Monoid package with the task of turning it into a GAP4 package as it was originally developed for GAP3. This was done, but after that he became unsure whether it was worth investing more time into the development. He felt that there was not much interest.

In 2010 ENA went St Andrews, determined to squeeze out a release from JDM with some new features needed for SgpDec. One man crowd with banners WE LIKE, WE NEED MONOID! RELEASE EARLY! RELEASE OFTEN! Apparently, this was convincing. JDM started to revise the code.

Around this time Monoid was renamed to Citrus. Much to the excitement then later disappointment for orange growers in Florida.

In 2011 JDM came to Eger, Hungary for the cute little algebra conference A^3. He started to write code for SgpDec and consequently making more upstream changes in Citrus.

Here comes the key point in this story. When including new code for partial permutations JDM was faced with a huge amount of copypaste-then-change-a-bit code. This did not feel right. There was an obvious need for more abstract code, meaning that most algorithms for transformation semigroups work for other semigroups as well. This is a very important moment for computational mathematics, as it is a prime example showing that math and computing is not a one-way relationship. Insights in software development can lead to more abstract and cleaner mathematical descriptions.

In 2012 the BIOMICS project started and they got the idea that inviting two developers is twice as good as inviting one, so JDM and ENA again had an opportunity to work together again (hinting the general semigroup action framework), again and again.

But it is time for JE appear on the scene. He and JDM met in Portugal (not for the first time) and talked about partition monoids. These are very interesting structures but without any efficient transformation representation, so these are objects that can really put the general framework to test. JDM in his energetic way did some coding to implement partition monoids in Semigroups, but more consultation was needed. This was not so easy since JE and JDM normally live at the other ends of the world.

In 2013, at the University of Western Sydney a new research centre for Mathematics (called CRM) was formed. The Centre have a program for inviting distinguished international visitors to work with UWS researchers. The more people the visitor can work with the better. JDM was an obvious candidate, and the visit did indeed happen between June 30-July22.

We took over the small meeting room for two weeks. Algorithms were discussed and tried on the board first. The whiteboard space was very limited, but nowadays you just take a shot with your mobile phone and erase the board.

Then the algorithms were immediately turned into GAP functions and methods and tested against the hand-calculated examples and known mathematical results.

JDM’s original estimate was one week, but it actually took 2 weeks to get some tangible results. As software development goes, the estimate was surprisingly accurate.

One example of these new computational results was the D-class picture of the full partition/Brauer monoids. Something that human eyes had never seen before. All in good timing for doing some marketing at the GAIA conference further down in Melbourne. JE gave a talk featuring these new images and there was also a backstage software demo for potential `customers’.

At GAIA we also observed something which must be a generational issue. We got the impression that not long ago mathematicians wrote and sang songs at conferences. What do we do now when we go back to the hotel room? We write code. 🙂 Also, the last row in the lecture room is not used for sleeping any more, it is used for software development. This is of course just an observation, not a judgement, but it seems that academic life was a wee bit more relaxed before.

All in all, as one can see in bitbucket commit messages and in the upcoming preprints, this was a very productive research visit and we also had time for some travel and bushwalks. Maybe a bit taxing on the families, but hopefully the 3 weeks of geek-life will be forgiven.

## 2013 GAP-SEMIGROUPS-SGPDEC (rainy) Summer Code Camp

Hatfield again, same people. Still BIOMICS funded. Many things happened at high speed. Both on the software and on the mathware side. Also, antisocial geek behaviour reached new heights, for instance sitting down at the dinner table, opening the laptop and telling the others “You may talk to me, but anything not code and math-related will be ignored…”

So, what is the progress?

We did beta testing of James’ development branch of GAP. The novelty here is that calculating with transformations now done in the kernel, which means SPEED!!! increase in every functions using transformations. Of course, having stuff in the kernel implies chasing nasty segmentation faults… but there was a happy end. So the new code is on the way to be included in the upcoming GAP 4.7.

Hand in hand with the new GAP release the semigroup packages are also updated. Citrus got renamed (again), the package is called Semigroups now, less fancy name, but more telltale. Saving future disappointments of orange farmers from Florida. Smallsemi was also hit by the wind of change, duplicate definitions had to be removed.

Following all these upstream changes, SgpDec also got its fair share of commits. Good things: the 0.7 development branch now has all the features of the old 0.6 branch. Everything is back, including holonomy decomposition. Bad thing: except some comments in the testfiles the package is completely devoid of any documentation. Something that will soon be rectified.

Talking of holonomy. We still believe in a short and elementary description of the proof. Working backwards from the working code, this will be part of the documentation.

We also agreed on how to make the one-line notation for finite transformations more compact. It is now called the compact notation.

Regarding the extreme programming part, the 8.5 hours long coding session in a cafe in Hatfield’s Galleria was… hm.. long. At the end of the day we cleaned up the datatypes in SgpDec. So it was very successful, discounting those lost three hours. The trouble came from the combination of these two mistakes:

1. I kept the test files separately, so James could not use them.

2. James continued where he finished in February, but “change as many things as possible at the same time” works fine in the beginning of the development, when everything is broken, but not when the codebase already has some consistency.

Reconciliation was successful. There are now proper test files for SgpDec and we also found those two swapped arguments that caused havoc everywhere.

Some photos:

Vertical screen space is important. We like WQHD monitors.

Code recycling – just bring your unused subroutines!

or

James does not produce trash code!

or

Code! if you have 5 minutes to spare…

Still thinking about the holonomy decomposition…

Checking the semantics of the compact notation.

## Interview: James East

James East is a lecturer in pure mathematics at University of Western Sydney, Australia. His research interest includes transformation semigroups, partition monoids/algebras and dual symmetric inverse monoids. As for the computational aspect he is old skool, i.e. pen and paper, but he inspired many of the upcoming changes in the Semigroups package and the semigroup functionality of GAP.

**By training, are you a mathematician or a software engineer?**

Mathematician

**How did you become involved in computational semigroup theory?**

It would be lying to say I’m really involved in computational semigroup theory! But a few problems I’m interested in working on soon would benefit from some help from GAP.

**What is your main research/development at the moment?**

Most of my current research centres around partition monoids, a class of monoids that arise in representation theory, but contain many important semigroups including the full transformation semigroups, and the symmetric and dual inverse semigroups. Inspiration for research is largely taken from classical transformation semigroup theory. There are different flavours in the finite and infinite cases.

I’m also interested in semigroup analogues of Coxeter groups or, equivalently, Coxeter analogues of transformation semigroups – examples include reflection and dual reflection monoids (special cases being the symmetric inverse semigroup and the factorizable part of the dual symmetric inverse semigroup on a finite set).

**What is your perspective on using computers in mathematical research?**

If it works, then I see no problems! Really, I like to be able to do things by hand, check them by hand, etc, but obviously this is not always possible. If I was the programmer, I’d always wonder if there was an error in my code somewhere, but then again, we do rely on results from papers we might not have been able to check carefully. Actually, I think there are some very interesting questions on epistemology arising from the use of computers in mathematics…

**What do you do in your free time?**I have a 1yo son, so free time is not as plentiful as it used to be, but what time I do have is divided among cricket, guitar, piano, whisky appreciation, and blogging (about philosophy).

## 2013 SgpDec Winter Code Camp

Half a year after the summer code camp we had another opportunity, this time funded by the BIOMICS project, to do `extreme coding’ on SgpDec. And we did. There are good and bad news.

The bad one is that we are back to square one. We branched the package code. The development version contains only cascade product functionality, no decompositions.

The good news is that it is a completely new and clean implementation, with precise mathematical documentation and better usage of GAP library and the Semigroups package code.

Here is what happened in detail.

**2013. February 2. Saturday** James arrived at Hatfield station. We walked to the Hatfield Mercure Hotel. I mention the location because they tolerated us working in the lobby for two days. Arguing about math and code passionately could be quite annoying to an outsider listener. I guess.

We spent the afternoon by checking how SgpDec can work without the now abandoned Citrus package and how compatible it is with the new Semigroups package. It sort of went OK but it took a few hours. However, the real benefit of doing this was that we finally understood each other. Yes, this means that half a year ago we did not understand James’ suggestions, and he did not fully get our goals. Well, so much about collaboration between like-minded. It still takes time.

By the evening we decided how to continue. Instead of patching here, welding other bits there on the existing codebase, we decided to start from scratch. Or almost from scratch. With the safety rope of the version control system (mercurial) we could just branch/remove/restart. Actually later we pushed it to its limits, we concurrently edited the same code, many and most of them big changes, so a merge got confused and interleaved two different functions. That was fun.

Late in the evening the SgpDec Steering Committee approved the decision for the complete overhaul, i.e. Chrystopher arrived and said: “Yes, good idea. Go ahead!”

**2013. February 3. Sunday** This was a 12-hours long hackathon. We might have had some fancy plans to go some other places, but we started coding early morning and we just stayed in the lobby of the hotel.

Our methodology was to remove some code, then I told James what the old functions did then he reimplemented it. This way we could get rid of old and now obsolete design decisions. Whenever he hit some difficulty, I just had to remember my situation years before and give him some hint. This worked very well, except when it did not. After 9 hours we hit the bottom and started to operate on the false assumptions that telling the same sentences louder and louder will make the other person understand. Well, here is agile software development for you… However, we survived this rather tricky situation (by having dinner, talking to family) and soon realized that we were talking about the same thing but with using slightly different terminology.

In any case, this day was a bit extreme. Here is a snapshot of the repository.

**2013. February 4-5. Monday-Tuesday **The tempo got a bit slower as the university was open and we met several people there, and talked a lot about the semigroup decompositions. But we still managed to get something well rounded. With the cascade products we can easily calculate the iterated wreath product of transformation semigroups. Here is the bird-eye view of the -class structure of the wreath product of full transformation semigroup and

or here is the original T_3wrT_2.pdf. James sent this from Luton airport on the way home, for our viewing pleasure.

## 2012 SgpDec Summer Code Camp

CAMPERS:

Paolo Dini

Attila Egri-Nagy

James D. Mitchell

Chrystopher Nehaniv

Maria Schilstra (on Wednesday)

LOCATION: University of Hertfordshire, Hatfield, England

**07.03.**

The meeting started with trying to connect to the big screen. Then we just used a projector.

An hour discussion of possible topics for the workshop.

SGPDEC UPDATE: The package is getting slimmer. Many functions needed for the holonomy decomposition are now included in Citrus. The visualisation functions got generalized and went into the separate Viz package. Then most recently some basic data structures were cut out of SgpDec and were moved to the (possibly transient package) Dust. The ultimate goal is that SgpDec will contain only the hierarchical coordinatization code and nothing else.

CITRUS UPDATE: James gave a 4hours version of the 20mins long Citrus intro talk. The performance of Citrus is impressive. What is more important, a new more general framework is emerging: generalizing from transformation semigroups to semigroup actions. This idea naturally comes from the software development process, but it looks like that this is going to be the next huge milestone in computational semigroup theory. This paradigm is bound to appear in SgpDec as well, possibly yielding new decomposition algorithms.

SGPDEC INSTALL SESSION: this was more difficult than expected. The script for compiling the packages was misbehaving. However, after an hour Chrystopher got it right and had the latest SgpDec running. James also, but hey, he is a GAP developer.

**07.04.**

PETRI NET SESSION: Guest talk by Maria Schilstra about biological modelling with Petri nets. Paolo’s Oregonator model. Chrystopher’s explanation how to turn a Petri net into an automaton. James now knows the origin of all those crazy semigroups we sent him to test Citrus’ performance.

In the afternoon we split up. Paolo and Maria worked on a Petri net simulator and we started to put together a TODO list for SgpDec.

CODING SESSION: Of course the first priority is to make SgpDec GAP 4.5 compliant. This looks like a simple administrative step but it turned out to be not so simple. To get James into the coding game we pushed the repository to bitbucket. This was followed by a high-speed commit-fix-push-pull-break-fix-again session. No added new functionality but code simplification and reorganizing yields performance improvements as well.

**07.05.**

TRANSFORMATION SEMIGROUP ENUMERATION: We started with the problem of enumerating the transformation semigroups. First a multiplication table reduction algorithm, then by using the results in the paper “Maximal Subsemigroups of Finite Semigroups”, by R. Graham, N. Graham and J. Rhodes) Jour. Comb. Th. 4 (1968), 203-209. After an overly optimistic start for recalculating the number for T3 we all agreed (again) that computers are indeed useful in semigroup theory.

CODING SESSION: Continuing the commit-push parade, used-only-once functions were inlined, redundant code removed. The most funny such redundant code was a doubly indexed array, i.e. finding an element, then finding its position, and finally returning the element with that index. Not in one line though, but still this is something to laugh at. Parallel commits yielded some conflicts but that is no problem with proper version control. Midnight saw a working version of SgpDec tagged as 0.6.41.

**07.06.**

The formal program of the Code Camp finished (James and Paolo returned home). However, the work continues with updating the documentation, doing more code revision (looking for skeletons – this was an insider joke 😉 and improving the display of the holonomy decomposition. This latter issue was discussed with Chrystopher today.

## New release: GAP 4.5.4

The long awaited new version of GAP is out now and it bundles together new versions of semigroup packages as well.

- Orb has new functionality to compute weak and strong orbits for semigroups and monoids.
- Citrus replaced the MONOID package for computing with transformation semigroups.
- Smallsemi, the database of small order semigroups is now included.

SgpDec will be updated soon.