Newton Iteration: From Numerics to Combinatorics, and Back
The talk will explore a variety of old and recent algorithms whose efficiency boils down to the fast convergence of Newton iteration. Numerically, and close to the root, the number of correct digits is doubled at each iteration. When working with power series, the problem of picking a good initial point disappears and the number of coefficients is doubled at each iteration. This observation, coupled with fast multiplication, leads to fast algorithms in a variety of problems of symbolic computation, ranging from classical results on algebraic series to more recent ones on systems of differential equations.
Newton iteration can be further lifted at the combinatorial level. There, quadratic convergence can be viewed in terms of increasing Strahler number. This combinatorial iteration translates to an efficient iteration on generating functions and yields an efficient algorithm for combinatorial enumeration. This improves the efficiency of random generation by the so-called recursive method. Furthermore, the numerical evaluation of this iteration leads to a fast numerical algorithm that was the missing step for efficient random generation by Boltzmann sampling, so that random objects of huge sizes can now be produced automatically.
Bruno Salvy, INRIA Rocquencourt, France