Computational group theory
Encyclopedia
In mathematics
, computational group theory is the study of
group
s by means of computers. It is concerned
with designing and analysing algorithm
s and
data structure
s to compute information about groups. The subject
has attracted interest because for many interesting groups
(including most of the sporadic groups) it is impractical
to perform calculations by hand.
Important algorithms in computational group theory include:
Two important computer algebra system
s (CAS) used for group theory are
GAP
and Magma
. Historically, other systems such as CAS (for character theory
) and Cayley (a predecessor of Magma) were important.
Some achievements of the field include:
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, computational group theory is the study of
group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
s by means of computers. It is concerned
with designing and analysing algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s and
data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s to compute information about groups. The subject
has attracted interest because for many interesting groups
(including most of the sporadic groups) it is impractical
to perform calculations by hand.
Important algorithms in computational group theory include:
- the Schreier–Sims algorithm for finding the order of a permutation groupPermutation groupIn mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose group operation is the composition of permutations in G ; the relationship is often written as...
- the Todd–Coxeter algorithm and Knuth–Bendix algorithm for coset enumerationCoset enumerationIn mathematics, coset enumeration is the problem of counting the cosets of a subgroup H of a group G given in terms of a presentation. As a by-product, one obtains a permutation representation for G on the cosets of H...
- the product-replacement algorithm for finding random elements of a group
Two important computer algebra system
Computer algebra system
A computer algebra system is a software program that facilitates symbolic mathematics. The core functionality of a CAS is manipulation of mathematical expressions in symbolic form.-Symbolic manipulations:...
s (CAS) used for group theory are
GAP
GAP computer algebra system
GAP is a computer algebra system for computational discrete algebra with particular emphasis on computational group theory.-History:...
and Magma
Magma computer algebra system
Magma is a computer algebra system designed to solve problems in algebra, number theory, geometry and combinatorics. It is named after the algebraic structure magma...
. Historically, other systems such as CAS (for character theory
Character theory
In mathematics, more specifically in group theory, the character of a group representation is a function on the group which associates to each group element the trace of the corresponding matrix....
) and Cayley (a predecessor of Magma) were important.
Some achievements of the field include:
- complete enumeration of all finite groups of order less than 2000
- computation of representations for all the sporadic groups