Biased tadpoles: a fast algorithm for centralizers in large matrix groups

Centralizers are an important tool in in computational group theory. Yet for large matrix groups, they tend to be slow. We demonstrate a O(√|G|(1/logε)) black box randomized algorithm that produces a centralizer using space logarithmic in the order of the centralizer, even for typical matrix groups of order 10²⁰ . An optimized version of this algorithm (larger space and no longer black box) typically runs in seconds for groups of order 10¹⁵ and minutes for groups of order 10²⁰. Further, the algorithm trivially parallelizes, and so linear speedup is achieved in an experiment on a computer with four CPU cores. The novelty lies in the use of a biased tadpole, which delivers an order of magnitude speedup as compared to the classical tadpole algorithm. The biased tadpole also allows a test for membership in a conjugacy class in a fraction of a second. Finally, the same methodology quickly finds the order of a matrix group via a vector stabilizer. This allows one to eliminate the already small possibility of error in the randomized centralizer algorithm.