Enhancing Group Search with Graph Techniques
Lead Research Organisation:
University of St Andrews
Department Name: Computer Science
Abstract
Group theory is a field in mathematics which investigates algebraic structures called groups, which can be used to describe the symmeties of any object. Thus, group theory has wide-reaching applications in virology, quantum computing, cyber security and communications theory. Groups are also used in finding and reducing symmetries within search problems, which is vital in modern Artificial Intelligence. So finding groups, their properties and computing fundamental group operations as fast as possible, is at the core of many UK world leading research areas and will have wide reaching impact in economic successes.
There is an inherit circular improvement that will come from the research in algorithms in group theory, as one of the computational techniques used in finding subgroups, their properties or computing operations is a type of search algorithm itself. Thus, improving search in groups will improve the search for other applications as well.
The current search techniques in groups are advanced but are still struggling with scaling issues. We are proposing to use search techniques commonly used in graph search problems and apply them to group theoretical search algorithms. Such techniques are
(1) (learned) nogood clauses during search which then will inform further search steps,
(2) restarting the search from the top at well defined intervals, and
(3) using weighted orderings on the search decisions.
We have found that using these techniques in graph problems sped up the search by at least two orders of magnitude. We expect the performance improvements to be the same or better across the board in group problems.
Further, these techniques allow for a simple way of parallelising the current sequential algorithms, without the need to design/engineer a whole new algorithm. Speeding up algorithms which solve group problems and enabling them to be easily parallelisable will further impact applications such as virology, where group theory is used to describe the structural and geometrical properties of viruses.
There is an inherit circular improvement that will come from the research in algorithms in group theory, as one of the computational techniques used in finding subgroups, their properties or computing operations is a type of search algorithm itself. Thus, improving search in groups will improve the search for other applications as well.
The current search techniques in groups are advanced but are still struggling with scaling issues. We are proposing to use search techniques commonly used in graph search problems and apply them to group theoretical search algorithms. Such techniques are
(1) (learned) nogood clauses during search which then will inform further search steps,
(2) restarting the search from the top at well defined intervals, and
(3) using weighted orderings on the search decisions.
We have found that using these techniques in graph problems sped up the search by at least two orders of magnitude. We expect the performance improvements to be the same or better across the board in group problems.
Further, these techniques allow for a simple way of parallelising the current sequential algorithms, without the need to design/engineer a whole new algorithm. Speeding up algorithms which solve group problems and enabling them to be easily parallelisable will further impact applications such as virology, where group theory is used to describe the structural and geometrical properties of viruses.
