Reports

On the Complexity of Composition and Generalized Composition of Power Series

Brent, R. P.; Traub, Joseph F.

Let F(x) = f1x + f2(x)(x) + . . . be a formal power series over a field Delta. Let F superscript 0(x) = x and for q = 1,2 . . . , define F superscript q(x) = F superscript (q-1) (F(x)). The obvious algorithm for computing the first n terms of F superscript q(x) is by the composition position analogue of repeated squaring. This algorithm has complexity about log 2 q times that of a single composition. The factor log 2 q can be eliminated in the computation of the first n terms of (F(x)) to the q power by a change of representation, using the logarithm and exponential functions. We show the factor log 2 q can also be eliminated for the composition problem. F superscript q(x) can often, but not always, be defined for more general q. We give algorithms and complexity bounds for computing the first n terms of F superscript q(x) whenever it is defined.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-162-85
Published Here
October 31, 2011