Details:
Title  On the complexity of the generalized MinRank problem  Author(s)  JeanCharles Faugère, Mohab Safey, PierreJean Spaenlehauer  Type  Article in Journal  Abstract  Abstract We study the complexity of solving the 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 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 0dimensional and radical system of bidegree ( D , 1 ) . We show that its complexity can be bounded by using the complexity bounds for the generalized MinRank problem.  Keywords  MinRank, Gröbner basis, Determinantal, Bihomogeneous, Structured algebraic systems  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717113000485 
Language  English  Journal  Journal of Symbolic Computation  Volume  55  Number  0  Pages  30  58  Year  2013  Edition  0  Translation 
No  Refereed 
No 
