low degree. The study of Simultaneous [Padé]{}approximations traces back to Hermite’s proof of the transcendence of $e$ [@hermite_sur_1878]. Solving Simultaneous [Padé]{}approximations has numerous applications, such as in coding theory, e.g. [@feng_generalization_1991; @schmidt_collaborative_2009]; or in distributed, reliable computation [@clement_pernet_high_2014]. Many algorithms have been developed for this problem, see e.g. [@beckermann_uniform_1992; @olesh_vector_2006; @sidorenko_linear_2011; @nielsen_generalised_2013] as well as the references therein. Usually one cares about the regime where $d \gg n$. Obtaining $O(n d^2)$ is classical through successive cancellation, see [@beckermann_uniform_1994] or [@feng_generalization_1991] for a Berlekamp–Massey-type variant. Using fast arithmetic, the previous best was ${O^{\scriptscriptstyle \sim}\!}(n^\omega d)$, where $\omega$ is the exponent for matrix multiplication, see \[ssec:cost\]. That can be done by computing a minimal approximant basis with e.g. [@giorgi_complexity_2003; @GuptaSarkarStorjohannValeriote11]; this approach traces back to [@barel_general_1992; @beckermann_uniform_1992]. Another possibility which achieves the same complexity is fast algorithms for solving structured linear systems, e.g. [@bostan_solving_2008]; see [@chowdhury_faster_2015] for a discussion of this approach.

A common description is to require $\deg \lambda < N_0$ for some degree bound $N_0$, and similarly $\deg {{\textnormal{rem}}}(\lambda S_1,\, x^d) < N_i$ for $i = 1,\ldots,n$. The degree bounds could arise naturally from the application, or could be set such that a solution must exist. A natural generalisation is 