Accession Number:

ADA022987

Title:

Fast Algorithms for Manipulating Formal Power Series.

Descriptive Note:

Interim rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1976-01-01

Pagination or Media Count:

41.0

Abstract:

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE