Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix

Abstract

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\stackrel{~}{}(r^{\ddot{I}‰-2}n(m+D))$ operations in $\mathbb{K}$. Here, $D$ is the sum of row degrees of $\mathbf{F}$, $\ddot{I}‰$ is the exponent of matrix multiplication, and $O\stackrel{~}{}(\cdot )$ hides logarithmic factors.

10 pages, 2 algorithms, 1 figure