Paper Info
Title
On the complexity of the generalized MinRank problem.
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 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.
Year
DOI
Venue
2013
10.1016/j.jsc.2013.03.004
Journal of Symbolic Computation
Keywords
DocType
Volume
MinRank,Gröbner basis,Determinantal,Bi-homogeneous,Structured algebraic systems
Journal
55
ISSN
Citations 
PageRank 
0747-7171
15
0.72
References 
Authors
13
3
Name
Order
Citations
PageRank
Jean-Charles Faugère1103774.00
Mohab Safey El Din245035.64
Pierre-Jean Spaenlehauer312912.08