The product replacement prospector.
type: Item
instance of: scholarly article
title: The product replacement prospector.
zbMATH Open document ID: 1245.20001
author: Henrik Bäärnhielm
author: C. R. Leedham-Green
published in: Journal of Symbolic Computation
publication date: 2011-12-21T00:00:00Z
review text: Many algorithms in computational group theory depend on being able to compute a list of independent random elements from a large group \(G\) where the group is defined by a small generating set and an appropriate group operation (technically, we are working with a black box group). The most popular program currently used to generate such elements is the product replacement algorithm (PRA) [\textit{F. Celler, C. R. Leedham-Green, S. H. Murray, A. C. Niemeyer} and \textit{E. A. O'Brien}, Commun. Algebra 23, No. 13, 4931-4948 (1995; Zbl 0836.20094)] which has the virtue of being quite fast. Although extensively studied, the theoretical basis for the PRA is still weak. However, experimental evidence indicates that in practice the PRA produces roughly random elements which are not too dependent. (It has been shown that the mixing time for the PRA is bounded by a polynomial in \(\ln|G|\) but in practice the algorithm is never run for sufficiently long to reach the bounds proved to ensure adequate mixing.) Fortunately in many applications we are only concerned to find an element from a subset \(S\subseteq G\) where \(|G|/|S|\) is polynomial in \(\ln|G|\) and in these cases the PRA seems to work well. The present paper proposes a new heuristic to improve the PRA. It keeps a new temporary list (called the sampler) which is statistically tested from time to time to see whether recently generated elements appear random. If they are sufficiently random then the algorithm continues, but if they are not then the algorithm backtracks. All of the elements generated can be stored as short straight line programs. The new algorithm (called the product replacement prospector) has been implemented in the computer algebra system MAGMA and experimental evidence suggests that it is superior to the PRA.
reviewed by: John D. Dixon
Mathematics Subject Classification ID: 20-04
Mathematics Subject Classification ID: 20P05
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 5991114
zbMATH Keywords: computational group theory
zbMATH Keywords: black-box groups
zbMATH Keywords: product replacement algorithm
zbMATH Keywords: random elements
describes a project that uses: GAP
describes a project that uses: ATLAS Group Representations
describes a project that uses: Magma
MaRDI profile type: Publication
full work available at URL: j.jsc.2011.08.017
OpenAlex ID: W2081165772
cites work: Q4240509
cites work: Strong bias of group generators: an obstacle to the “product replacement algorithm”
cites work: The Magma algebra system. I: The user language
cites work: Generating random elements of a finite group
cites work: Q3684278
cites work: Moderate growth and random walk on finite groups
cites work: Comparison techniques for random walk on finite groups
cites work: Generating random elements in finite groups.
cites work: The Distribution of Chi-Square
cites work: Q4781984
cites work: Constructive recognition of classical groups in odd characteristic.
cites work: The computational matrix group project.
cites work: What do we know about the product replacement algorithm?
cites work: Karl Pearson and the Chi-Squared Test
cites work: Q4787523
DOI: 10.1016/J.JSC.2011.08.017
description: scientific article; zbMATH DE number 5991114