Fast Algorithms for Manipulating Formal Power Series.
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
The classical algorithms require On sup 3 operations to compute the first n terms in the reversion of a power series or the composition of two series, and On 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 On log n sup 32 operations. In many cases of practical importance only On 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.
- Theoretical Mathematics