by definition has $\deg_{-{\bm{N}}} {\bm{v}} < 0$.

A solution specification for the problem in \[ex:simpade\] is $$({\bm{\lambda}}, {\bm{\delta}}) = \big( [x^4 + 1,\ x^3 + x]{^\top},\ (-1, -1) \big)  \ .$$ The completion of this is $$A = \begin{bmatrix}
           x^4 + 1 & x^{2} + 1 & 1 & x^{3} + 1 \\
           x^3 + x & x  & x^{3} + x & x^4+x^3 + x
         \end{bmatrix}$$ One can verify that $A$ is $(-{\bm{N}})$-row reduced.

We present two algorithms for solving \[prob:sim\_pade\_basis\], both with complexity $O\big(n^{\omega-1}\, {{\mathsf{M}}}(d)\,(\log d)\,(\log
d/n)^2\big)$, where $d = \max_i \deg g_i$ and ${{\mathsf{M}}}(d)$ is the cost of multiplying two polynomials of degree $d$, see \[ssec:cost\]. They both depend crucially on recent developments that allow computing minimal approximant bases of non-square matrices faster than for the square case [@zhou_efficient_2012; @jeannerod_computation_2016]. We remark that from the solution basis, one can also compute the expanded form of one or a few of the solutions in the same complexity, for instance if a single, expanded solution to the simultaneous [Padé]{}problem is needed.

Our first algorithm in \[sec:dual\] assumes $g_i = x^d$ for all $i$ and some $d \in {\mathbb Z\xspace}_{\geq 0}$. It utilises a well-known duality between Simultaneous [Padé]{}approximations and 