MITACS Seminar Series on Mathematics of Computer Algebra and Analysis
Newton's Iteration for Combinatorial Systems and Applications.
Dr. Bruno Salvy, Projet ALGO, INRIA, Rocquencourt, France
Abstract: Many families of discrete objects defined recursively can be modeled by systems of combinatorial equations. Newton's iteration extends to this framework. It yields a quadratic iterative method for computing the structures. A consequence is that the enumeration of these objects can be performed in quasi-optimal complexity. Also, this iteration transfers to a numerical scheme that has applications in subroutines for efficient random generation. This is joint work with Carine Pivoteau and Michèle Soria.