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

2:30pm, Tuesday May 17th, 2011, in K9509.

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.