Algorithms for Simultaneous Padé Approximations

Abstract

We describe how to solve simultaneous Padé approximations over a power series ring $K[[x]]$ for a field $K$ using $O(n^{\omega -1}d)$ operations in $K$, where $d$ is the sought precision and $n$ is the number of power series to approximate. We develop two algorithms using different approaches. Both algorithms return a reduced sub-bases that generates the complete set of solutions to the input approximations problem that satisfy the given degree constraints. Our results are made possible by recent breakthroughs in fast computations of minimal approximant bases and Hermite Padé approximations.

ISSAC 2016

References in corpus (2)

• Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts
• Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations

Cited by in corpus (6)

• Computing Canonical Bases of Modules of Univariate Relations
• Power Decoding Reed--Solomon Codes Up to the Johnson Radius
• Improved Power Decoding of One-Point Hermitian Codes
• Enhancing simultaneous rational function recovery: adaptive error correction capability and new bounds for applications
• Polynomial Linear System Solving with Random Errors: new bounds and early termination technique
• Decoding of Interleaved Reed-Solomon Codes Using Improved Power Decoding