×

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
PDF BibTeX XML Cite
Full Text: DOI