Hermite [Padé]{}approximations, see e.g. [@beckermann_uniform_1992]. The Hermite [Padé]{}problem is immediately solvable by fast minimal approximant basis computation. A remaining step is to efficiently compute a single row of the adjoint of a matrix in Popov form, and this is done by combining partial linearisation [@GuptaSarkarStorjohannValeriote11] and high-order lifting [@storjohann_high-order_2003].

Our second algorithm in \[sec:intersect\] supports arbitrary $g_i$. The algorithm first solves $n$ single-sequence [Padé]{}approximations, each of $S_1,\ldots,S_n$. The solution bases for two problem instances can be combined by computing the intersection of their row spaces; this is handled by a minimal approximant basis computation. A solution basis of the full Simultaneous [Padé]{}problem is then obtained by structuring intersections along a binary tree.

Before we describe our algorithms, we give some preliminary notation and definitions in \[sec:preliminaries\], and in \[sec:subroutines\] we describe some of the computational tools that we employ.

Both our algorithms have been implemented in Sage v. 7.0 [@stein_sagemath_????] (though asymptotically slower alternatives to the computational tools are used). The source code can be downloaded from <http://jsrn.dk/code-for-articles>.

Cost model {#ssec:cost}
----------

We count basic arithmetic operations in ${{\mathsf{K}}}$ on an algebraic RAM. We will state complexity results in terms of an exponent $\omega$ for matrix multiplication, and a function 