Algorithms for combinatorial structures: Well-founded systems and Newton iterations.

Carine Pivoteau 1 Bruno Salvy 2 Michele Soria 3
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 APR - Algorithmes, Programmes et Résolution
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : We consider systems of recursively defined combinatorial structures. We give algorithms checking that these systems are well founded, computing generating series and providing numerical values. Our framework is an articulation of the constructible classes of Flajolet and Sedgewick with Joyal's species theory. We extend the implicit species theorem to structures of size zero. A quadratic iterative Newton method is shown to solve well-founded systems combinatorially. From there, truncations of the corresponding generating series are obtained in quasi-optimal complexity. This iteration transfers to a numerical scheme that converges unconditionally to the values of the generating series inside their disk of convergence. These results provide important subroutines in random generation. Finally, the approach is extended to combinatorial differential systems.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00622853
Contributor : Bruno Salvy <>
Submitted on : Monday, September 12, 2011 - 6:26:34 PM
Last modification on : Friday, May 24, 2019 - 5:28:24 PM
Long-term archiving on : Tuesday, November 13, 2012 - 10:35:19 AM

Files

newtonOracleLong.pdf
Files produced by the author(s)

Identifiers

Citation

Carine Pivoteau, Bruno Salvy, Michele Soria. Algorithms for combinatorial structures: Well-founded systems and Newton iterations.. Journal of Combinatorial Theory, Series A, Elsevier, 2012, 119 (8), pp.1711-1773. ⟨10.1016/j.jcta.2012.05.007⟩. ⟨inria-00622853⟩

Share

Metrics

Record views

743

Files downloads

337