On the Complexity of the Generalized MinRank Problem
Authors:
- Mohab Safey El DinMDMohab Safey El Din
Preprint
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\"obner 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.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Global optimization of polynomials restricted to a smooth variety using sums of squaresJournal of Symbolic Computation, 2012
- On the geometry of polar varietiesApplicable Algebra in Engineering, Communication and Computing, 2010
- Polynomial evaluation and interpolation on special sets of pointsJournal of Complexity, 2005
- New Technique for Decoding Codes in the Rank Metric and Its Cryptography ApplicationsProblems of Information Transmission, 2002
- From Enumerative Geometry to Solving Systems of Polynomial Equations2002
- Common Tangents to Four Unit Balls in R 3Discrete & Computational Geometry, 2001
- The Computational Complexity of Some Problems of Linear AlgebraJournal of Computer and System Sciences, 1999
- The Magma Algebra System I: The User LanguageJournal of Symbolic Computation, 1997
- Cohen-Macaulay Rings, Invariant Theory, and the Generic Perfection of Determinantal LociAmerican Journal of Mathematics, 1971
- A class of perfect determinantal idealsBulletin of the American Mathematical Society, 1970