论文标题
多项式矩阵的等级轮廓的等级敏感计算
Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix
论文作者
论文摘要
考虑一个矩阵$ \ mathbf {f} \ in \ mathbb {k} [x]^{m \ times n} $在字段上$ \ mathbb {k} $上的单变量多项式。我们研究计算$ \ Mathbf {f} $的列秩轮廓的问题。为此，我们首先给出了一种算法，该算法改善了周，拉巴恩和斯托霍恩的最小内核基础算法（会议记录ISSAC 2012）。然后，我们提供了第二种算法，该算法以$ \ o \ tilde {〜}（r^{ω-2} n（m+d））$ operations $ \ tillbb {k} $计算$ \ mathbf {f} $的列级级别配置文件。在这里，$ d $是$ \ mathbf {f} $，$ω$的行的总和，是矩阵乘法的指数，$ o \ tilde {〜}（\ cdot）$ hid bay boolgarithmic因素。
Consider a matrix $\mathbf{F} \in \mathbb{K}[x]^{m \times n}$ of univariate polynomials over a field $\mathbb{K}$. We study the problem of computing the column rank profile of $\mathbf{F}$. To this end we first give an algorithm which improves the minimal kernel basis algorithm of Zhou, Labahn, and Storjohann (Proceedings ISSAC 2012). We then provide a second algorithm which computes the column rank profile of $\mathbf{F}$ with a rank-sensitive complexity of $O\tilde{~}(r^{ω-2} n (m+D))$ operations in $\mathbb{K}$. Here, $D$ is the sum of row degrees of $\mathbf{F}$, $ω$ is the exponent of matrix multiplication, and $O\tilde{~}(\cdot)$ hides logarithmic factors.
