Complexity of solving a linear equation system over $k[x]$

Question

Let $k$ be a field and let $A \in k[x]^{m \times n}$ be a polynomial matrix whose entry with highest degree has degree $d$. Let $b \in k[x]^m$. What is known about the complexity of computing a solution $v \in k[x]^n$ with $Av=b$ under the assumption that such a solution exists?

Is it $O^\sim(\max(m,n)^\omega d)$ where $\omega$ is the matrix multiplication constant (i.e. the multiplication of two $n \times n$ matrices over $k$ uses $O(n^\omega)$ steps in $k$)?

Any reference is appreciated!

Answer 1

• The problem for $b=0$ is answered in the paper

  Computing Minimal Nullspace Bases by Zhou, Labahn and Storjohann

  and it also computes a minimal basis of the kernel of $A$ and has complexity $O^\sim(n^\omega \lceil md/n \rceil)$.

• Assuming that $A$ is square and non-singular, the paper

  Triangular $x$-basis decomposition and derandomization of linear algebra algorithms over $K[x]$ by Storjohann, Sarkar, Gupta and Valeriote

  provides a deterministic algorithm for computing the unique solution $A^{-1}b$ using $O(n^\omega(\log n)^2 M(d) + n B(d))$ operations from the ground field.