zbMATH — the first resource for mathematics

The middle product algorithm. I: Speeding up the division and square root of power series. (English) Zbl 1064.68094
Summary: We present new algorithms for the inverse, division, and square root of power series. The key trick is a new algorithm – MiddleProduct – computing the \(n\) middle coefficients of a \((2n- 1)\times n\) full product in the same number of multiplications as a full \(n\times n\) product. This improves previous work of Brent, Mulders, Karp and Markstein, Burnikel and Ziegler. These results apply both to series and polynomials.

68W30 Symbolic computation and algebraic computation
68W40 Analysis of algorithms
65D20 Computation of special functions and constants, construction of tables
Full Text: DOI