Certifying a probabilistic parallel modular algorithm for rational univariate representation

2021/06/21 by Parisse, Bernard
#FOS: Computer and information sciences #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.2106.10912

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 \refprop: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.

Related

• Solving via modular methods
• Massively Parallel Modular Methods in Commutative Algebra and Algebraic Geometry
• A probabilistic and deterministic modular algorithm for computing Groebner basis over \Q
• Integer Polynomial Factorization by Recombination of Real Factors: Re-evaluating an Old Technique in Modern Era
• Computing Modular Polynomials