FAST ALGORITHMS FOR COMPOSITION AND REVERSION OF FORMAL POWER SERIES (PRELIMINARY VERSION)

R. P. BRENT AND H. T. KUNG

Abstract

In our earlier papers [1, 3], we gave fast algorithms for manipulating dense univariate power series. In this paper, fast algorithms for composition and reversion of dense multivariate power series are presented. The new algorithms require substantially less operations than the best previously known algorithms. The relative advantage of the new algorithms increases with the number of variables in the multivariate power series.

Comments

Only the Abstract is given here. The full paper appeared as [2]. The univariate case is considered in [3], and generalized composition is considered in [4]. It should be noted that most multivariate power series occurring in practice are sparse, i.e. many of the coefficients are zero, but our algorithms do not take advantage of this.

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. rpb029.

2. R. P. Brent and H. T. Kung, “Fast algorithms for composition and reversion of multivariate power series (preliminary version)”, 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.

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.

(Brent) Computer Centre, Australian National University, Canberra, Australia

(Kung) Department of Computer Science, Carnegie-Mellon University, Pittsburgh, Pennsylvania, USA

1991 Mathematics Subject Classification. Primary 68Q25; Secondary 65Y20, 68Q40. Key words and phrases. Formal power series, multivariate power series, reversion of power series,

composition of power series, computational complexity, fast algorithms.

CR Categories. 5.7, 5.15, 5.17. This work has been supported in part by the National Science Foundation under Grant MCS 75-222-55

and the Office of Naval Research under Contract N000014-76-C-0370, NR 044-422.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1977, the authors. Abstract and Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb039a typeset using AMS-L^{A}TEX