{\leftarrow}{{\ensuremath{\mathsf{NegMinBasis}}\xspace}}(d, H, {\bm{h}})$ ${\textbf{return }}({\bm{\lambda}}, {\bm{\delta}})$

[$\mathsf{DirectSimPade}$]{} can be performed in time ${O^{\scriptscriptstyle \sim}\!}(n^{\omega} \deg H) = {O^{\scriptscriptstyle \sim}\!}(n^\omega \max_i \deg g_i)$ using the minimal approximant basis algorithm by Jeannerod, et al. [@jeannerod_computation_2016], see \[sec:subroutines\].

A closely related alternative to [$\mathsf{DirectSimPade}$]{} is the recent algorithm by Neiger [@neiger_fast_2016] for computing solutions to modular equations with general moduli $g_i$. This would give the complexity ${O^{\scriptscriptstyle \sim}\!}(n^{\omega-1} \sum_i \deg g_i) \subset {O^{\scriptscriptstyle \sim}\!}(n^\omega \max_i \deg g_i)$.

All of the above solutions ignore the sparse, simple structure of the input matrices, which is why they do not obtain the improved complexity that we do here.

Computational tools {#sec:subroutines}
===================

The main computational tool we will use is the following very recent result from Jeannerod, Neiger, Schost and Villard [@jeannerod_computation_2016] on minimal approximant basis computation.

\[thm:orderbasis\] There exists an algorithm ${{\ensuremath{\mathsf{PopovBasis}}\xspace}}(d,A, {\bm{s}})$ where the input is an order $d \in {\mathbb Z\xspace}_+$, a polynomial matrix $A \in {{\mathsf{K}}}[x]^{n
  \times m}$ of degree at most $d$, and shift ${\bm{s}} \in {\mathbb Z\xspace}^n$, and which returns $(F, {\bm{\delta}})$, where $F$ is an ${\bm{s}}$-minimal approximant basis of $A$ of order $d$, $F$ is in ${\bm{s}}$-Popov form, and ${\bm{\delta}} = {{\textnormal{rowdeg}}}_{{\bm{s}}} F$. [[$\mathsf{PopovBasis}$]{}]{}has complexity $O(n^{\omega-1}\, {{\mathsf{M}}}(\sigma)\, (\log \sigma) 