Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A fast algorithm for reversion of power series


Author: Fredrik Johansson
Journal: Math. Comp. 84 (2015), 475-484
MSC (2010): Primary 68W30
DOI: https://doi.org/10.1090/S0025-5718-2014-02857-3
Published electronically: May 6, 2014
MathSciNet review: 3266971
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1006/jsco.1998.0216
  • [2] Daniel J. Bernstein, Removing redundancy in high-precision Newton iteration, http://cr.yp.to/papers.html#fastnewton, 2004.
  • [3] 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 (2010a:68186)
  • [4] 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 (2010h:68221), https://doi.org/10.1145/1390768.1390806
  • [5] R. P. Brent and J. T. Kung, Fast algorithms for manipulating formal power series, Journal of the ACM, 25 (1978), no. 4, 581-595.
  • [6] The MPIR development team, MPIR: Multiple Precision Integers and Rationals, http://www.mpir.org.
  • [7] G. Hanrot and P. Zimmermann, Newton iteration revisited, http://www.loria.fr/~zimmerma/papers/fastnewton.ps.gz, 2004.
  • [8] 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.
  • [9] David Harvey, Faster algorithms for the square root and reciprocal of power series, Math. Comp. 80 (2011), no. 273, 387-394. MR 2728985 (2011m:68299), https://doi.org/10.1090/S0025-5718-2010-02392-0
  • [10] 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 0471439 (57 #11172)
  • [11] Xiaohan Huang and Victor Y. Pan, Fast rectangular matrix multiplication and applications, J. Complexity 14 (1998), no. 2, 257-299. MR 1629113 (99i:15002), https://doi.org/10.1006/jcom.1998.0476
  • [12] Kiran S. Kedlaya and Christopher Umans, Fast polynomial factorization and modular composition, SIAM J. Comput. 40 (2011), no. 6, 1767-1802. MR 2863194, https://doi.org/10.1137/08073408X
  • [13] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878 (83i:68003)
  • [14] Robert L. Probert, On the additive complexity of matrix multiplication, SIAM J. Comput. 5 (1976), no. 2, 187-203. MR 0408311 (53 #12076)
  • [15] 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 (88d:68043), https://doi.org/10.1016/0304-3975(86)90107-6
  • [16] A. J. Stothers, On the complexity of matrix multiplication, Ph.D. thesis, University of Edinburgh, 2010.
  • [17] Joris van der Hoeven, Relax, but don't be too lazy, J. Symbolic Comput. 34 (2002), no. 6, 479-542. MR 1943041 (2003k:13026), https://doi.org/10.1006/jsco.2002.0562
  • [18] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757 (2004g:68202)
  • [19] V. Vassilevska Williams, Breaking the Coppersmith-Winograd barrier, http://cs.berkeley.edu/~virgi/matrixmult.pdf, 2011.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30

Retrieve articles in all journals with MSC (2010): 68W30


Additional Information

Fredrik Johansson
Affiliation: Research Institute for Symbolic Computation, Johannes Kepler University, 4040 Linz, Austria
Email: fredrik.johansson@risc.jku.at

DOI: https://doi.org/10.1090/S0025-5718-2014-02857-3
Received by editor(s): August 22, 2011
Received by editor(s) in revised form: April 26, 2013
Published electronically: May 6, 2014
Additional Notes: This work was supported by Austrian Science Fund (FWF) grant Y464-N18.
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society