arXiv preprint ·
Probably correct row echelon form in the F4 algorithm
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Symbolic Computation
A Structural Proof of the Lower Bound 21 for $3\times3$ Matrix Multiplication over $\mathbb F_2$
Generative Interpretability via Scalable Neuro-Symbolic Models
LogicTrack: Auditing Reasoning Trajectories of Large Language Models with Formal Logic Solvers
Diversity of EML-type operators
Linguistic Features for Interpretable Textual Entailment
Get the few papers worth your time in Symbolic Computation every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.