论文标题
通过希格曼线性化基质多项式分解
Matrix Polynomial Factorization via Higman Linearization
论文作者
论文摘要
在继续进行非交通性多项式分解的最新工作时，我们考虑了多项式矩阵的分解问题，并显示了以下结果。 （1）作为输入A的全等级$ d \ times d $矩阵$ m $，其条目的条目$ m_ {ij} $是免费的非共同戒指$ \ mathbb {f} _q \ langle x_1，x_2，x_2，x_n \ ldots，x_n \ rangle $} $ rangle x_1，n $ m_}算术公式最多$ s $，我们给出一种随机算法，该算法在$ d，s，s，n $和$ \ \ \ \ \ \ \ \ \ \ log_2q $中运行，该算法计算$ m $作为矩阵产品$ m = m_1m_1m_2 \ cdots m_r $，每个$ d $ d $ dist $ m mm_i is ired profe tirred in Irred; mim_i is ird Is ird in Ird Is red in Ird Is ired tirred（in Is ired in Irred）每个$ m_i $的条目是$ \ mathbb {f} _q \ langle x_1，x_2，\ ldots，x_n \ rangle $中的多项式。我们还获得了在$ poly（d，n，s，q）$中运行的问题的确定性算法。 （2）一种特殊情况是矩阵的有效分解，其条目是$ \ mathbb {f} [x] $中的单变量多项式。当$ \ mathbb {f} $是有限字段时，上述结果适用。当$ \ mathbb {f} $是理性的字段时，我们会为问题获得确定性的多项式时间算法。
In continuation to our recent work on noncommutative polynomial factorization, we consider the factorization problem for matrices of polynomials and show the following results. (1) Given as input a full rank $d\times d$ matrix $M$ whose entries $M_{ij}$ are polynomials in the free noncommutative ring $\mathbb{F}_q\langle x_1,x_2,\ldots,x_n \rangle$, where each $M_{ij}$ is given by a noncommutative arithmetic formula of size at most $s$, we give a randomized algorithm that runs in time polynomial in $d,s, n$ and $\log_2q$ that computes a factorization of $M$ as a matrix product $M=M_1M_2\cdots M_r$, where each $d\times d$ matrix factor $M_i$ is irreducible (in a well-defined sense) and the entries of each $M_i$ are polynomials in $\mathbb{F}_q \langle x_1,x_2,\ldots,x_n \rangle$ that are output as algebraic branching programs. We also obtain a deterministic algorithm for the problem that runs in $poly(d,n,s,q)$. (2)A special case is the efficient factorization of matrices whose entries are univariate polynomials in $\mathbb{F}[x]$. When $\mathbb{F}$ is a finite field the above result applies. When $\mathbb{F}$ is the field of rationals we obtain a deterministic polynomial-time algorithm for the problem.
