Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix
| Autor: | Labahn, George, Neiger, Vincent, Vu, Thi Xuan, Zhou, Wei |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1145/3476446.3535495 |
| Popis: | 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^{\omega-2} n (m+D))$ operations in $\mathbb{K}$. Here, $D$ is the sum of row degrees of $\mathbf{F}$, $\omega$ is the exponent of matrix multiplication, and $O\tilde{~}(\cdot)$ hides logarithmic factors. Comment: 10 pages, 2 algorithms, 1 figure |
| Databáze: | arXiv |
| Externí odkaz: |
|