Fast Algorithms for Manipulating Formal Power Series.
Abstract
The classical algorithms require O(n sup 3) operations to compute the first n terms in the reversion of a power series or the composition of two series, and O((n sup 2) log n) operations 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 O((n log n) sup 3/2) operations. In many cases of practical importance only O(n log n) operations are required. An application to root-finding methods which use inverse interpolation is described, some results on multivariate power series are stated, and several open questions are mentioned.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1976
- Accession Number
- ADA022987
Entities
People
- H. T. Kung
- R. P. Brent
Organizations
- Carnegie Mellon University