basis $G$ for an $A$ of column dimension $m$ has $\det G = x^D$ for some $D \in {\mathbb Z\xspace}_{\geq 0}$ with $D \leq md$.

Many problems of ${{\mathsf{K}}}[x]$ matrices or approximations reduce to the computation of (shifted) minimal approximant bases, see e.g. [@beckermann_uniform_1994; @giorgi_complexity_2003], often resulting in the best known asymptotic complexities for these problems.

Direct solving of Simultaneous [Padé]{}approximations {#sec:direct_solve}
-----------------------------------------------------

Let $({\bm{S}}, {\bm{g}}, {\bm{N}})$ be an instance of \[prob:sim\_pade\_basis\] of size $n$. We recall some known approaches for computing a solution specification using row reduction and minimal approximant basis computation.

### Via reduced basis {#sec:direct_reduced_basis}

Using the predictable degree property it is easy to show that if $R \in {{\mathsf{K}}}[x]^{(n+1)
\times (n+1)}$ is an $(-{\bm{N}})$-reduced basis of $$A = 
 \left [ \begin{array}{c|c} 
  1 & {\bm{S}} \\\hline
 & {  \ifx\null\null  \Gamma_{{\bm{g}}}  \else  \Gamma_{{\bm{g}}_{\null}}  \fi}\end{array} \right]
       \in {{\mathsf{K}}}[x]^{(n+1) \times (n+1)},$$ then the sub-matrix of $R$ comprised of the rows with negative $(-{\bm{N}})$-degree form a solution basis. A solution specification $({\bm{\lambda}}, {\bm{\delta}})$ is then a subvector ${\bm{\lambda}}$ of the first column of $R$, with ${\bm{\delta}}$ the corresponding subtuple ${\bm{\delta}}$ of ${{\textnormal{rowdeg}}}_{(- {\bm{N}})} R$.

Mulders and Storjohann [@mulders_lattice_2003] gave an iterative algorithm for performing row reduction by successive cancellation; it is 