## Relax, but don’t be too lazy.(English)Zbl 1011.68189

Summary: Assume that we wish to expand the product $$h= fg$$ of two formal power series $$f$$ and $$g$$. Classically, there are two types of algorithms to do this: zealous algorithms first expand $$f$$ and $$g$$ up to order $$n$$, multiply the results and truncate at order $$n$$. Lazy algorithms on the contrary compute the coefficients of $$f$$, $$g$$ and $$h$$ gradually and they perform no more computations than strictly necessary at each stage. In particular, at the moment we compute the coefficient $$h_i$$ of $$z^i$$ in $$h$$, only $$f_0,\dots, f_i$$ and $$g_0,\dots, g_i$$ are known.
Lazy algorithms have the advantage that the coefficients of $$f$$ and $$g$$ may actually depend on “previous” coefficients of $$h$$, as long as they are computed before they are needed in the multiplication, i.e. the coefficients $$f_i$$ and $$g_i$$ may depend on $$h_0,\dots, h_{i-1}$$. For this reason, lazy algorithms are extremely useful when solving functional equations in rings of formal power series. However, lazy algorithms have the disadvantage that the classical asymptotically fast multiplication algorithms on polynomials – such as the divide and conquer algorithm and fast Fourier multiplication – cannot be used.
In a previous paper, we therefore introduced relaxed algorithms, which share the property concerning the resolution of functional equations with lazy algorithms, but perform slightly more computations than lazy algorithms during the computation of a given coefficient of $$h$$. These extra computations anticipate the computations of the next coefficients of $$h$$ and dramatically improve the asymptotic time complexities of such algorithms.
In this paper, we survey several classical and new zealous algorithms for manipulating formal power series, including algorithms for multiplication, division, resolution of differential equations, composition and reversion. Next, we give various relaxed algorithms for these operations. All algorithms are specified in great detail and we prove theoretical time and space complexity bounds. Most algorithms have been experimentally implemented in C++ and we provide benchmarks. We conclude by some suggestions for future developments and a discussion of the fitness of the lazy and relaxed approaches for specific applications.
This paper is intended both for those who are interested in the most recent algorithms for the manipulation of formal power series and for those who want to actually implement a power series library into a computer algebra system.

### MSC:

 68W30 Symbolic computation and algebraic computation 13F25 Formal power series rings

### Keywords:

lazy algorithms; zealous algorithms; relaxed algorithms

CABAL; gfun; CS
Full Text:

### References:

 [1] Bernardin, L., On bivariate hensel lifting and its parallelization, (), 96-100 · Zbl 0918.11063 [2] Bernstein, D.J., Composing power series over a finite ring in essentially linear time, J. s. c., 26, 339-341, (1998) · Zbl 0934.68129 [3] Brent, R.P.; Kung, H.T., O((n$$log$$n)3/2) algorithms for composition and reversion of power series, () · Zbl 0411.68043 [4] Brent, R.P.; Kung, H.T., Fast algorithms for composition and reversion of multivariate power series, Proc. conf. th. comp. sc., Waterloo, Ontario, Canada, (1977), University of Waterloo, p. 149-158 · Zbl 0411.68043 [5] Brent, R.P.; Kung, H.T., Fast algorithms for manipulating formal power series, J. ACM, 25, 581-595, (1978) · Zbl 0388.68052 [6] Brent, R.P.; Traub, J.F., On the complexity of composition and generalized composition of power series, SIAM J. comput., 9, 54-66, (1980) · Zbl 0447.68033 [7] Canny, J.; Kaltofen, E.; Lakshman, Y., Solving systems of non-linear polynomial equations faster, Proceedings of ISSAC ’89, Portland, OR, (1989), ACM Press New York, p. 121-128 [8] Cantor, D.G.; Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta infor., 28, 693-701, (1991) · Zbl 0766.68055 [9] Chudnovsky, D.V.; Chudnovsky, G.V., Computer algebra in the service of mathematical physics and number theory (computers in mathematics, Stanford, CA, 1986), volume 125 of lecture notes in pure and applied mathematics, (1990), Dekker New York, p. 109-232 [10] S. A. Cook, 1966 [11] Cooley, J.W.; Tukey, J.W., An algorithm for the machine calculation of complex Fourier series, Math. comput., 19, 297-301, (1965) · Zbl 0127.09002 [12] Denise, A.; Dutour, I.; Zimmermann, P., Cs: a mupad package for counting and randomly generating combinatorial structures, Proceedings of FPSAC’98, (1998), Sofware Demonstration, p. 195-204 [13] Denise, A.; Zimmermann, P., Uniform random generation of decomposable structures using floating-point arithmetic, Theor. comput. sci., 218, 219-232, (1999) [14] Flajolet, P.; Salvy, B.; Zimmermann, P., Automatic average-case analysis of algorithms, T. c. s., 79, 37-109, (1990) · Zbl 0768.68041 [15] Flajolet, P.; Sedgewick, R., An introduction to the analysis of algorithms, (1996), Addison-Wesley Reading, MA [16] Flajolet, P.; Soria, M., The cycle construction, SIAM J. discrete math., 4, 48-60, (1991) · Zbl 0714.05003 [17] Flajolet, P.; Zimmerman, P.; Van Cutsem, B., A calculus for the random generation of labelled combinatorial structures, Theor. comput. sci., 132, 1-35, (1994) · Zbl 0799.68143 [18] Heideman, M.T.; Johnson, D.H.; Burrus, C.S., Gauss and the history of the fft, IEEE acoust. speech signal process. magazine, 1, 14-21, (1984) [19] Karatsuba, A.; Ofman, J., Умнoжнe мнoгoзнaчныx чиcэл нa aвтoмaтax, Dokl. akad. nauk SSSR, 7, 293-294 English translation in Karatsuba and Ofman (1963), (1962) [20] Karatsuba, A.; Ofman, J., Multiplication of multidigit numbers on automata, Sov. phys. dokl., 7, 595-596, (1963) [21] Knuth, D.E., The art of computer programming, volume 2 of seminumerical algorithms, (1997), Addison-Wesley [22] Kung, H.T.; Traub, J.F., All algebraic functions can be computed fast, J. ACM, 25, 245-260, (1978) · Zbl 0371.68019 [23] G. Lecerf, É. Schost, 2001, GAGE, École polytechnique, 91228 Palaiseau, France [24] Lipshitz, L., D-finite power series, J. algeb., 122, 353-373, (1989) · Zbl 0695.12018 [25] Mulders, T., On short multiplication and division, Aaecc, 11, 69-88, (2000) · Zbl 0968.68200 [26] Norman, A.; Fitch, J., Cabal: polynomial and power series algebra on a parallel computer, (), 196-203 · Zbl 0923.68074 [27] Norman, A.C., Computing with formal power series, ACM trans. math. software, 1, 346-356, (1975) · Zbl 0315.65044 [28] Nussbaumer, H.J., Fast Fourier transforms and convolution algorithms, (1981), Springer · Zbl 0599.65098 [29] Odlyzko, A.M., Periodic oscillations of coefficients of power series that satisfy functional equations, Adv. math., 44, 180-205, (1982) · Zbl 0484.30002 [30] Pólya, G., Kombinatorische anzahlbestimmungen für gruppen, graphen und chemische verbindungen, Acta math., 68, 145-254, (1937) · JFM 63.0547.04 [31] Richardson, D.; Salvy, B.; Shackell, J.; van der Hoeven, J., Expansions of exp-log functions, (), 309-313 · Zbl 0914.65008 [32] B. Salvy, 1991 [33] Salvy, B.; Zimmermann, P., Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM trans. math. software, 20, 163-177, (1994) · Zbl 0888.65010 [34] Schönhage, A.; Strassen, V., Schnelle multiplikation grosser zahlen, Computing, 7, 281-292, (1971) · Zbl 0223.68007 [35] Sieveking, M., An algorithm for division of power series, Computing, 10, 153-156, (1972) · Zbl 0251.68023 [36] M. Soria, 1990 [37] Stanley, R.P., Differentially finite power series, Europ. J. comb., 1, 175-188 MR # 81m:05012, (1980) [38] Stanley, R.P., Enumerative combinatorics, (1999), Cambridge University Press · Zbl 0928.05001 [39] Stroustrup, B., The C++ programming language, (1995), Addison-Wesley [40] Toom, A.L., The complexity of a scheme of functional elements realizing the multiplication of integers, Sov. math., 4, 714-716, (1963) · Zbl 0203.15604 [41] Toom, A.L., O cлoжнocти cкxмы из фyнктcиoнaльныx лэмэнтoв, pэaлизиpyюшчи yмнoжнe цлыx чиcл, Dokl. akad. nauk SSSR, 150, 496-498 English translation in Toom (1963a), (1963) [42] J. van der Hoeven, 1997a [43] van der Hoeven, J., Lazy multiplication of formal power series, (), 17-20 · Zbl 0932.68135 [44] von Zurgathen, J.; Gerhard, J., Modern computer algebra, (1999), Cambridge University Press [45] Zeilberger, D., A holonomic systems approach to special functions identities, J. comput. appl. math., 32, 321-368, (1990) · Zbl 0738.33001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.