the $2 \times 2$ matrix $A$: each iteration corresponds to a reduced basis for a range of possible shifts [@sugiyama_further_1976; @justesen_complexity_1976; @gustavson_fast_1979]. The complexity of this is $O({{\mathsf{M}}}(\deg g_1) \log \deg g_1)$.

### Via minimal approximant basis

First consider the special case when all $g_i = x^d$ for the same $d$. An approximant ${\bm{v}} = (\lambda, \phi_1, \ldots, \phi_n)$ of order $d$ of $$\begin{aligned}
   A &=  \left [ \begin{array}{c}
 - {\bm{S}} \\
 I
            \end{array} \right ]
       \in {{\mathsf{K}}}[x]^{(n+1) \times n}\end{aligned}$$ clearly satisfies $\lambda S_i \equiv \phi_i \mod x^d$ for $i =
1,\ldots,n$; conversely, any such vector ${\bm{v}}$ satisfying these congruences must be an approximant of $A$ of order $d$. So the negative part of a $(-{\bm{N}})$-minimal approximant basis of $A$ of order $d$ is a solution basis.

In the general case we can reduce to a minimal approximant bases computation as shown by \[alg:simpadedirect\]. Correctness of the algorithm follows from the following result.

\[thm:simpadedirect\] Corresponding to an instance $({\bm{S}}, {\bm{g}}, {\bm{N}})$ of \[prob:sim\_pade\_basis\] of size $n$, define a shift ${\bm{h}}$ and order $d$:

-   ${\bm{h}} := -({\bm{N}} \mid N_0 -1, \ldots, N_0-1) \in {\mathbb Z\xspace}^{2n+1}$

-   $d := N_0 + \max_i \deg g_i -1$

If $G$ is the negative part 