A fast algorithm for reversion of power series

Johansson, Fredrik

doi:10.1090/S0025-5718-2014-02857-3

A fast algorithm for reversion of power series
HTML articles powered by AMS MathViewer

by Fredrik Johansson PDF

Math. Comp. 84 (2015), 475-484 Request permission

Abstract:

We give an algorithm for reversion of formal power series, based on an efficient way to implement the Lagrange inversion formula. Our algorithm requires $O(n^{1/2}(M(n) + M\!M(n^{1/2})))$ operations where $M(n)$ and $M\!M(n)$ are the costs of polynomial and matrix multiplication, respectively. This matches the asymptotic complexity of an algorithm of Brent and Kung, but we achieve a constant factor speedup whose magnitude depends on the polynomial and matrix multiplication algorithms used. Benchmarks confirm that the algorithm performs well in practice.

References

Daniel J. Bernstein, Composing power series over a finite ring in essentially linear time, J. Symbolic Comput. 26 (1998), no. 3, 339–341. MR 1633872, DOI 10.1006/jsco.1998.0216
Daniel J. Bernstein, Removing redundancy in high-precision Newton iteration, http://cr.yp.to/papers.html\#fastnewton, 2004.
Daniel J. Bernstein, Fast multiplication and its applications, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 325–384. MR 2467550
Alin Bostan, Bruno Salvy, and Éric Schost, Power series composition and change of basis, ISSAC 2008, ACM, New York, 2008, pp. 269–276. MR 2513515, DOI 10.1145/1390768.1390806
R. P. Brent and J. T. Kung, Fast algorithms for manipulating formal power series, Journal of the ACM, 25 (1978), no. 4, 581–595.
The MPIR development team, MPIR: Multiple Precision Integers and Rationals, http://www.mpir.org.
G. Hanrot and P. Zimmermann, Newton iteration revisited, http://www.loria.fr/~zimmerma/papers/fastnewton.ps.gz, 2004.
W. B. Hart, Fast Library for Number Theory: An Introduction, Proceedings of the Third international congress conference on Mathematical software (Berlin, Heidelberg), ICMS’10, Springer-Verlag, 2010, http://flintlib.org, pp. 88–91.
David Harvey, Faster algorithms for the square root and reciprocal of power series, Math. Comp. 80 (2011), no. 273, 387–394. MR 2728985, DOI 10.1090/S0025-5718-2010-02392-0
J. Hopcroft and J. Musinski, Duality applied to the complexity of matrix multiplication and other bilinear forms, SIAM J. Comput. 2 (1973), 159–173. MR 471439, DOI 10.1137/0202013
Xiaohan Huang and Victor Y. Pan, Fast rectangular matrix multiplication and applications, J. Complexity 14 (1998), no. 2, 257–299. MR 1629113, DOI 10.1006/jcom.1998.0476
Kiran S. Kedlaya and Christopher Umans, Fast polynomial factorization and modular composition, SIAM J. Comput. 40 (2011), no. 6, 1767–1802. MR 2863194, DOI 10.1137/08073408X
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
Robert L. Probert, On the additive complexity of matrix multiplication, SIAM J. Comput. 5 (1976), no. 2, 187–203. MR 408311, DOI 10.1137/0205016
Peter Ritzmann, A fast numerical algorithm for the composition of power series with complex coefficients, Theoret. Comput. Sci. 44 (1986), no. 1, 1–16. MR 858688, DOI 10.1016/0304-3975(86)90107-6
A. J. Stothers, On the complexity of matrix multiplication, Ph.D. thesis, University of Edinburgh, 2010.
Joris van der Hoeven, Relax, but don’t be too lazy, J. Symbolic Comput. 34 (2002), no. 6, 479–542. MR 1943041, DOI 10.1006/jsco.2002.0562
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
V. Vassilevska Williams, Breaking the Coppersmith-Winograd barrier, http://cs.berkeley.edu/~virgi/matrixmult.pdf, 2011.