Algorithms for simultaneous Hermite-Padé approximations (Q2200312)

Let \(K[x]\) denote the polynomials over a field \(K\), and let \(S\in K[x]^{t\times n}\) and \(g\in K[x]^{1\times n}\) be given, then the simultaneous Hermite-Padé approximation problem is to find polynomial vectors \(\lambda\in K[x]^{1\times t}\) and \(\phi\in K[x]^{1\times n}\) such that \({\lambda} S=\phi\mod g\) when degree \(\gamma=[\lambda~\phi]\le N\in\mathbb{Z}^{1\times (t+n)}_{\ge0}\). Classical simultaneous Padé corresponds to \(t=1\) and classical Hermite-Padé to \(n=1\) with all \(g_i(x)=x^d\) for some fixed \(d\). These special cases were considered in many papers and books. Here the authors generalize their previous paper on simultaneous Padé [\textit{J. Rosenkilde né Nielsen} and \textit{A. Storjohann}, in: Proceedings of the 41st international symposium on symbolic and algebraic computation, ISSAC 2016, Waterloo, Canada, July 20--22, 2016. New York, NY: Association for Computing Machinery (ACM). 405--412 (2016; Zbl 1365.65035)] to the general case, but concentrate on \(t<n\). They give two efficient algorithms that generates a \((-N)\)-row reduced matrix \(A\in K[x]^{*\times (t+n)}\) whose rows form a minimal basis for the space of all possible solutions \([\lambda~\phi]\) with degrees bounded by \(N\). The first algorithm is based on the duality between simultaneous Padé (a \(t\times n\) problem with \(t<n\)) and Hermite-Padé (an \(n\times t\) problem) which allows to choose the most efficient method. The second algorithm essentially solves the problem by divide and conquer, combining solutions of smaller \(t\times t\) problems. The algorithms are fast in the sense that, neglecting log-terms, the complexity is \(O(n^{\omega-1}td)\) where \(O(n^\omega)\) is the cost to multiply two matrices from \(K[x]^{n\times n}\), and \(d\) refers to the approximation order. The algorithms are formally described and a website is available to download the sage software.