93 citations · 387 across the 28 of their papers we have counts for
23 papers · 1 filter
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…
Computing critical points for invariant algebraic systems
Jean-Charles Faugère, George Labahn, Mohab Safey El Din +2
Let be a field and , in be multivariate polynomials (with ) invariant under the action of $\m…
Gr{ö}bner Basis over Semigroup Algebras: Algorithms and Applications for Sparse Polynomial Systems
Matías Bender, Jean-Charles Faugère, Elias Tsigaridas
Gr{ö}bner bases is one the most powerful tools in algorithmic non-linear algebra. Their computation is an intrinsically hard problem with a complexity at least single exponential i…
A nearly optimal algorithm to decompose binary forms
Matías Bender, Jean-Charles Faugère, Ludovic Perret +1
Symmetric tensor decomposition is an important problem with applications in several areas for example signal processing, statistics, data analysis and computational neuroscience. I…
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…
Towards Mixed Gr{ö}bner Basis Algorithms: the Multihomogeneous and Sparse Case
Matías Bender, Jean-Charles Faugère, Elias Tsigaridas
One of the biggest open problems in computational algebra is the design of efficient algorithms for Gr{ö}bner basis computations that take into account the sparsity of the input po…
Bilinear systems with two supports: Koszul resultant matrices, eigenvalues, and eigenvectors
Matías Bender, Jean-Charles Faugère, Angelos Mantzaflaris +1
A fundamental problem in computational algebraic geometry is the computation of the resultant. A central question is when and how to compute it as the determinant of a matrix. whos…
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…
Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems
Jean-Charles Faugere, Pierre-Jean Spaenlehauer, Jules Svartz
B{é}zout 's theorem states that dense generic systems of n multivariate quadratic equations in n variables have 2 n solutions over algebraically closed fields. When only a small su…
Determinantal sets, singularities and application to optimal control in medical imagery
Bernard Bonnard, Jean-Charles Faugère, Alain Jacquemard +2
Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast b…
GBLA -- Gröbner Basis Linear Algebra Package
Brice Boyer, Christian Eder, Jean-Charles Faugère +2
This is a system paper about a new GPLv2 open source C library GBLA implementing and improving the idea of Faugère and Lachartre (GB reduction). We further exploit underlying struc…
On the complexity of computing Gröbner bases for weighted homogeneous systems
Jean-Charles Faugère, Mohab Safey El Din, Thibaut Verron
Solving polynomial systems arising from applications is frequently made easier by the structure of the systems. Weighted homogeneity (or quasi-homogeneity) is one example of such a…
Sparse Gröbner Bases: the Unmixed Case
Jean-Charles Faugere, Pierre-Jean Spaenlehauer, Jules Svartz
Toric (or sparse) elimination theory is a framework developped during the last decades to exploit monomial structures in systems of Laurent polynomials. Roughly speaking, this amou…
On the Complexity of the F5 Gröbner basis Algorithm
Magali Bardet, Jean-Charles Faugère, Bruno Salvy
We study the complexity of Gröbner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system. We…
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…
Sparse FGLM algorithms
Jean-Charles Faugère, Chenqi Mou
Given a zero-dimensional ideal I in K[x1,...,xn] of degree D, the transformation of the ordering of its Groebner basis from DRL to LEX is a key step in polynomial system solving an…
Polynomial Systems Solving by Fast Linear Algebra
Jean-Charles Faugère, Pierrick Gaudry, Louise Huot +1
Polynomial system solving is a classical problem in mathematics with a wide range of applications. This makes its complexity a fundamental problem in computer science. Depending on…
On the Complexity of Computing Gröbner Bases for Quasi-homogeneous Systems
Jean-Charles Faugère, Mohab Safey El Din, Thibaut Verron
Let $\K$ be a field and $(f_1, \ldots, f_n)\subset \K[X_1, \ldots, X_n]$ be a sequence of quasi-homogeneous polynomials of respective weighted degrees w.r.t a…
Critical Points and Gröbner Bases: the Unmixed Case
Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer
We consider the problem of computing critical points of the restriction of a polynomial map to an algebraic variety. This is of first importance since the global minimum of such a…
On the Complexity of Solving Quadratic Boolean Systems
Magali Bardet, Jean-Charles Faugère, Bruno Salvy +1
A fundamental problem in computer science is to find all the common zeroes of quadratic polynomials in unknowns over . The cryptanalysis of several modern cip…
On the Complexity of the Generalized MinRank Problem
Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer
We study the complexity of solving the \emph{generalized MinRank problem}, i.e. computing the set of points where the evaluation of a polynomial matrix has rank at most . A natu…
Gröbner Bases of Bihomogeneous Ideals generated by Polynomials of Bidegree (1,1): Algorithms and Complexity
Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer
Solving multihomogeneous systems, as a wide range of structured algebraic systems occurring frequently in practical problems, is of first importance. Experimentally, solving these…
Computing modular correspondences for abelian varieties
Jean-Charles Faugère, David Lubicz, Damien Robert
The aim of this paper is to give a higher dimensional equivalent of the classical modular polynomials . If is the -invariant associated to an elliptic curve $E_…