\, (\log \sigma /n)^2)$ operations in ${{\mathsf{K}}}$, where $\sigma = md$.

Our next result says that we can quickly compute the first row of ${{\textnormal{adj}}}(F)$ if $F$ is a minimal approximant basis in Popov form. In particular, since $F$ is an approximant basis $\det F = x^D$ for some $D \leq \sigma$, where $\sigma = md$ from \[thm:orderbasis\].

\[thm:fastsolver\] Let $F \in {{\mathsf{K}}}[x]^{n \times n}$ be in Popov form and with $\det F = x^D$ for some $D \in {\mathbb Z\xspace}_{\geq 0}$. Then the first row of ${{\textnormal{adj}}}(F)$ can be computed in $O(n^{\omega-1}\, {{\mathsf{M}}}(D)\, (\log D) \, (\log D/n))$ operations in ${{\mathsf{K}}}$.

Because $F$ is in ${\bm{s}}$-Popov form, $D$ is the sum of the column degrees of $F$. We consider two cases: $D \geq n$ and $D < n$.

First suppose $D
\geq n$. Partial linearisation [@GuptaSarkarStorjohannValeriote11 Corollary 2] can produce from $F$, with no operations in ${{\mathsf{K}}}$, a new matrix $G \in {{\mathsf{K}}}[x]^{\bar n \times \bar n}$ with dimension $\bar{n} < 2n$, $\deg G \leq \lceil D/n\rceil$, $\det G = \det F$, and such that $F^{{-1}}$ is equal to the principal $n \times n$ sub-matrix of $G^{{-1}}$. Let ${\bm{v}} \in {{\mathsf{K}}}[x]^{1 \times \bar{n}}$ be the first row of $x^DI_{\bar{n}}$. 