Fast Parallel Computation with Permutation Groups

We develop fast parallel solutions to a number of basic problems involving solvable and nilpotent permutation groups. Testing solvability is in NC, and RNC includes, for solvable groups, finding order, testing membership, finding the derived series and finding a composition series. Additionally, for nilpotent groups, one can, in RNC, find the center, a central composition series, and point-wise stabilizers of sets. There are applications to graph isomorphism. In fact, we exhibit a class of vertex-colored graphs for which determining isomorphism is NC-equivalent to computing ranks of matrices Over small fields. A useful tool is the observation that the problem of finding the smallest subspace containing a given set of vectors and closed under a given set of linear transformations (all over a small field) belongs to RNC.

Authors

• Eugene M. Luks
• Pierre McKenzie

Keywords

• Concurrent computing
• Testing
• Linear algebra
• Information science
• Vectors
• Polynomials
• Parallel algorithms
• Encoding
• Councils
• Instruments
• Parallelization
• Permutation Group
• Proof Of Theorem
• Group Classification
• Linear Transformation
• Order Polynomial
• Series Of Derivatives
• Abelian Group
• Child Nodes
• Sequential Algorithm
• Cyclic Group
• Color Categories
• Normal Subgroup
• Subset Of Points
• Automorphism Group
• Composite Series
• Class Of Graphs
• Arbitrary Group
• Vector Space
• Homomorphism
• Direct Product
• Identity Transformation
• Commutative
• Brute Force