
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2009  Copyright 2009 Universität Bonn, Institut für Informatik, Abt. V  
85304 23.06.2009 
Deterministic Polynomial Time Algorithms for Matrix Completion Problems
Gábor Ivanyos, Marek Karpinski and Nitin Saxena [Download PostScript] [Download PDF] 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 [HKM05, HKY06]. We design efficient deterministic algorithms for common generalizations of the results of Lovász 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. 

Last Change:
06/23/09 at 09:52:28
English 
Universität Bonn > Institut für Informatik > Abteilung V 