On the Complexity of the Generalized MinRank Problem

Details On the Complexity of the Generalized MinRank Problem On the Complexity of the Generalized MinRank Problem

2011-12-19

arxiv.org/abs/1112.4411v1

Computer Science

Symbolic Computation

33 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of the Generalized MinRank Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of the Generalized MinRank Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of the Generalized MinRank Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-213063