Probabilistic method speeds up main step in F4 algorithm
Probably correct row echelon form in the F4 algorithm
Symbolic ComputationData Structures and Algorithms
Summary
One tough step in the F4 algorithm is changing matrices into row echelon form, which can take a lot of time. Some current fast versions use a chance-based method but didn’t say how often it might mess up. The authors figured out a bound on the chance of error for this method. They also created a version of the F4 that uses randomness but checks its work to avoid mistakes, and showed it can run faster on standard problems.
What this means in practice
- •For computer algebra system developers: Improve algebra software performance by using a verified probabilistic step in computing row echelon forms within the F4 algorithm.
- •For cryptography software engineers: Speed up polynomial computations by integrating a practical randomized algorithm with error guarantees in cryptographic tools.
Authors
Alexander Demin
Abstract
The computation of row echelon form is one of the main bottlenecks in the F4 algorithm. Several state of the art implementations use a probabilistic algorithm attributed to Monagan, Pearce, and Steel to accelerate this computation. Despite this, no bound on the probability that the algorithm returns an incorrect result appears to be available. In this paper, we provide such a bound. Furthermore, building on this result, we propose a Las-Vegas variant of the F4 algorithm and show experimentally that it can outperform deterministic F4 on some classical examples.