Skip to Main content Skip to Navigation
Journal articles

On the Complexity of the Generalized MinRank Problem

Jean-Charles Faugère 1 Mohab Safey El Din 1 Pierre-Jean Spaenlehauer 1, 2
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : 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 $r$. A natural algebraic representation of this problem gives rise to a \emph{determinantal ideal}: the ideal generated by all minors of size $r+1$ of the matrix. We give new complexity bounds for solving this problem using Gröbner bases algorithms under genericity assumptions on the input matrix. In particular, these complexity bounds allow us to identify families of generalized MinRank problems for which the arithmetic complexity of the solving process is polynomial in the number of solutions. We also provide an algorithm to compute a rational parametrization of the variety of a 0-dimensional and radical system of bi-degree $(D,1)$. We show that its complexity can be bounded by using the complexity bounds for the generalized MinRank problem.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-00654094
Contributor : Pierre-Jean Spaenlehauer <>
Submitted on : Tuesday, December 20, 2011 - 6:28:21 PM
Last modification on : Friday, May 24, 2019 - 5:30:29 PM

Links full text

Identifiers

Citation

Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer. On the Complexity of the Generalized MinRank Problem. Journal of Symbolic Computation, Elsevier, 2013, 55, pp.30-58. ⟨10.1016/j.jsc.2013.03.004⟩. ⟨hal-00654094⟩

Share

Metrics

Record views

363