×

A fast algorithm for reversion of power series. (English) Zbl 1312.68236

Summary: 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) + MM(n^{1/2})))\) operations where \( M(n)\) and \( MM(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.

MSC:

68W30 Symbolic computation and algebraic computation
30-04 Software, source code, etc. for problems pertaining to functions of a complex variable
68Q25 Analysis of algorithms and problem complexity

Software:

MPIR; FLINT
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bernstein, Daniel J., Composing power series over a finite ring in essentially linear time, J. Symbolic Comput., 26, 3, 339-341 (1998) · Zbl 0934.68129 · doi:10.1006/jsco.1998.0216
[2] [Bernstein2004] Daniel J. Bernstein, Removing redundancy in high-precision Newton iteration, \urlhttp://cr.yp.to/papers.html#fastnewton, 2004.
[3] Bernstein, Daniel J., Fast multiplication and its applications. Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ. 44, 325-384 (2008), Cambridge Univ. Press: Cambridge:Cambridge Univ. Press · Zbl 1208.68239
[4] Bostan, Alin; Salvy, Bruno; Schost, {\'E}ric, Power series composition and change of basis. ISSAC 2008, 269-276 (2008), ACM: New York:ACM · Zbl 1489.68409 · doi:10.1145/1390768.1390806
[5] [BrentKung1978] R. P. Brent and J. T. Kung, Fast algorithms for manipulating formal power series, Journal of the ACM, 25 (1978), no. 4, 581-595. · Zbl 0388.68052
[6] [MPIR] The MPIR development team, MPIR: Multiple Precision Integers and Rationals, \urlhttp://www.mpir.org.
[7] [HanrotZimmermann2004] G. Hanrot and P. Zimmermann, Newton iteration revisited, \urlhttp://www.loria.fr/ zimmerma/papers/fastnewton.ps.gz, 2004.
[8] [Hart2010] 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, \urlhttp://flintlib.org, pp. 88-91. · Zbl 1273.11177
[9] Harvey, David, Faster algorithms for the square root and reciprocal of power series, Math. Comp., 80, 273, 387-394 (2011) · Zbl 1217.65052 · doi:10.1090/S0025-5718-2010-02392-0
[10] Hopcroft, J.; Musinski, J., Duality applied to the complexity of matrix multiplication and other bilinear forms, SIAM J. Comput., 2, 159-173 (1973) · Zbl 0294.65022
[11] Huang, Xiaohan; Pan, Victor Y., Fast rectangular matrix multiplication and applications, J. Complexity, 14, 2, 257-299 (1998) · Zbl 0919.65030 · doi:10.1006/jcom.1998.0476
[12] Kedlaya, Kiran S.; Umans, Christopher, Fast polynomial factorization and modular composition, SIAM J. Comput., 40, 6, 1767-1802 (2011) · Zbl 1333.11117 · doi:10.1137/08073408X
[13] Knuth, Donald E., The art of computer programming. Vol. 2, xiii+688 pp. (1981), Addison-Wesley Publishing Co., Reading, Mass. · Zbl 0895.65001
[14] Probert, Robert L., On the additive complexity of matrix multiplication, SIAM J. Comput., 5, 2, 187-203 (1976) · Zbl 0328.65029
[15] Ritzmann, Peter, A fast numerical algorithm for the composition of power series with complex coefficients, Theoret. Comput. Sci., 44, 1, 1-16 (1986) · Zbl 0632.68039 · doi:10.1016/0304-3975(86)90107-6
[16] [Stothers2010] A. J. Stothers, On the complexity of matrix multiplication, Ph.D. thesis, University of Edinburgh, 2010.
[17] van der Hoeven, Joris, Relax, but don’t be too lazy, J. Symbolic Comput., 34, 6, 479-542 (2002) · Zbl 1011.68189 · doi:10.1006/jsco.2002.0562
[18] von zur Gathen, Joachim; Gerhard, J{\"u}rgen, Modern computer algebra, xiv+785 pp. (2003), Cambridge University Press: Cambridge:Cambridge University Press · Zbl 1055.68168
[19] [VassilevskaWilliams2011] V. Vassilevska Williams, Breaking the Coppersmith-Winograd barrier, \urlhttp://cs.berkeley.edu/ virgi/matrixmult.pdf, 2011. \endbiblist
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.