On the Complexity of Composition and Generalized Composition of Power Series
 Title:
 On the Complexity of Composition and Generalized Composition of Power Series
 Author(s):
 Brent, R. P.
Traub, Joseph F.
 Date:
 1985
 Type:
 Reports
 Department(s):
 Computer Science
 Persistent URL:
 https://doi.org/10.7916/D8G167TN
 Series:
 Columbia University Computer Science Technical Reports
 Part Number:
 CUCS16285
 Publisher:
 Department of Computer Science, Columbia University
 Publisher Location:
 New York
 Abstract:
 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 (q1) (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.
 Subject(s):
 Computer science
 Item views
 174
 Metadata:

text  xml
 Suggested Citation:
 R. P. Brent, Joseph F. Traub, 1985, On the Complexity of Composition and Generalized Composition of Power Series, Columbia University Academic Commons, https://doi.org/10.7916/D8G167TN.