## 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

gfun; CS; CABAL
Full Text:

### References:

  Bernardin, L., On bivariate hensel lifting and its parallelization, (), 96-100 · Zbl 0918.11063  Bernstein, D.J., Composing power series over a finite ring in essentially linear time, J. s. c., 26, 339-341, (1998) · Zbl 0934.68129  Brent, R.P.; Kung, H.T., O((n$$log$$n)3/2) algorithms for composition and reversion of power series, () · Zbl 0411.68043  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  Brent, R.P.; Kung, H.T., Fast algorithms for manipulating formal power series, J. ACM, 25, 581-595, (1978) · Zbl 0388.68052  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  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  Cantor, D.G.; Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta infor., 28, 693-701, (1991) · Zbl 0766.68055  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  S. A. Cook, 1966  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  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  Denise, A.; Zimmermann, P., Uniform random generation of decomposable structures using floating-point arithmetic, Theor. comput. sci., 218, 219-232, (1999)  Flajolet, P.; Salvy, B.; Zimmermann, P., Automatic average-case analysis of algorithms, T. c. s., 79, 37-109, (1990) · Zbl 0768.68041  Flajolet, P.; Sedgewick, R., An introduction to the analysis of algorithms, (1996), Addison-Wesley Reading, MA  Flajolet, P.; Soria, M., The cycle construction, SIAM J. discrete math., 4, 48-60, (1991) · Zbl 0714.05003  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  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)  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)  Karatsuba, A.; Ofman, J., Multiplication of multidigit numbers on automata, Sov. phys. dokl., 7, 595-596, (1963)  Knuth, D.E., The art of computer programming, volume 2 of seminumerical algorithms, (1997), Addison-Wesley  Kung, H.T.; Traub, J.F., All algebraic functions can be computed fast, J. ACM, 25, 245-260, (1978) · Zbl 0371.68019  G. Lecerf, É. Schost, 2001, GAGE, École polytechnique, 91228 Palaiseau, France  Lipshitz, L., D-finite power series, J. algeb., 122, 353-373, (1989) · Zbl 0695.12018  Mulders, T., On short multiplication and division, Aaecc, 11, 69-88, (2000) · Zbl 0968.68200  Norman, A.; Fitch, J., Cabal: polynomial and power series algebra on a parallel computer, (), 196-203 · Zbl 0923.68074  Norman, A.C., Computing with formal power series, ACM trans. math. software, 1, 346-356, (1975) · Zbl 0315.65044  Nussbaumer, H.J., Fast Fourier transforms and convolution algorithms, (1981), Springer · Zbl 0599.65098  Odlyzko, A.M., Periodic oscillations of coefficients of power series that satisfy functional equations, Adv. math., 44, 180-205, (1982) · Zbl 0484.30002  Pólya, G., Kombinatorische anzahlbestimmungen für gruppen, graphen und chemische verbindungen, Acta math., 68, 145-254, (1937) · JFM 63.0547.04  Richardson, D.; Salvy, B.; Shackell, J.; van der Hoeven, J., Expansions of exp-log functions, (), 309-313 · Zbl 0914.65008  B. Salvy, 1991  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  Schönhage, A.; Strassen, V., Schnelle multiplikation grosser zahlen, Computing, 7, 281-292, (1971) · Zbl 0223.68007  Sieveking, M., An algorithm for division of power series, Computing, 10, 153-156, (1972) · Zbl 0251.68023  M. Soria, 1990  Stanley, R.P., Differentially finite power series, Europ. J. comb., 1, 175-188 MR # 81m:05012, (1980)  Stanley, R.P., Enumerative combinatorics, (1999), Cambridge University Press · Zbl 0928.05001  Stroustrup, B., The C++ programming language, (1995), Addison-Wesley  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  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)  J. van der Hoeven, 1997a  van der Hoeven, J., Lazy multiplication of formal power series, (), 17-20 · Zbl 0932.68135  von Zurgathen, J.; Gerhard, J., Modern computer algebra, (1999), Cambridge University Press  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.