Carine Pivoteau ; Bruno Salvy ; Michèle Soria - Boltzmann Oracle for Combinatorial Systems

dmtcs:3585 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science - https://doi.org/10.46298/dmtcs.3585
Boltzmann Oracle for Combinatorial SystemsArticle

Authors: Carine Pivoteau 1; Bruno Salvy ORCID2; Michèle Soria 1

  • 1 Algorithmes, Programmes et Résolution
  • 2 Algorithms

Boltzmann random generation applies to well-defined systems of recursive combinatorial equations. It relies on oracles giving values of the enumeration generating series inside their disk of convergence. We show that the combinatorial systems translate into numerical iteration schemes that provide such oracles. In particular, we give a fast oracle based on Newton iteration.


Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: Random generation,Boltzmann generation,combinatorics,Newton iteration,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Funding:
    Source : HAL
  • Génération Aléatoire : Modèles, Méthodes et Algorithmes; Funder: French National Research Agency (ANR); Code: ANR-07-BLAN-0330

6 Documents citing this article

Consultation statistics

This page has been seen 267 times.
This article's PDF has been downloaded 250 times.