Visualising Fully Persistent Balanced Trees

A data structure is “partially persistent” if all past versions can be accessed via some kind of date stamp, even after subsequent operations have changed the structure. It is “fully persistent” if those structures can also be modified, creating a tree of versions, a bit like a badly managed git repository. The papers linked below […]

Continue reading

Linear Algebra over Finite Fields on a GPU

Many problems in mathematics and computer science come down to matrix multiplication where the matrix entries are integers considered modulo a prime p. Quite often p is 2, but other primes are also interesting. A great deal of effort has been put into optimizing this calculation on multicore CPUs. On our 64 core server, for […]

Continue reading

Parallel Algorithms for Permutation Groups

Computation with permutation groups is one of the basic pillars of computational discrete mathematics. In 1987 in the paper linked below, Babai, Kantor and Seress showed that a number of key permutation group problems lie in the complexity class NC. This contains highly parallelizable problems, where an instance of size n can be solved very […]

Continue reading

Combinatorial Games and Surreal Numbers

This is a broad topic area, rather than a specific project.  There are a number of possible projects in this area and I would be happy to work with an interested student (or several students) to formulate a project or projects. The area is essentially defined by a number of Books: “On Numbers and Games” […]

Continue reading

Cache and multi-core efficient algorithms for high-degree permutations

Permutations (bijective maps between the integers 1..n and themselves) are one of the most basic data types in computational mathematics. Algorithms for permutations have been developed at least since the 1960s, and are widely used. With modern computers it is reasonable to work with permutations on hundreds of millions or billions of points.  However the very […]

Continue reading

Coroutines and checkpointing in GAP

The GAP system (www.gap-system.org) has at its heart an interpreter for the GAP language, a dynamically-typed procedural language not dissimilar to Python.  Millions of lines of GAP code are incorporated into the GAP system and extension packages.  At present, while execution of a GAP function can be terminated by the return statement, or interrupted by […]

Continue reading