FAST ALGORITHMS FOR MANIPULATING FORMAL POWER SERIES

R. P. BRENT AND H. T. KUNG

Abstract

The classical algorithms require order n^{3} operations to compute the first n terms in the reversion of a power series or the composition of two series, and order n^{2} log n if the fast Fourier transform is used for power series multiplication. In this paper we show that the composition and reversion problems are equivalent (up to constant factors), and we give algorithms which require only order (n log n)^{3/2} operations. In many cases of practical importance only order n log n operations are required; these include certain special functions of power series and power series solutions of certain differential equations. Applications to root-finding methods which use inverse interpolation and to queueing theory are described, some results on multivariate power series are stated, and several open questions are mentioned.

Comments

Only the Abstract is given here. The results were announced in [1], and the full paper appeared as [3]. The multivariate case is considered in [2], and generalized composition is considered in [4].

References

1. R. P. Brent and H. T. Kung, “O((n log n)^{3/2}) algorithms for composition and reversion of power series”, in Analytic Computational Complexity (edited by J. F. Traub), Academic Press, New York, 1975, 217– 225. MR 52#15938, 55#1699; Zbl 342.65010. Also appeared as a Technical Report, Department of Computer Science, Carnegie-Mellon University (May 1975), 7 pp. rpb029.

2. R. P. Brent and H. T. Kung, “Fast algorithms for composition and reversion of multivariate power series”, in Proceedings of a Conference on Theoretical Computer Science (held at the University of Waterloo), Department of Computer Science, University of Waterloo, Waterloo, Ontario (August 1977), 149–158. Zbl 404.00019, 411.68043. rpb039.

3. R. P. Brent and H. T. Kung, “Fast algorithms for manipulating formal power series”, Journal of the ACM 25 (1978), 581–595. CR 20#34535, MR 58#25090, Zbl 388.68052. Also appeared as a Technical Report, Department of Computer Science, Carnegie-Mellon University (January 1976), 38 pp. rpb045.

1991 Mathematics Subject Classification. Primary 68Q25; Secondary 65Y20, 68Q40.

Key words and phrases. Formal power series, reversion of power series, composition of power series, computational complexity, fast algorithms, special functions of power series, power series solution of differential equations, queueing theory, fast Fourier transform, root-finding, inverse interpolation.

CR Categories. 5.7, 5.15, 5.17.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1978, ACM. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb045a typeset using AMS-L^{A}TEX 2 RPB045A, BRENT AND KUNG

4. R. P. Brent and J. F. Traub, “On the complexity of composition and generalized composition of power series”, SIAM J. on Computing 9 (1980), 54–66. MR 81b:68042. rpb050. (Brent) Australian National University, Canberra, Australia (Kung) Carnegie-Mellon University, Pittsburgh, Pennsylvania, USA