# 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.

##### MSC:
 68W30 Symbolic computation and algebraic computation 68W40 Analysis of algorithms 65D20 Computation of special functions and constants, construction of tables
##### Keywords:
middle product; inversion; division; square root; Newton’s method
Full Text: