Home » visits

Category Archives: visits

Orbital graphs and constructive matrix recognition

Paula Hähndel (Martin-Luther-Universität Halle-Wittenberg) writes on her visit to St Andrews in Spring 2019, supported by CoDiMa:

“My stay in St Andrews was a great opportunity to meet the local GAP community. I was encouraged to continue my improvements of parts of the GAP documentation, and I used some of my time during my stay to do so. I also continued to discuss some ideas about orbital graphs with Markus Pfeiffer. One part of this was discussing ways to construct groups that have interesting orbital graphs, which would provide good test cases for the search algorithms that are developed by Wilf Wilson, Chris Jefferson and Markus.

I also gave a talk about constructive matrix group recognition and the discussion (mainly with Mun See Chang, Wilf and Chris) continued afterwards. We also discussed many of the details that are needed for implementation, but that were not addressed in the talk. This hopefully was a good preparation for the Summer School on Matrix Group Recognition in Aachen this year that us four will attend together. I am thankful for the opportunity to come. It was a really nice and productive time in St Andrews.”

Algorithms for black box groups

CoDiMa partially supported the visit of Prof. Alexandre Borovik (University of Manchester) to Dr Sukru Yalcinkaya (Istanbul University) on 8-21 September 2018. They reported the following:

In this short period of very intensive work in a small group (A. Borovik, S. Yalcinkaya (Istanbul University), and M. Lavrauw (Sabanci University)) we achieved a significant further progress towards efficient algorithms for analysis of black box groups representing classical linear groups over finite fields of odd characteristic. These results are highly significant for probabilistic methods of computational group theory. Unlike much of the previously existed methods which were conditional on the existence of Discrete Logarithm Oracles, our algorithms run in time polynomial in input length, work for very large sizes of fields without use of oracles of any kind and have been successfully tested for prime fields of order about 10^70.

Computations in small overlap monoids

For several days in June 2018, Mark Kambites (Manchester) visited James Mitchell in St Andrews, supported by the CoDiMa research visits programme. The visit allowed Mark Kambites and James Mitchell to discuss algorithms for performing computations in small overlap monoids. Efficient algorithms for various problems in this important class of finitely presented monoids were developed by Mark in a series of papers published between 2007 and 2011. The most basic of these (to solve the word problem) was implemented by Mark himself in the GAP SmallOverlap package in 2008. James and students have recently re-implemented this much more efficiently, and also begun to implement Mark’s other algorithms for more sophisticated tasks such as computing normal forms. However, they have encountered some problems with practical implementation of the algorithms in Mark’s papers. The visit allowed James to explain these issues, and Mark to clarify how some of the algorithms were supposed to function. In addition, the visit allowed Mark to attend the 28th NBSAN meeting, which provided a valuable opportunity for discussions with other experts in the field.

Symmetry vs Regularity: The first 50 years since Weisfeiler-Leman stabilization

Madeleine Whybrow reports:

With the support of CoDiMa, I attended the conference “Symmetry vs Regularity: The first 50 years since Weisfeiler-Leman stabilization” in Pilsen, Czech Republic. It was a very impressive event and nearly all of the major contributors to the field of algebraic graph theory over the past 50 years were present. There were some great talks presenting both the history of the area and also the new directions of research.

There was a strong computational theme throughout the conference and there were many stimulating talks and conversations on this topic. I gave a talk in which I presented my work with Markus Pfeiffer developing an algorithm in GAP to construct Majorana representations. This was well received and many people were very interested in our work, particularly in the methods that we use. Overall, it was an interesting and enjoyable week and I had the chance to meet lots of people and have lots of useful discussions.

Madeleine Whybrow’s second visit to St Andrews

I spent a week in St Andrews working with Markus Pfeiffer on an ongoing project which we are working on writing and implementing an algorithm to construct 2-closed Majorana representations. Funding for this trip was provided by CoDiMa.

Majorana algebras are non-associate algebras used to study the Monster group and its subgroups. They can be studied either in their own right, or as Majorana representations of certain groups. Many examples of Majorana algebras have been constructed by hand but it has become clear that, in order to construct bigger and more interesting algebras, a more computational approach is needed.

In a celebrated paper in 2012, Akos Seress announced the existence of an algorithm to constuct 2-closed Majorana representations. Sadly Seress passed away in 2013 and the full details of his algorithm and his results were never published. Recovering his work has been an important aim of the theory ever since.

This was my second visit funded by CoDiMa to work on this project. After the first visit, we had implemented such an algorithm and had started to reproduce Seress’ results. However, constructing Majorana representations is very expensive both in terms of time and memory and so the algorithm requires a lot of optimisation, which was the focus of our work this time around.

The week was a sucess and we have now completely recovered Seress’ results and we are expecting to shortly be able to construct representations larger than those achieved by Seress.

Our work is available on GitHub.

Madeleine Whybrow

8th International Workshop on Parallel Symbolic Computation (PASCO’17)

The 8th International Workshop on Parallel Symbolic Computation (PASCO’17) took place in Kaiserslautern, Germany, July 23-24, 2017, and was co-located with the International Symposium on Symbolic and Algebraic Computation (ISSAC’17). This instance of PASCO continued the mission of promoting and advancing parallel algorithms and software in all areas of mathematical computation. It therefore occupies a unique space in the landscape of international conferences and workshops, that brings together (parallel) systems developers and theoreticians in the broad area of mathematical software, in particular for symbolic computation. As in previous instances, PASCO’17 was generously supported by Maplesoft, who donated 2 Maple licences for the recipients of the best paper and the best student paper awards in the programme of PASCO’17. Details about the event can be found in the preface to the PASCO’17 proceedings, published in the ACM Digital Library: https://dl.acm.org/citation.cfm?id=3115936&picked=prox

The travel funding by Codima allowed me (Hans-Wolfgang Loidl) to attend this event, as General Chair for PASCO’17, in person and to oversee the running of the workshop. I was particularly pleased by the good attendance for the sessions of this event: the workshop programme contained a total of 13 contributed papers, reflecting the focused nature of this workshop, but attendance to the sessions was in the range of 30-40 academics and students, as well as representatives from Maplesoft and other companies. This reflects the wider interest in the high-performance aspects of this field.

From a Codima point of view, this was a good opportunity to flag the presence of this UK network and to strengthen its international connections. Codima members have been involved in the running of this event as General and Publicity chairs, and continue to take a leading role in the growing of this community. New links have been established between Codima members and the invited speakers from PASCO’17: the group in Glasgow is in collaboration with Prof Florent Hivert, on parallel symbolic algorithms in the area of semigroup enumeration. We hope to further firm up these links by inviting Prof Hivert for a research visit to Scotland.

Hans-Wolfgang Loidl (Heriot-Watt)

Wedderga package coding sprint

In November 2017, Sugandha Maheshwary (IISER Mohali, India) and Ángel del Río (Murcia, Spain) visited St Andrews for a Wedderga package coding sprint. The main goal of the coding sprint was to incorporate new code developed by Sugandha Maheshwary and Gurmeet Bakshi, and prepare a new release of the package which will be compatible with the new major release of GAP coming soon in 2018. The sprint resulted in the new major release of Wedderga. Beyond incorporating the new code, we improved other aspects of the package, including code coverage by the regression tests. In her reflections on the visit, Sugandha Maheshwary wrote:

I have been using and working with GAP for more than 3 years and wanted to contribute some functions. I visited University of St Andrews as a visitor of Dr Alexander Konovalov. During my stay I was trained for technical skills that are needed for the collaborative software development. I was part of the process of release of new version (4.9.0) of package named “Wedderga”, which gave me immense pleasure, confidence and motivation to contribute further. I was also introduced to Software Carpentry, which I would say is a must for beginners. My visit was largely funded by CoDiMa, and I am really grateful for the same.

Leonard Soicher’s visit to Portugal

The CoDiMa project supported my participation in “All Kinds of Mathematics Remind me of You: Conference to celebrate the 70th Anniversary of Peter J. Cameron“, held at the University of Lisbon, 24-27 July 2017. This conference brought together many colleagues, students and collaborators of Peter Cameron, and a diverse range of interesting mathematical research (covering Peter’s diverse range of interests) was presented and discussed.

This conference gave me the opportunity to present and discuss my recent algorithms and programs (in GAP/GRAPE) to exploit graph symmetry in graph colouring, in particular in the difficult problem of computing the chromatic number of a graph. I was also able to discuss the application of these programs to the determination of the “non-synchronizing” primitive permutation groups (of interest to researchers in semigroup and automata theory) of degree at most 255.

Leonard Soicher

Groups, Rings and the Yang-Baxter equation

In June 2017 Alexander Konovalov took part in the conference Groups, Rings and the Yang-Baxter equation” (Spa, Belgium). He gave a talk “GAP Group Rings Toolkit” with an overview of the functionality to work with group rings available in GAP and four of its packages, demonstrated the Jupyter kernel for GAP, and organised a coding sprint to work on the Wedderga package. As a result, Wedderga development version has been migrated from Bitbucket to GitHub (https://github.com/gap-packages/wedderga), and a new collaborator, Dr Sugandha Maheshwary (ISER Mohali), had submitted her first pull request to Wedderga.

Visitor Madeleine Whybrow: Constructing Majorana Representations in GAP

After meeting at the Workshop on Permutation Groups: Methods and Applications in Bielefeld in Germany, Markus Pfeiffer became interested in some computational work which I am developing as part of my PhD. He kindly invited me to St Andrews to spend a week working together on my code. Funding for this trip was provided by CoDiMa.

The work concerns developing and implementing an algorithm which can construct Majorana algebras, objects which occur in the study of the Monster group and its associated representation, the Griess algebra. In particular, I am interested in studying these algebras as Majorana representations of certain finite groups.

The algorithm takes as its input a finite group and a generating set of involutions. It considers all possible Majorana representations of the group with respect to the generating set and then, for each representation, either attempts to construct it or shows that it cannot exist.

In 2012, Akos Seress announced that he had constructed such an algorithm and published a list of groups whose Majorana representations he had been able to classify. However, Seress sadly passed away before he was able to publish the details of either his algorithm or of the representations which he had constructed. Reproducing his work has been an important aim of Majorana theory ever since.

The code is currently able to construct the Majorana representations of some groups, but we have not been able to reproduce the full results of Seress’ work. Together, we have been working on improving the methods in the algorithm to extend its capabilities. Improvements can come either from better implementation of the current methods, or from finding new approaches from theoretical work on the algebras.

This work is of particular interest as these algebras are defined over the reals and their construction involves some linear algebra over rational numbers. Improving GAP’s functionality over fields of characteristic zero is something which is being actively worked on and will benefit this problem as well as many others.

I also got the opportunity to present my work at the School of Mathematics and Statistics’ Pure Colloquium.

Overall, the week was very productive and we look forward to working together in the future.

 

Madeleine Whybrow