Archive

Archive for the ‘report’ Category

Computing Partition Monoids – 3 weeks down under

July 24, 2013 Leave a comment

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:

DSC02631

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.

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

DSC02618JDM’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

June 15, 2013 1 comment

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:

  DSC02547
Vertical screen space is important. We like WQHD monitors.

DSC02546

Code recycling – just bring your unused subroutines!

or

James does not produce trash code!

or

Code! if you have 5 minutes to spare…

 DSC02552

Still thinking about the holonomy decomposition…

DSC02539

Checking the semantics of the compact notation.

Categories: report

2013 SgpDec Winter Code Camp

March 5, 2013 1 comment

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.

hotelcoding

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.

sgpdecheads

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 D-class structure of the wreath product of full transformation semigroup T_3 and T_2

T_3wrT_2

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

Categories: report

2012 SgpDec Summer Code Camp

July 6, 2012 2 comments

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.

Image

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.
Image
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.
Image
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.

Image

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.

Categories: report Tags: ,