Algorithms for simultaneous Hermite-Padé approximations

DOI10.1016/J.JSC.2019.07.026MaRDI QIDQ2200312zbMATH OpenOpenAlexWikidataFDO

Authors Johan Rosenkilde, Arne Storjohann

Publication date 19 September 2020

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2019.07.026

fast algorithms minimal polynomial bases Padé approximation software structured linear systems

Approximation by rational functions (41A20) Padé approximation (41A21) Algorithms for approximation of functions (65D15)

Review text

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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Algorithms for simultaneous Hermite-Padé approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200312)