similar to but faster than earlier algorithms [@kailath_linear_1980; @lenstra_factoring_1985]. Generically on input $F \in {{\mathsf{K}}}[x]^{m \times m}$ it has complexity $O(n^3 (\deg F)^2)$. Alekhnovich [@alekhnovich_linear_2005] gave what is essentially a Divide & Conquer variant of Mulders and Storjohann’s algorithm, with complexity ${O^{\scriptscriptstyle \sim}\!}(n^{\omega+1}\deg F)$. Nielsen remarked [@nielsen_generalised_2013] that these algorithms perform fewer iterations when applied to the matrix $A$ above, due to its low *orthogonality defect*: ${\rm OD}(F) = \sum{{\textnormal{rowdeg}}}F - \deg \det F$, resulting in $O(n^2(\deg A)^2)$ respectively ${O^{\scriptscriptstyle \sim}\!}(n^\omega \deg A)$. Nielsen also used the special shape of $A$ to give a variant of the Mulders–Storjohann algorithm that computes coefficients in the working matrix in a lazy manner with a resulting complexity $O(n \,\mathsf{P}(\deg A))$, where $\mathsf P(\deg A) = (\deg A)^2$ when the $g_i$ are all powers of $x$, and $\mathsf P(\deg A) = {{\mathsf{M}}}(\deg A)\deg A$ otherwise.

Giorgi, et al. [@giorgi_complexity_2003] gave a reduction for performing row reduction by computing a minimal approximant basis. For the special matrix $A$, this essentially boils down to the approach described in the following section.

When $n = 1$, the extended Euclidean algorithm on input $S_1$ and $g_1$ can solve the approximation problem by essentially computing the reduced basis of 