Speeding Up Abstract Algebra
Abstract algebra, an area of advanced pure mathematics, is an essential but challenging element of university teaching across subjects from pure mathematics and computer science to physics, chemistry, and engineering. Software that automates the routine calculations of abstract algebra can be useful in helping learners to come to grips with challenging concepts without becoming bogged down with the technical details of the calculation. Researchers from the School of Computer Science have been integrating their work on key mathematical structures into leading software for computational abstract algebra, allowing their research to benefit thousands of users across multiple platforms around the world.
St Andrews researchers including Dr Olexandr Konovalov have made major progress linking mathematical software systems, both to each other and to associated tools such as modern user interfaces. One of the multiple projects concerned is OpenDreamKit, a European Research Infrastructure project which operated from 2015 to 2019 to bring mathematical software packages together. Their research has made major contributions to efficient, mathematically correct, and reliable links between diverse mathematical systems and popular user interface tools.
This work forms part of a much larger body of ongoing research in algorithms, systems, and applications around computational algebra, hosted within the Centre for Interdisciplinary Research in Computational Algebra (CIRCA) since its establishment in 2000. Bridging the School of Mathematics and Statistics and the School of Computer Science, CIRCA plays an ongoing role as a major centre for the development of the Groups, Algorithms, Programming (GAP) system. GAP is a software package which helps the user to calculate with complex mathematical objects, such as groups, semigroups, permutations, and matrices. GAP’s highly extensible design gives it the potential to cover many of the key disciplines in pure mathematics. As a result, the research insights of the team are frequently expressed as algorithms, databases, and software technologies distributed as part of GAP, which is itself used for teaching.
Twenty-five St Andrews researchers have contributed directly to the project. Their development of new algorithms for computing with semigroups has expanded GAP’s capabilities in the area, from almost nothing to a credible platform for teaching and researching what is a key topic in abstract algebra.
One of the key structures of abstract algebra are semigroups, which describe the transformations of physical and abstract objects and the ways in which they combine. St Andrews research on algorithms for semigroups has been essential to software for wide-ranging computation in this important topic. Co-written by Professor Steve Linton, “Computing Transformation Semigroups” is a foundational paper in the area. In 2012, researchers led by Professors Mitchell and Kelsey classified over 12 quintillion non-equivalent semigroups of order 10, and constructed a searchable library of the nearly two trillion that comprise the orders up to order 8.
Further St Andrews research sped up algorithms for permutation groups dramatically. Permutation groups are ubiquitous in mathematics, describing symmetries of objects and structures. Dr Christopher Jefferson played a key role in the development, implementation, and release of a family of new algorithms for some central problems in the area, outperforming the best existing implementations massively in some cases. On one test, Jefferson’s algorithm completed three times as many examples as the previous best-in class example in one-fifth of the time. These algorithms are widely used behind the scenes in mathematical software, so improving them speeds up user calculations across countless mathematical topics. Professor Colva Roney-Dougal had previously extended the classification of all primitive permutation groups from degree 1000 to degree 4095, adding nearly 17,000 new groups.
In 2008, Professor Max Neunhöffer worked with Australian mathematician Cheryl Praeger to develop a new algorithm, up to 200 times faster than alternatives, for calculating minimal polynomials, a similarly fundamental problem for matrices. This algorithm improves the speed of many common computations used in areas such as error-correcting codes and cryptography as well purely mathematical applications.
Integrating and Improving Software Systems
New algorithms developed at St Andrews have increased the speed of key computations across GAP as a whole. This allows students to work flexibly and interactively with more and larger examples of the mathematical objects they are studying. While the smallest examples of these computations can be done by hand or with older software, they often fail to represent the object’s typical form, which can mislead students.
Thanks to the group’s research on linking mathematical software, GAP is now also part of the broader SageMath software system and the CoCalc online scientific collaboration and teaching platform, enabling thousands of additional students to benefit from its capabilities. The team are responsible for GAP’s compatibility with the Jupyter notebook user interface, with which many students and teachers are familiar, and which is widely used in data science and scientific data analysis.
By adding new capabilities for computing with semigroups, new and faster algorithms for key problems, new databases, and new links to other systems, the group have enhanced software widely used in the teaching and learning of abstract algebra. Their work has improved teaching practices worldwide. Many teachers are now using computational software to teach abstract algebra, enabling them to make their courses more investigative and student-centred. These benefits extend to the roughly 20,000 weekly users of CoCalc due to the team’s work linking it to GAP.
Both GAP and SageMath are free for anyone to download and use. A recent survey of the use of GAP, SageMath and CoCalc in teaching found users across 23 countries, totalling nearly 6,000 users. This included courses delivered to over 2,500 students in at least seven African countries, many of whom were taking computer-supported courses in semigroup theory – something that would have been impossible without the research conducted by the team at St Andrews.
Researchers from CIRCA have made huge leaps in our understanding of complex and powerful mathematical concepts. By sharing their work through freely available software, and working to integrate powerful existing systems, they have ensured that thousands of mathematicians can benefit from their insights.