The product replacement algorithm is polynomial

The product replacement algorithm is a heuristic designed to generate random group elements. The idea is to run a random walk on generating /spl kappa/-tuples of the group, and then output a random component. The algorithm was designed by C. R. Leedham-Green, and further investigated by F. Cellar et al. (1995). It was found to have an outstanding performance, much better than the previously known algorithms (P. Diaconis and L. Saloff-Coste, 1996). The algorithm is now included in two major group algebra packages: GAP (M. Scheonert et al. , 1995) and MAGMA (W. Bosma et al. , 1997). In spite of the many serious attempts and partial results, the analysis of the algorithm remains difficult at best. For small values of /spl kappa/, even graph connectivity becomes a serious obstacle. The most general results are due to Diaconis and Saloff-Coste, who used a state of the art analytic technique to obtain polynomial bounds in special cases, and (sub)-exponential bounds in the general case. The main result of the paper is a polynomial upper bound for the cost of the algorithm, provided /spl kappa/ is large enough.

Authors

• Igor Pak

Keywords

• Polynomials
• Mathematics
• Heuristic algorithms
• Algebra
• Packaging
• Upper bound
• Costs
• Random number generation
• Nearest neighbor searches
• Tail
• Random Walk
• Proof Of Theorem
• Production Run
• Universal Constant
• Abelian Group
• Finite Group
• Uniform Flow
• Walking Step
• Path Points
• Total Variation Distance
• Edge Path
• Edge Labels
• Nilpotent Groups