Improved algorithms speed up key polynomial computations and reconstructions
Refined complexity bounds for rational reconstruction and XGCD through Padé approximants and Cauchy interpolants
Symbolic Computation
Summary
Some important problems in working with polynomials involve finding common divisors or reconstructing fractions efficiently. The authors show new ways to solve these problems by connecting them to methods of approximation and interpolation using special polynomials. They develop faster algorithms with clear performance guarantees, including clever tricks that reduce complex calculations to simpler ones involving selected points. Surprisingly, these techniques work even for classical methods that seemed different before. This results in the fastest known approaches for the problems studied.
What this means in practice
- •For computer algebra system developers: Optimize polynomial gcd and rational reconstruction computations to improve symbolic algebra software performance.
- •For error-correcting code engineers: Enhance decoding algorithms for linearly recurrent sequences by adapting faster Berlekamp-Massey-like computations.
Authors
Vincent Neiger, Mohab Safey El Din, Kevin Tran
Abstract
When computing with univariate polynomials, two fundamental and related problems are the XGCD and rational reconstruction, classically solved in quasi-linear complexity using the half-gcd algorithm. These problems have various applications in algebraic computations and bear strong connections to linearly recurrent sequences, structured matrices, and continued fractions. This article first gives a collection of algorithmic reductions, showing that rational reconstruction and XGCD can be solved via the computation of bases of relations modulo a freely-chosen polynomial $M(x)$. In particular, one recovers the folklore idea that bases of Padé approximants (i.e., $M(x) = x^d$) can be used to perform quasi-linear rational reconstruction or XGCD, extending to fast algorithms the well-known link between the Berlekamp-Massey algorithm and the extended Euclidean algorithm. One highlight of these reductions is that, instead of approximants, one may rely on Cauchy interpolants (i.e., $M(x)$ vanishes at chosen points). In a second part, this article describes divide-and-conquer algorithms for approximants and interpolants along with complexity analyses showing an explicit leading constant in front of the dominant term. For interpolants, the best leading constant is obtained through a variant that stores polynomials represented by evaluations, and exploits fast extrapolation in order to avoid repeated conversions to the monomial basis; this requires special points, in geometric or arithmetic progression, or FFT points when the base field allows them. Combining the analyses with the reductions leads to the best complexity bounds we are aware of for rational reconstruction and XGCD. Perhaps surprisingly, even Padé approximants or Berlekamp-Massey-like computations, which intrinsically involve $M(x) = x^d$, are accelerated by reducing them to Cauchy interpolation at well-chosen points.