48 citations · 62 across the 14 of their papers we have counts for
15 papers
Computing points in connected components defined by a real inequation: algorithms, complexity and implementations, Part I
Jérémy Berthomieu, Edern Gillot, Mohab Safey El Din
We consider the problem of computing sample points in each connected component of a semi-algebraic set defined by the non-vanishing or the positivity of an n-variate polynomial of…
Multiword matrix multiplication over large finite fields in floating-point arithmetic
Jérémy Berthomieu, Stef Graillat, Dimitri Lesnoff +1
This article is concerned with the efficient computation of modular matrix multiplication C=AB mod p, a key kernel in computer algebra. We focus on floating-point arithmetic, which…
Computing submatrices of the Hermite normal form of a structured polynomial matrix
Jérémy Berthomieu, Vincent Neiger, Hugo Passe
Following several decades of successive algorithmic improvements, works from the 2010s have showed how to compute the Hermite normal form (HNF) of a univariate polynomial matrix wi…
Extracting Linear Relations from Gröbner Bases for Formal Verification of And-Inverter Graphs
Daniela Kaufmann, Jérémy Berthomieu
Formal verification techniques based on computer algebra have proven highly effective for circuit verification. The circuit, given as an and-inverter graph, is encoded as a set of…
Computing Generic Fibers of Polynomial Ideals with FGLM and Hensel Lifting
Jérémy Berthomieu, Rafael Mohr
We describe a version of the FGLM algorithm that can be used to compute generic fibers of positive-dimensional polynomial ideals. It combines the FGLM algorithm with a Hensel lifti…
Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems
Alin Bostan, Jérémy Berthomieu, Andrew Ferguson +1
We consider ideals involving the maximal minors of a polynomial matrix. For example, those arising in the computation of the critical values of a polynomial restricted to a variety…
New efficient algorithms for computing Gröbner bases of saturation ideals (F4SAT) and colon ideals (Sparse-FGLM-colon)
Jérémy Berthomieu, Christian Eder, Mohab Safey El Din
This paper is concerned with linear algebra based methods for solving exactly polynomial systems through so-called Gröbner bases, which allow one to compute modulo the polynomial i…
Faster change of order algorithm for Gröbner bases under shape and stability assumptions
Jérémy Berthomieu, Vincent Neiger, Mohab Safey El Din
Solving zero-dimensional polynomial systems using Gröbner bases is usually done by, first, computing a Gröbner basis for the degree reverse lexicographic order, and next computing…
Polynomial-Division-Based Algorithms for Computing Linear Recurrence Relations
Jérémy Berthomieu, Jean-Charles Faugère
Sparse polynomial interpolation, sparse linear system solving or modular rational reconstruction are fundamental problems in Computer Algebra. They come down to computing linear re…
msolve: A Library for Solving Polynomial Systems
Jérémy Berthomieu, Christian Eder, Mohab Safey El Din
We present a new open source C library \texttt{msolve} dedicated to solving multivariate polynomial systems of dimension zero through computer algebra methods. The core algorithmic…
On the computation of asymptotic critical values of polynomial maps and applications
Jérémy Berthomieu, Andrew Ferguson, Mohab Safey El Din
Let be a polynomial tuple in and let . We consider the problem of comput…
Guessing Gr{ö}bner Bases of Structured Ideals of Relations of Sequences
Jérémy Berthomieu, Mohab Safey El Din
Assuming sufficiently many terms of a n-dimensional table defined over a field are given, we aim at guessing the linear recurrence relations with either constant or polynomial coef…
In-depth comparison of the Berlekamp--Massey--Sakata and the Scalar-FGLM algorithms: the adaptive variants
Jérémy Berthomieu, Jean-Charles Faugère
The Berlekamp--Massey--Sakata algorithm and the Scalar-FGLM algorithm both compute the ideal of relations of a multidimensional linear recurrent sequence.Whenever quering a single…
In-depth comparison of the Berlekamp -- Massey -- Sakata and the Scalar-FGLM algorithms: the non adaptive variants
Jérémy Berthomieu, Jean-Charles Faugère
We compare thoroughly the Berlekamp -- Massey -- Sakata algorithm and the Scalar-FGLM algorithm, which compute both the ideal of relations of a multi-dimensional linear recurrent s…
Polynomial-Time Algorithms for Quadratic Isomorphism of Polynomials: The Regular Case
Jérémy Berthomieu, Jean-Charles Faugère, Ludovic Perret
Let and be two sets of nonlinear polynomials over ( being a fie…