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
Résumé : Nous considérons des systèmes de structures combinatoires définies récursivement. Nous présentons une méthode à convergence quadratique qui résout ces systèmes lorsqu'ils sont bien fondés. Nous en déduisons les troncatures des séries génératrices correspondantes en complexité quasi-optimale. Cette itération se traduit en un schéma numérique qui converge de manière inconditionnelle vers les valeurs des séries génératrices à l'intérieur de leur disque de convergence. Ces techniques sont notamment utiles en génération aléatoire.
Type de document :
Article dans une revue
Journal of Combinatorial Theory, Series A, Elsevier, 2012, 119 (8), pp.1711-1773. 〈10.1016/j.jcta.2012.05.007〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00622853
Contributeur : Bruno Salvy <>
Soumis le : lundi 12 septembre 2011 - 18:26:34
Dernière modification le : vendredi 31 août 2018 - 09:25:55
Document(s) archivé(s) le : mardi 13 novembre 2012 - 10:35:19

Fichiers

newtonOracleLong.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

693

Téléchargements de fichiers

255