Fast Algorithms for Manipulating Formal Power Series
Richard P. Brent, H. T. Kung · Journal of the ACM · 1978
The classical algorithms require order n ~ operations to compute the first n terms in the reversion of a power series or the composition of two series, and order nelog n operations if the fast Founer 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 order (n log n) ~/2 operations In many cases of practical importance only order n log n operations are required, these include certain special functions of power series and power series solution of certain differential equations Applications to root-finding methods which use inverse mterpolauon and to queuemg theory are described, some results on multivariate power series are stated, and several open questions are mentioned KEY WORDS AND PHRASES formal power series, reversion of power series, composition of power series, computational complexity, fast algorithms, special functions of power series, power series solution of dlfferentml equations, queuetng theory, fast Fourier transform CRCATEGORIES 57,5 15,5 17 IntroductionWe are mterested m the complexity of algorithms for mampulatlng formal power series.For example, such algorithms may compute the first n terms in the product, quotient, or composition of two gwen power series.These problems arise in combmatorics and analysis of algorithms, where the desired power series is a generating function, as well as in numerical analysis.See, for example, Knuth [26], Ferguson, Nielsen, and Cook [14], Riordan [35], Gilbert [18], Nwen [31], Jackson and Reilly [25], Levy and Lessman [30], Norman [32], and Henrici [20, 21].Let ~ be the integral domain of formal power series P(s) = po + p~s + p2s 2 + over some field K "Formal" means that we are not concerned with questions of convergence.If F is a set of indetermmates over K, and E is a finite subset of the extension field K(F), then L(E mod F) denotes the number of operations necessary to compute E, starting from K U F and working in K(F).Informally, L(E rood F) is the number of operations required to compute E, given F. If A, B E @ and C is the formal product of A and B, we define M(n) = L(¢o ..... cn mod a0 ..... an, b0 ..... b,,) Informally, M(n) is the number of operations required to compute the