Deterministic Polynomial Time Algorithms for Matrix Completion Problems
Deterministic Polynomial Time Algorithms for Matrix Completion Problems
复制标题
矩阵补全问题的确定性多项式时间算法
DOI：
10.1112/s1461157013000296
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Nitin Saxena
中科院分区：
文献类型：
--
作者：
G. Ivanyos;Marek Karpinski;Nitin Saxena
我们提出了一些新的确定性算法来解决最大秩矩阵补全问题（简称矩阵补全），即给给定符号矩阵中的变量赋值以使结果矩阵秩最大化的问题。矩阵补全是计算复杂性的基本问题之一。它有许多重要的算法应用，其中包括计算动态传递闭包或多播网络编码[N]。J. A. Harvey， D. R. Karger，和K. Murota，第16届ACM-SIAM离散算法研讨会论文集，2005年，第489-498页；N. J. A. Harvey， D. R. Karger， S. Yekhanin，第十七届ACM-SIAM离散算法研讨会论文集，2006,pp. 1103-1111。我们设计了有效的确定性算法，用于Lovasz和Geelen在这个问题上的结果的一般推广，通过允许输入矩阵的条目中的线性多项式，使得每个变量对应的子矩阵具有秩1。我们的方法是代数的，与Lovasz和Geelen的方法有很大的不同。我们在线性变换的线性空间的更一般的集合中观察矩阵补全问题，并使用贪心方法在那里找到最大秩元素。矩阵代数和模在算法中起着至关重要的作用。我们给出了与矩阵代数自然相关的矩阵补全的特殊实例的（硬度）结果；也就是说，与计算模块的同构（有已知的确定性多项式时间算法）相比，在两个给定模块之间寻找满射或单射同态与一般矩阵补全问题一样困难。寻找最大维度循环子模块（即，由单个元素生成）的难度相同。对于“双重”任务，即寻找给定模块的最小生成器数量，我们提出了一个确定性多项式时间算法。本文开发的证明方法适用于相当一般的模块，也可以是独立的兴趣。
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 to maximize the resulting matrix rank. Matrix completion is one of the fundamental problems in computational complexity. It has numerous important algorithmic applications, among others, in computing dynamic transitive closures or multicast network codings [N. J. A. Harvey, D. R. Karger, and K. Murota, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 489-498; N. J. A. Harvey, D. R. Karger, and S. Yekhanin, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 1103-1111]. We design efficient deterministic algorithms for common generalizations of the results of Lovasz and Geelen on this problem by allowing linear polynomials in the entries of the input matrix such that the submatrices corresponding to each variable have rank one. Our methods are algebraic and quite different from those of Lovasz and Geelen. We look at the problem of matrix completion in the more general setting of linear spaces of linear transformations and find a maximum rank element there using a greedy method. Matrix algebras and modules play a crucial role in the algorithm. We show (hardness) results for special instances of matrix completion naturally related to matrix algebras; i.e., in contrast to computing isomorphisms of modules (for which there is a known deterministic polynomial time algorithm), finding a surjective or an injective homomorphism between two given modules is as hard as the general matrix completion problem. The same hardness holds for finding a maximum dimension cyclic submodule (i.e., generated by a single element). For the “dual” task, i.e., finding the minimal number of generators of a given module, we present a deterministic polynomial time algorithm. The proof methods developed in this paper apply to fairly general modules and could also be of independent interest.
用 GRH 换取代数：因式分解多项式和相关结构的算法
DOI：
10.1090/s0025-5718-2011-02505-6
发表时间：
2011
期刊：
ArXiv
影响因子：
--
作者：
G. Ivanyos;M. Karpinski;L. Rónyai;N. Saxena
通讯作者：
N. Saxena