Deterministic Polynomial Time Algorithms for Matrix Completion Problems

Details Deterministic Polynomial Time Algorithms for Matrix Completion Problems Deterministic Polynomial Time Algorithms for Matrix Completion Problems

2009-07-04

arxiv.org/abs/0907.0774v2

Computer Science

Data Structures and Algorithms

14 pages, preliminary

Scientific paper

We present new deterministic algorithms for several cases of the maximum rank matrix completion problem (for short matrix completion), i.e. the problem of assigning values to the variables in a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to the fundamental problems in computational complexity with numerous important algorithmic applications, among others, in computing dynamic transitive closures or multicast network codings (Harvey et al SODA 2005, Harvey et al SODA 2006). We design efficient deterministic algorithms for common generalizations of the results of Lovasz and Geelen on this problem by allowing linear functions in the entries of the input matrix such that the submatrices corresponding to each variable have rank one. We present also a deterministic polynomial time algorithm for finding the minimal number of generators of a given module structure given by matrices. We establish further several hardness results related to matrix algebras and modules. As a result we connect the classical problem of polynomial identity testing with checking surjectivity (or injectivity) between two given modules. One of the elements of our algorithm is a construction of a greedy algorithm for finding a maximum rank element in the more general setting of the problem. The proof methods used in this paper could be also of independent interest.

Affiliated with

Also associated with

No associations

Rating

Deterministic Polynomial Time Algorithms for Matrix Completion Problems 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 Deterministic Polynomial Time Algorithms for Matrix Completion Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic Polynomial Time Algorithms for Matrix Completion Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-530392