Research interests

Abstract algebraic algorithms

Algebraic computation research includes the design, development, implementation, application and analysis of algorithms for computer use in abstract algebraic problem solving. Work is being undertaken on various procedures for computations in groups and related structures: coset enumeration; p-quotient calculation; subgroup presentation; and presentation manipulation. Programs implementing these algorithms have been incorporated into coherent packages of machine implementations for the study of algebraic structures including Gap (Germany), Magma (Australia) and Quotpic (UK).

A nilpotent quotient algorithm for graded Lie rings [More]
Coset enumeration strategies [More]
Algorithms for groups [More]
Application of substring searching methods to group presentations [More]
Application of computational tools for finitely presented groups [More]
A new problem in string searching [More]
Groups of deficiency zero [More]
Central factors of deficiency zero groups [More]
Practical parallel coset enumeration [More]
Symmetric presentations and orthogonal groups [More]
Automorphism groups of certain non-quasiprimitive almost simple graphs [More]
On the automorphism groups of quasiprimitive almost simple graphs [More]
A family of non-quasiprimitive graphs admitting a quasiprimitive 2-arc transitive group action [More]
A presentation for the Lyons simple group [More]
On Sims' presentation for Lyons' simple group [More]
Groups with exponent six [More]
Elementary Algebra Revisited: Randomized Algorithms [More]
Computing in groups with exponent six [More]
Some challenging group presentations [More]
Experiments in coset enumeration [More]
Proving a group trivial made easy: a case study in coset enumeration [More]
A presentation for the Thompson sporadic simple group [More]
Certain cyclically presented groups are infinite [More]
Parallel coset enumeration using threads [More]
Efficient simple groups [More]
Andrews-Curtis and Todd-Coxeter proof words [More]
Breadth-first search and the Andrews-Curtis conjecture [More]
Irreducible cyclic presentations of the trivial group [More]
Short balanced presentations of perfect groups [More]
On the efficiency of some finite groups [More]
4-Engel groups are locally nilpotent [More]
Experimenting with infinite groups, I [More]
Nice efficient presentations for all small simple groups and their covers [More]
Efficient presentations for the Mathieu simple group M22 and its cover [More]
Certain Roman and flock generalized quadrangles have nonisomorphic elation groups [More]
Computing with elation groups [More]
The Fa,b,c conjecture is true, I [More]
Computing with 4-Engel groups [More]
On proofs in finitely presented groups [More]
The Fa,b,c conjecture is true, II [More]

Combinatorial computation

Combinatorial computation is basic to pure research, new technologies and product development. Work is being done to design, implement, test, analyse and apply effective fundamental combinatorial algorithms on high performance computers. This means designing new algorithms, redesigning old ones, and using such algorithms to solve problems where current techniques are inadequate.

Counting trees [More]
Finding the k most vital edges with respect to minimum spanning trees for k=2 and 3 [More]
Improved Lightpath (Wavelength) Routing in Large WDM Networks [More]
On routing in circulant graphs [More]
Finding a Low-Diameter and Low-Weight k-Connected Subgraph [More]

Computing canonical forms of matrices

The existence of canonical forms for integer matrices (and for matrices over other rings) has been known since the middle of the last century. The computation of canonical forms for matrices has important applications in both theoretical and practical areas of mathematics, science and engineering. This project aims to design, implement, test and analyze effective computer algorithms and data structures for computing canonical forms of matrices over various rings and fields, with a view to application to research problems in the areas associated with the matrices. Algorithms developed in this project are incorporated into leading systems for computational algebra and number theory, including Gap (Germany), Magma (Australia), Lidia (Germany), Quotpic (UK) and Pari (France). A fundamental building block for canonical matrix algorithms is provided by extended gcd algorithms.

Recognizing badly presented Z-modules [More]
Hermite normal form computation for integer matrices [More]
Integer matrix diagonalization [More]
On the worst-case complexity of integer Gaussian elimination [More]
Extended gcd and Hermite normal form algorithms via lattice basis reduction [More]
Matrix reduction algorithms for Euclidean rings [More]
Elementary Algebra Revisited: Randomized Algorithms [More]
Some Performance Studies in Exact Linear Algebra [More]

Greatest common divisors

Extended gcd calculation has a long history and plays an important role in computational number theory and linear algebra. Extended gcd algorithms are studied both in theory and in practice. Keith Matthews provides a very informative and useful link to computational number theory.

The complexity of greatest common divisor computations [More]
Extended gcd algorithms [More]
A solution to the extended gcd problem [More]
Extended gcd calculation [More]
A hard problem that is almost always easy [More]
A new algorithm and refined bounds for extended gcd computation [More]
Extended gcd and Hermite normal form algorithms via lattice basis reduction [More]
Elementary Algebra Revisited: Randomized Algorithms [More]
GCD of many integers [More]
The complexity of the extended GCD problem [More]

Perfect hashing

A classic problem in computer science is how to store information so that it can be searched and retrieved efficiently. Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. The aim of the project is to investigate, both from theoretical and practical points of view, algorithms for generating perfect hash functions. Software based on these algorithms and data structures is available in systems for data management and the Linux software library.

An optimal algorithm for generating minimal perfect hash functions [More]
Graph theoretic obstacles to perfect hashing [More]
Graphs, hypergraphs and hashing [More]
A family of perfect hashing methods [More]
Perfect Hashing [More]

Distributed and parallel algorithms

With the increasing availability of multiprocessor systems, good algorithms for both distributed and parallel environments are most important. The aim of this project is to design, develop, implement and analyze leading edge algorithms for these contexts.

Reconstructing a distributed depth-first-search tree after network topology changes [More]
Empirical analysis of distributed depth-first search algorithms [More]
Distributed algorithms for depth-first search [More]
An efficient method for constructing a distributed depth-first search tree [More]
Approximation Algorithms for 2-Connectivity Augmentation in A Graph [More]
Finding the k most vital edges with respect to minimum spanning trees for k=2 and 3 [More]
Parallel approximate edge coloring revisited [More]
Improved Lightpath (Wavelength) Routing in Large WDM Networks [More]
On routing in circulant graphs [More]
Finding a Low-Diameter and Low-Weight k-Connected Subgraph [More]

Algorithms and applications in finite fields

One of the most important properties of a finite field is that any function defined on it can be represented as a polynomial. Different classes of polynomials which have special types of behaviour are important because of their applications in areas such as cryptography, combinatorics and finite geometries. The aim of this project is to study the behaviour of classes of polynomials by computational and theoretical methods and to develop applications of the results obtained.

Functional decomposition of a class of wild polynomials [More]
Giesbrecht's algorithm, the HFE cryptosystem and Ore's ps-polynomials [More]
On decomposition properties of sub-linearised polynomials [More]

Algorithm analysis

Important questions about algorithms include: How hard is an algorithm? What can/cannot be computed by an algorithm given limited resources (space, time)? Such questions are addressed in many of the above papers, sometimes theoretically, sometimes practically. Also:

On the Complexity of the Extended Euclidean Algorithm
Electronic Notes in Theoretical Computer Science 78 (2003)
Full Text (PDF 81Kb) Full Text (PostScript 121Kb)

Last updated: 4 February 2006