论文标题
通过CAT（0）空格的离散凸优化计算NC级
Computing the nc-rank via discrete convex optimization on CAT(0) spaces
论文作者
论文摘要
在本文中，我们介绍了线性符号矩阵\ [a = a = a_1 x_1 + a_2 x_2 + cdots + a_m x_m，\ \]，每个$ a_i $都是$ n \ times n $ n $ n $， $（i = 1,2，\ ldots，m）$是非交换变量。对于这个问题，Garg，Gurvits，Oliveira和Wigderson给出了多项式时间算法，以$ \ MATHBB {K} = \ Mathbb {Q} $，以及Ivanyos，Qiao和Subrahmanyam，以及subrahmanyam，用于任意字段$ \ MATHBB $ \ MATHBB。我们提出了一种在任意字段$ \ mathbb {k} $上工作的多项式时间算法。我们的算法基于在模块化晶格上的suppodular优化和对CAT（0）空间的凸优化的组合。
In this paper, we address the noncommutative rank (nc-rank) computation of a linear symbolic matrix \[ A = A_1 x_1 + A_2 x_2 + \cdots + A_m x_m, \] where each $A_i$ is an $n \times n$ matrix over a field $\mathbb{K}$, and $x_i$ $(i=1,2,\ldots,m)$ are noncommutative variables. For this problem, polynomial time algorithms were given by Garg, Gurvits, Oliveira, and Wigderson for $\mathbb{K} = \mathbb{Q}$, and by Ivanyos, Qiao, and Subrahmanyam for an arbitrary field $\mathbb{K}$. We present a significantly different polynomial time algorithm that works on an arbitrary field $\mathbb{K}$. Our algorithm is based on a combination of submodular optimization on modular lattices and convex optimization on CAT(0) spaces.
