Dense Gaussian elimination yields a practical, certified Julia solver for rational univariate representations of zero-dimensional ideals with thousands of solutions in seconds.
Certifying a probabilistic parallel modular algorithm for rational univariate representation
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This paper is about solving polynomial systems. It first recalls how to do that efficiently with a very high probability of correctness by reconstructing a rational univariate representation (rur) using Groebner revlex computation, Berlekamp-Massey algorithm and Hankel linear system solving modulo several primes in parallel. Then it introduces a new method (theorem \ref{prop:check}) for rur certification that is effective for most polynomial systems.These algorithms are implemented in https://www-fourier.univ-grenoble-alpes.fr/~parisse/giac.html since version 1.7.0-13 or 1.7.0-17 for certification, it has (July 2021) leading performances on multiple CPU, at least for an open-source software.
fields
cs.SC 1years
2026 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Fast Rational Univariate Representation via Gaussian Elimination
Dense Gaussian elimination yields a practical, certified Julia solver for rational univariate representations of zero-dimensional ideals with thousands of solutions in seconds.