Geodesic
Fast algorithms for elementary operations on complex power series
Diskretnaya Matematika, Tome 22 (2010) no. 1, pp. 17-49.

Voir la notice de l'article provenant de la source Math-Net.Ru

It is shown that the inversion of a complex-valued power series can be realised asymptotically with complexity of 5/4 multiplications (if we compare the upper bounds). It is shown that the calculation of the square root requires asymptotically also no more than 5/4 multiplications, the computation of an exponential has the complexity equal to 13/6 multiplications, and raising to an arbitrary power requires 41/12 multiplications. 
@article{DM_2010_22_1_a2,
     author = {I. S. Sergeev},
     title = {Fast algorithms for elementary operations on complex power series},
     journal = {Diskretnaya Matematika},
     pages = {17--49},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2010_22_1_a2/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - Fast algorithms for elementary operations on complex power series
JO  - Diskretnaya Matematika
PY  - 2010
SP  - 17
EP  - 49
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2010_22_1_a2/
LA  - ru
ID  - DM_2010_22_1_a2
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T Fast algorithms for elementary operations on complex power series
%J Diskretnaya Matematika
%D 2010
%P 17-49
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2010_22_1_a2/
%G ru
%F DM_2010_22_1_a2
I. S. Sergeev. Fast algorithms for elementary operations on complex power series. Diskretnaya Matematika, Tome 22 (2010) no. 1, pp. 17-49. http://geodesic.mathdoc.fr/item/DM_2010_22_1_a2/

[1] Cook S., On the minimum computation time of functions, Doctoral Thesis, Harvard Univ., Cambridge, Mass., 1966

[2] Brent R. P., “Multiple-precision zero-finding methods and the complexity of elementary function evaluation”, Analytic Computational Complexity, ed. Traub J. F., Academic Press, New York, 1975, 151–176 | MR

[3] von zur Gathen J., Gerhard J., Modern computer algebra, Cambridge Univ. Press, Cambridge, 1999 | MR

[4] Bernstein D. J., “Fast multiplication and its applications”, Algorithmic Number Theory. Lattices, Number Fields, Curves and Cryptography, Mathematical Sciences Research Institute Publications, 44, eds. Buhler J. P. et al., Cambridge, 2008, 325–384 | MR | Zbl

[5] Sieveking M., “An algorithm for division of power series”, Computing, 10 (1972), 153–156 | DOI | MR | Zbl

[6] Brent R. P., Kung H. T., “Fast algorithms for manipulating formal power series”, J. Assoc. Comput. Mach., 25:4 (1978), 581–595 | MR | Zbl

[7] Aho A. V., Hopcroft J. E., Ullman J. D., The design and analysis of computer algorithms, Addison–Wesley, Reading, Mass., 1976 | MR

[8] Schönhage A., “Variations on computing reciprocals of power series”, Inf. Process. Lett., 74 (2000), 41–46 | DOI | MR | Zbl

[9] Bernstein D. J., Removing redundancy in high-precision newton iteration, ne opublikovano http://cr.yp.to/fastnewton.html

[10] van der Hoeven J., Newton's Method and FFT Trading, Technical Report 2006–17, Univ. Paris-Sud, Orsay, 2006

[11] Karatsuba A. A., Ofman Yu. P., “Umnozhenie mnogoznachnykh chisel na avtomatakh”, Dokl. AN SSSR, 145:2 (1962), 293–294

[12] Hanrot G., Quercia M., Zimmermann P., “The middle product algorithm. I: Speeding up the division and square root of power series”, Appl. Algebra Eng. Commun. Comput., 14 (2004), 415–438 | DOI | MR | Zbl

[13] Sergeev I. S., “Bystrye algoritmy dlya elementarnykh operatsii so stepennymi ryadami”, Materialy IX Mezhdunarodnogo seminara “Diskretnaya matematika i ee prilozheniya”, Izd-vo mekh.-mat. f-ta MGU, Moskva, 2007, 123–126

[14] Bernstein D. J., “The tangent FFT”, Lecture Notes Computer Sci., 4851, 2007, 291–300 | Zbl

[15] Schönhage A., “Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients”, Lecture Notes Computer Sci., 144, 1982, 3–15 | MR | Zbl

[16] van der Hoeven J., Notes on the truncated fourier transform, Technical Report 2005-5, Univ. Paris-Sud, Orsay, 2005

[17] Bürgisser P., Clausen M., Shokrollahi M. A., Algebraic complexity theory, Springer, Berlin, 1997 | MR | Zbl

[18] Knuth D. E., The art of computer programming: seminumerical algorithms, v. 2, Addison–Wesley Longman, Boston, 1998 | MR | Zbl

[19] Bostan A., Chyzak F., Ollivier F., Salvy B., Schost É., Sedoglavic A., “Fast computation of power series solutions of systems of differential equations”, Proc. Symposium on Discrete Algorithms, SIAM, Philadelphia, 2007, 1012–1021 | MR

[20] Schulz G., “Iterative Berechnung der reziproken Matrix”, Z. Angewandte Math. Mech., 13 (1933), 57–59 | DOI | Zbl

[21] Cooley J. W., Tukey J. W., “An algorithm for the machine calculation of complex Fourier series”, Math. Comput., 19 (1965), 297–301 | DOI | MR | Zbl

[22] van der Hoeven J., “New algorithms for relaxed multiplication”, J. Symbolic Comput., 42 (2007), 792–802 | DOI | MR | Zbl

[23] Karp A. H., Markstein P., “High-precision division and square root”, ACM Trans. Math. Softw., 23 (1997), 561–589 | DOI | MR | Zbl

[24] Bostan A., Schost É., “A simple and fast algorithm for computing exponentials of power series”, Inf. Process. Lett., 109 (2009), 754–756 | DOI | MR

[25] Strassen V., “Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten”, Numer. Math., 20 (1973), 238–251 | DOI | MR | Zbl