Most of my papers are available in electronic form from the list below.

Usually, I put preliminary versions on arXiv. You can be informed of new ones by subscribing to this rss feed.

2025

• A. Bostan, B. Salvy, and M. F. Singer, “On deciding transcendence of power series,” arXiv, 2025.
  arXiv BibTeX

  @techreport{BostanSalvySinger2025,
    arxiv = {abs/2504.16697},
    author = {Bostan, Alin and Salvy, Bruno and Singer, Michael F.},
    eprint = {2504.16697},
    institution = {arXiv},
    title = {On deciding transcendence of power series},
    year = {2025}
  }
  

  Abstract

  It is well known that algebraic power series are differentially finite (D-finite): they satisfy linear differential equations with polynomial coefficients. The converse problem, whether a given D-finite power series is algebraic or transcendental, is notoriously difficult. We prove that this problem is decidable: we give two theoretical algorithms and a transcendence test that is efficient in practice.

• A. Ibrahim and B. Salvy, “Positivity Proofs for Linear Recurrences through Contracted Cones,” Journal of Symbolic Computation, 2025.
  arXiv doi BibTeX

  @article{IbrahimSalvy2025,
    arxiv = {abs/2412.08576},
    eprint = {2412.08576},
    author = {Ibrahim, Alaa and Salvy, Bruno},
    doi = {10.1016/j.jsc.2025.102463},
    journal = {Journal of Symbolic Computation},
    title = {Positivity Proofs for Linear Recurrences through Contracted Cones},
    year = {2025}
  }
  

  Abstract

  Deciding the positivity of a sequence defined by a linear recurrence with polynomial coefficients and initial condition is difficult in general. Even in the case of recurrences with constant coefficients, it is known to be decidable only for order up to 5. We consider a large class of linear recurrences of arbitrary order, with polynomial coefficients, for which an algorithm decides positivity for initial conditions outside of a hyperplane. The underlying algorithm constructs a cone, contracted by the recurrence operator, that allows a proof of positivity by induction. The existence and construction of such cones relies on the extension of the classical Perron-Frobenius theory to matrices leaving a cone invariant.

2024

• A. Bostan, T. Rivoal, and B. Salvy, “Minimization of differential equations and algebraic values of E-functions,” Mathematics of Computation, vol. 93, no. 347, pp. 1427–1472, 2024.
  arXiv doi BibTeX

  @article{BostanRivoalSalvy2024,
    arxiv = {abs/2209.01827},
    author = {Bostan, Alin and Rivoal, Tanguy and Salvy, Bruno},
    doi = {10.1090/mcom/3912},
    journal = {Mathematics of Computation},
    number = {347},
    pages = {1427--1472},
    title = {Minimization of differential equations and algebraic values of {$E$}-functions},
    volume = {93},
    year = {2024}
  }
  

  Abstract

  A power series being given as the solution of a linear differential equation with appropriate initial conditions, minimization consists in finding a non-trivial linear differential equation of minimal order having this power series as a solution. This problem exists in both homogeneous and inhomogeneous variants; it is distinct from, but related to, the classical problem of factorization of differential operators. Recently, minimization has found applications in Transcendental Number Theory, more specifically in the computation of non-zero algebraic points where Siegel’s E-functions take algebraic values. We present algorithms and implementations for these questions, and discuss examples and experiments.

• H. Brochet and B. Salvy, “Reduction-Based Creative Telescoping for Definite Summation of D-finite Functions,” Journal of Symbolic Computation, vol. 125, pp. 21 pages, 2024.
  arXiv doi BibTeX

  @article{BrochetSalvy2024,
    arxiv = {abs/2307.07216},
    author = {Brochet, Hadrien and Salvy, Bruno},
    doi = {10.1016/j.jsc.2024.102329},
    journal = {Journal of Symbolic Computation},
    pages = {21 pages},
    title = {Reduction-Based Creative Telescoping for Definite Summation of D-finite Functions},
    volume = {125},
    year = {2024}
  }
  

  Abstract

  Creative telescoping is an algorithmic method initiated by Zeilberger to compute definite sums by synthesizing summands that telescope, called certificates. We describe a creative telescoping algorithm that computes telescopers for definite sums of D-finite functions as well as the associated certificates in a compact form. The algorithm relies on a discrete analogue of the generalized Hermite reduction, or equivalently, a generalization of the Abramov-Petkovšek reduction. We provide a Maple implementation with good timings on a variety of examples.

• A. Ibrahim and B. Salvy, “Positivity certificates for linear recurrences,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024, pp. 982–994.
  arXiv doi BibTeX

  @inproceedings{IbrahimSalvy2024,
    arxiv = {abs/2306.05930},
    author = {Ibrahim, Alaa and Salvy, Bruno},
    booktitle = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
    doi = {10.1137/1.9781611977912.37},
    editor = {Woodruff, David P.},
    eprint = {2306.05930},
    month = jan,
    pages = {982--994},
    title = {Positivity certificates for linear recurrences},
    year = {2024}
  }
  

  Abstract

  We show that for solutions of linear recurrences with polynomial coefficients of Poincaré type and with a unique simple dominant eigenvalue, positivity reduces to deciding the genericity of initial conditions in a precisely defined way. We give an algorithm that produces a certificate of positivity that is a data-structure for a proof by induction. This induction works by showing that an explicitly computed cone is contracted by the iteration of the recurrence.

• M. Masson, D. Arzelier, F. Bréhard, M. Joldes, and B. Salvy, “Fast and reliable computation of the instantaneous orbital collision probability,” Journal of Guidance, Control, and Dynamics, vol. 47, no. 8, pp. 1660–1673, 2024.
  PDF doi BibTeX

  @article{MassonArzelierBrehardJoldesSalvy2024,
    author = {Masson, Matthieu and Arzelier, Denis and Br{\'e}hard, Florent and Joldes, Mioara and Salvy, Bruno},
    doi = {10.2514/1.G008102},
    journal = {Journal of Guidance, Control, and Dynamics},
    keywords = {debris risk management ; probability of collision ; Power series approximation ; Laplace transform ; Saddle-point approximation ; Numerical accuracy ; Cancellation Problem ; Holonomic Functions ; Error bounds ; Integration algorithm},
    number = {8},
    pages = {1660--1673},
    title = {Fast and reliable computation of the instantaneous orbital collision probability},
    url = {https://hal.laas.fr/hal-04134188},
    volume = {47},
    year = {2024}
  }
  

  Abstract

  Due to the increasing number of objects in Low Earth orbit, the fast and reliable estimation of the collision risk is an important challenge for spacecraft owners/operators. Among the available risk indicators, we focus on computing the instantaneous probability of collision, which can be modeled as the integral of a three-dimensional Gaussian probability density function over a Euclidean ball. We propose an efficient and accurate method for evaluating this integral. It is based on the combination of two complementary strategies. For the first one, convergent series and numerical error bounds are computed. These bounds provide a tradeoff between the accuracy needed and the number of terms to compute. The second one, using divergent series, approximates the value of the integral with a good accuracy in most cases with only a few terms computed. Based on those two methods, a hybrid algorithm is tested on cases borrowed from the literature and compared against existing methods. Several numerical results and comparisons confirm both the efficiency and robustness of our approach.

• J.-M. Muller and B. Salvy, “Effective Quadratic Error Bounds for Floating-Point Algorithms Computing the Hypotenuse Function,” arXiv, May 2024.
  arXiv BibTeX

  @techreport{MullerSalvy2024,
    arxiv = {abs/2405.03588},
    author = {Muller, Jean-Michel and Salvy, Bruno},
    eprint = {2405.03588},
    institution = {arXiv},
    month = may,
    title = {Effective Quadratic Error Bounds for Floating-Point Algorithms Computing the Hypotenuse Function},
    year = {2024}
  }
  

  Abstract

  We provide tools to help automate the error analysis of algorithms that evaluate simple functions over the floating-point numbers. The aim is to obtain tight relative error bounds for these algorithms, expressed as a function of the unit round-off. Due to the discrete nature of the set of floating-point numbers, the largest errors are often intrinsically arithmetic in the sense that their appearance may depend on specific bit patterns in the binary representations of intermediate variables, which may be present only for some precisions. We focus on generic (i.e., parameterized by the precision) and analytic over-estimations that still capture the correlations between the errors made at each step of the algorithms. Using methods from computer algebra, which we adapt to the particular structure of the polynomial systems that encode the errors, we obtain bounds with a linear term in the unit round-off that is sharp in manycases. An explicit quadratic bound is given, rather than the O()-estimate that is more common in this area. This is particularly important when using low precision formats, which are increasingly common in modern processors. Using this approach, we compare five algorithms for computing the hypotenuse function, ranging from elementary to quite challenging.

• V. Neiger, B. Salvy, É. Schost, and G. Villard, “Faster Modular Composition,” Journal of the ACM, vol. 71, no. 2, pp. 1–79, 2024.
  arXiv doi BibTeX

  @article{NeigerSalvySchostVillard2024,
    arxiv = {abs/2110.08354},
    author = {Neiger, Vincent and Salvy, Bruno and Schost, {\'E}ric and Villard, Gilles},
    doi = {10.1145/3638349},
    eprint = {2110.08354},
    institution = {arXiv},
    journal = {Journal of the ACM},
    number = {2},
    pages = {1--79},
    title = {Faster Modular Composition},
    volume = {71},
    year = {2024}
  }
  

  Abstract

  A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by n, the algorithm uses O(n^1.43) field operations, breaking through the 3/2 barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require O(n^1.63) field operations in general, and n^3/2+o(1) field operations in the particular case of power series over a field of large enough characteristic. If using cubic-time matrix multiplication, the new algorithm runs in n^5/3+o(1) operations, while previous ones run in O(n^2) operations. Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation.

• N. Pali and B. Salvy, “Explicit maximal totally real embeddings,” Advances in Mathematics, vol. 459, no. 110031, 2024.
  doi BibTeX

  @article{PaliSalvy2024,
    author = {Pali, Nefton and Salvy, Bruno},
    doi = {https://doi.org/10.1016/j.aim.2024.110031},
    issn = {0001-8708},
    journal = {Advances in Mathematics},
    keywords = {Maximal totally real embeddings, Complex structures, Grauert tubes, Covariant derivatives},
    number = {110031},
    title = {Explicit maximal totally real embeddings},
    volume = {459},
    year = {2024}
  }
  

  Abstract

  This article deals with an explicit canonical construction of a maximal totally real embedding for real analytic manifolds equipped with a covariant derivative operator acting on the real analytic sections of its tangent bundle or of its complexified tangent bundle. The existence of maximal totally real embeddings for real analytic manifolds is known from previous celebrated works by Bruhat-Whitney [1] and Grauert [4]. Their construction is based on the use of analytic continuation of local frames and local coordinates that are far from being canonical or explicit. As a consequence, the form of the corresponding complex structure has been a mystery since the very beginning. A quite simple recursive expression for such complex structures has been provided in the first author’s work “On maximal totally real embeddings” [12]. In our series of articles we focus on the case of torsion free connections. In the present article we give a fiberwise Taylor expansion of the canonical complex structure which is expressed in terms of symmetrization of curvature monomials and a rather simple and explicit expression of the coefficients of the expansion. We explain also a rather simple geometric characterization of such canonical complex structures. Our main result and argument can be useful for the study of open questions in the theory of the embeddings in consideration such as their moduli space.

2023

• N. Brisebarre and B. Salvy, “Differential-Difference Properties of Hypergeometric Series,” Proceedings of the American Mathematical Society, vol. 151, no. 6, pp. 2603–2617, 2023.
  arXiv doi BibTeX

  @article{BrisebarreSalvy2023,
    arxiv = {abs/2207.00393},
    author = {Brisebarre, Nicolas and Salvy, Bruno},
    doi = {10.1090/proc/16316},
    eprint = {2207.00393},
    journal = {Proceedings of the American Mathematical Society},
    number = {6},
    pages = {2603--2617},
    title = {Differential-Difference Properties of Hypergeometric Series},
    volume = {151},
    year = {2023}
  }
  

  Abstract

  Six families of generalized hypergeometric series in a variable x and an arbitrary number of parameters are considered. Each of them is indexed by an integer n. Linear recurrence relations in n relate these functions and their product by the variable x. We give explicit factorizations of these equations as products of first order recurrence operators. Related recurrences are also derived for the derivative with respect to x. These formulas generalize well-known properties of the classical orthogonal polynomials.

2022

• Y. Bugeaud, A. Dujella, W. Fang, T. Pejković, and B. Salvy, “Absolute root separation,” Experimental Mathematics, vol. 31, no. 3, pp. 805–812, 2022.
  arXiv doi BibTeX

  @article{BugeaudDujellaFangPejkovicSalvy2022,
    arxiv = {abs/1907.1232},
    author = {Bugeaud, Yann and Dujella, Andrej and Fang, Wenjie and Pejkovi{\'c}, Tomislav and Salvy, Bruno},
    doi = {10.1080/10586458.2019.1699480},
    eprint = {1907.1232},
    journal = {Experimental Mathematics},
    number = {3},
    pages = {805--812},
    title = {Absolute root separation},
    volume = {31},
    year = {2022}
  }
  

  Abstract

  The absolute separation of a polynomial is the minimum nonzero difference between the absolute values of its roots. In the case of polynomials with integer coefficients, it can be bounded from below in terms of the degree and the height (the maximum absolute value of the coefficients) of the polynomial. We improve the known bounds for this problem and related ones. Then we report on extensive experiments in low degrees, suggesting that the current bounds are still very pessimistic.

2021

• A. Bostan, T. Rivoal, and B. Salvy, “Explicit degree bounds for right factors of linear differential operators,” Bulletin of the London Mathematical Society, vol. 53, no. 1, pp. 53–62, 2021.
  arXiv doi BibTeX

  @article{BostanRivoalSalvy2021,
    arxiv = {abs/1906.05529},
    author = {Bostan, Alin and Rivoal, Tanguy and Salvy, Bruno},
    doi = {10.1112/blms.12396},
    eprint = {1906.05529},
    journal = {Bulletin of the London Mathematical Society},
    number = {1},
    pages = {53--62},
    title = {Explicit degree bounds for right factors of linear differential operators},
    volume = {53},
    year = {2021}
  }
  

  Abstract

  If a linear differential operator with rational function coefficients is reducible, its factors may have coefficients with numerators and denominators of very high degree. We give a completely explicit bound for the degrees of the (monic) right factors in terms of the degree and the order of the original operator, as well as the largest modulus of the local exponents at all its singularities, for which bounds are known in terms of the degree, the order and the height of the original operator.

• S. Melczer and B. Salvy, “Effective Coefficient Asymptotics of Multivariate Rational Functions via Semi-Numerical Algorithms for Polynomial Systems,” Journal of Symbolic Computation, vol. 103, pp. 234–279, 2021.
  arXiv doi BibTeX

  @article{MelczerSalvy2021,
    archiveprefix = {arXiv},
    arxiv = {abs/1905.04187},
    author = {Melczer, Stephen and Salvy, Bruno},
    doi = {10.1016/j.jsc.2020.01.001},
    eprint = {1905.04187},
    journal = {Journal of Symbolic Computation},
    pages = {234--279},
    primaryclass = {cs.SC},
    title = {Effective Coefficient Asymptotics of Multivariate Rational Functions via Semi-Numerical Algorithms for Polynomial Systems},
    volume = {103},
    year = {2021}
  }
  

  Abstract

  The coefficient sequences of multivariate rational functions appear in many areas of combinatorics. Their diagonal coefficient sequences enjoy nice arithmetic and asymptotic properties, and the field of analytic combinatorics in several variables (ACSV) makes it possible to compute asymptotic expansions. We consider these methods from the point of view of effectivity. In particular, given a rational function, ACSV requires one to determine a (generically) finite collection of points that are called critical and minimal. Criticality is an algebraic condition, meaning it is well treated by classical methods in computer algebra, while minimality is a semi-algebraic condition describing points on the boundary of the domain of convergence of a multivariate power series. We show how to obtain dominant asymptotics for the diagonal coefficient sequence of multivariate rational functions under some genericity assumptions using symbolic-numeric techniques. To our knowledge, this is the first completely automatic treatment and complexity analysis for the asymptotic enumeration of rational functions in an arbitrary number of variables.

2020

• J. Dahne and B. Salvy, “Computation of Tight Enclosures for Laplacian Eigenvalues,” SIAM J. Sci. Comput., vol. 42, no. 5, pp. A3210–A3232, 2020.
  arXiv doi BibTeX

  @article{DahneSalvy2020,
    arxiv = {abs/2003.08095},
    author = {Dahne, Joel and Salvy, Bruno},
    doi = {10.1137/20M1326520},
    eprint = {2003.08095},
    journal = {SIAM J. Sci. Comput.},
    number = {5},
    pages = {A3210--A3232},
    title = {Computation of Tight Enclosures for {L}aplacian Eigenvalues},
    volume = {42},
    year = {2020}
  }
  

  Abstract

  Recently, there has been interest in high precision approximations of the first eigenvalue of the Laplace–Beltrami operator on spherical triangles for combinatorial purposes. We compute improved and certified enclosures to these eigenvalues. This is achieved by applying the method of particular solutions in high precision, the enclosure being obtained by a combination of interval arithmetic and Taylor models. The index of the eigenvalue is certified by exploiting the monotonicity of the eigenvalue with respect to the domain. The classically troublesome case of singular corners is handled by combining expansions at all corners and an expansion from an interior point. In particular, this allows us to compute 100 digits of the fundamental eigenvalue for the three-dimensional Kreweras model that has been the object of previous efforts.

2019

• B. Salvy, “Linear Differential Equations as a Data-Structure,” Foundations of Computational Mathematics, vol. 19, no. 5, pp. 1071–1112, 2019.
  arXiv Read at Springer (free) doi BibTeX

  @article{Salvy2019,
    arxiv = {abs/1811.08616},
    author = {Salvy, Bruno},
    doi = {10.1007/s10208-018-09411-x},
    journal = {Foundations of Computational Mathematics},
    notetext = {the slides},
    noteurl = {http://perso.ens-lyon.fr/bruno.salvy/talks/},
    number = {5},
    pages = {1071--1112},
    title = {Linear Differential Equations as a Data-Structure},
    url = {https://rdcu.be/bfleN},
    volume = {19},
    year = {2019}
  }
  

  Abstract

  A lot of information concerning solutions of linear differential equations can be computed directly from the equation. It is therefore natural to consider these equations as a data-structure, from which mathematical properties can be computed. A variety of algorithms has thus been designed in recent years that do not aim at “solving”, but at computing with this representation. Many of these results are surveyed here.

  
  See also the slides

2018

• A. Bostan, F. Chyzak, P. Lairez, and B. Salvy, “Generalized Hermite Reduction, Creative Telescoping and Definite Integration of D-Finite Functions,” in ISSAC’18—Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, 2018, pp. 95–102.
  arXiv PDF from ACM (free) doi BibTeX

  @inproceedings{BostanChyzakLairezSalvy2018,
    arxiv = {abs/1805.03445},
    author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Lairez, Pierre and Salvy, Bruno},
    booktitle = {I{SSAC}'18---{P}roceedings of the 2018 {ACM} {I}nternational {S}ymposium on {S}ymbolic and {A}lgebraic {C}omputation},
    doi = {10.1145/3208976.3208992},
    pages = {95--102},
    publisher = {ACM Press},
    title = {Generalized {H}ermite Reduction, Creative Telescoping and Definite Integration of {D}-Finite Functions},
    url = {http://dl.acm.org/authorize?N667523},
    year = {2018}
  }
  

  Abstract

  Hermite reduction is a classical algorithmic tool in symbolic integration. It is used to decompose a given rational function as a sum of a function with simple poles and the derivative of another rational function. We extend Hermite reduction to arbitrary linear differential operators instead of the pure derivative, and develop efficient algorithms for this reduction. We then apply the generalized Hermite reduction to the computation of linear operators satisfied by single definite integrals of D-finite functions of several continuous or discrete parameters. The resulting algorithm is a generalization of reduction-based methods for creative telescoping.

• B. Salvy, “Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation,” in 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Dagstuhl, Germany, 2018, vol. 96, pp. 1:1–1:5.
  PDF doi BibTeX

  @inproceedings{Salvy2018,
    address = {Dagstuhl, Germany},
    author = {Salvy, Bruno},
    booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
    doi = {10.4230/LIPIcs.STACS.2018.1},
    editor = {Niedermeier, Rolf and Vall{\'e}e, Brigitte},
    isbn = {978-3-95977-062-0},
    issn = {1868-8969},
    notetext = {the slides and the Maple demo session},
    noteurl = {http://perso.ens-lyon.fr/bruno.salvy/talks/},
    pages = {1:1--1:5},
    publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    title = {{Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation}},
    url = {http://drops.dagstuhl.de/opus/volltexte/2018/8535},
    urn = {urn:nbn:de:0030-drops-85352},
    volume = {96},
    year = {2018},
    annote = {Keywords: Analytic Combinatorics, Generating Functions, Random Generation}
  }
  

  Abstract

  In a probabilistic context, the main data structures of computer science are viewed as random combinatorial objects. Analytic Combinatorics, as described in the book by Flajolet and Sedgewick, provides a set of high-level tools for their probabilistic analysis. Recursive combinatorial definitions lead to generating function equations from which efficient algorithms can be designed for enumeration, random generation and, to some extent, asymptotic analysis. With a focus on random generation, this tutorial first covers the basics of Analytic Combinatorics and then describes the idea of Boltzmann sampling and its realisation. The tutorial addresses a broad TCS audience and no particular pre-knowledge on analytic combinatorics is expected.

  
  See also the slides and the Maple demo session

2017

• A. Bostan et al., Algorithmes Efficaces en Calcul Formel. Palaiseau: Frédéric Chyzak (auto-édit.), 2017.
  PDF BibTeX

  @book{aecf-2017-livre,
    address = {Palaiseau},
    author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Giusti, Marc and Lebreton, Romain and Lecerf, Gr{\'e}goire and Salvy, Bruno and Schost, {\'E}ric},
    isbn = {979-10-699-0947-2},
    langid = {french},
    language = {french},
    month = sep,
    note = {686 pages. Imprim{\'e} par CreateSpace. Aussi disponible en version {\'e}lectronique.},
    publisher = {Fr{\'e}d{\'e}ric Chyzak (auto-{\'e}dit.)},
    title = {Algorithmes Efficaces en Calcul Formel},
    url = {https://hal.archives-ouvertes.fr/AECF/},
    year = {2017}
  }
  

  Abstract

  Le calcul formel traite des objets mathématiques exacts d’un point de vue informatique. L’ouvrage « Algorithmes efficaces en calcul formel » explore deux directions : la calculabilité et la complexité. La calculabilité étudie les classes d’objets mathématiques sur lesquelles des réponses peuvent être obtenues algorithmiquement. La complexité donne ensuite des outils pour comparer des algorithmes du point de vue de leur efficacité. Les premières parties de ce livre présentent des algorithmes rapides sur des objets de base (entiers, polynômes, séries, matrices, récurrences linéaires) en insistant sur des principes généraux de conception d’algorithmes efficaces. La suite de l’ouvrage construit sur ces parties pour aborder des questions qui ont connu des progrès récents : factorisation de polynômes, algorithmique des systèmes polynomiaux, sommation et intégration définie. Tiré de notes de cours de master, ce livre est accessible aux étudiants ayant suivi une licence ou une classe préparatoire scientifique. Il peut également servir d’introduction à l’algorithmique du calcul formel pour des scientifiques d’autres disciplines curieux d’ouvrir le capot et de comprendre comment fonctionnent les systèmes de calcul formel qu’ils utilisent, et comment en tirer meilleur profit.

  
  686 pages. Imprimé par CreateSpace. Aussi disponible en version électronique.
• A. Bostan, L. Dumont, and B. Salvy, “Algebraic Diagonals and Walks: Algorithms, Bounds, Complexity,” Journal of Symbolic Computation, vol. 83, pp. 68–92, 2017.
  arXiv doi BibTeX

  @article{BostanDumontSalvy2015a,
    arxiv = {abs/1510.04526},
    author = {Bostan, Alin and Dumont, Louis and Salvy, Bruno},
    doi = {10.1016/j.jsc.2016.11.006},
    eprint = {1510.04526},
    journal = {Journal of Symbolic Computation},
    note = {This is an extended version of the ISSAC'15 article, with more precise results and more detailed proofs.},
    pages = {68--92},
    title = {Algebraic Diagonals and Walks: Algorithms, Bounds, Complexity},
    volume = {83},
    year = {2017}
  }
  

  Abstract

  The diagonal of a multivariate power series F is the univariate power series Diag(F) generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case Diag(F) is an algebraic function. We propose an algorithm that computes an annihilating polynomial for Diag(F). We give a precise bound on the size of this polynomial and show that generically, this polynomial is the minimal polynomial and that its size reaches the bound. The algorithm runs in time quasi-linear in this bound, which grows exponentially with the degree of the input rational function. We then address the related problem of enumerating directed lattice walks. The insight given by our study leads to a new method for expanding the generating power series of bridges, excursions and meanders. We show that their first N terms can be computed in quasi-linear complexity in N, without first computing a very large polynomial equation.

  
  This is an extended version of the ISSAC’15 article, with more precise results and more detailed proofs.
• A. Bostan, P. Lairez, and B. Salvy, “Multiple binomial sums,” Journal of Symbolic Computation, vol. 80, pp. 351–386, 2017.
  arXiv doi BibTeX

  @article{BostanLairezSalvy2017,
    arxiv = {abs/1510.07487},
    author = {Bostan, Alin and Lairez, Pierre and Salvy, Bruno},
    doi = {10.1016/j.jsc.2016.04.002},
    eprint = {1510.07487},
    journal = {Journal of Symbolic Computation},
    pages = {351--386},
    title = {Multiple binomial sums},
    volume = {80},
    year = {2017}
  }
  

  Abstract

  Multiple binomial sums form a large class of multi-indexed sequences, closed under partial summation, which contains most of the sequences obtained by multiple summation of binomial coefficients and also all the sequences with algebraic generating function. We study the representation of the generating functions of binomial sums by integrals of rational functions. The outcome is twofold. Firstly, we show that a univariate sequence is a multiple binomial sum if and only if its generating function is the diagonal of a rational function. Secondly we propose algorithms that decide the equality of multiple binomial sums and that compute recurrence relations for them. In conjunction with geometric simplifications of the integral representations, this approach behaves well in practice. The process avoids the computation of certificates and the problem of accurate summation that afflicts discrete creative telescoping, both in theory and in practice.

• Y. Bugeaud, A. Dujella, T. Pejkovic, and B. Salvy, “Absolute real root separation,” The American Mathematical Monthly, vol. 124, no. 10, pp. 930–936, Dec. 2017.
  arXiv doi BibTeX

  @article{BugeaudDujellaPejkovicSalvy2017,
    arxiv = {abs/1606.01131},
    author = {Bugeaud, Yann and Dujella, Andrej and Pejkovic, Tomislav and Salvy, Bruno},
    doi = {10.4169/amer.math.monthly.124.10.930},
    eprint = {1606.01131},
    journal = {The American Mathematical Monthly},
    month = dec,
    number = {10},
    pages = {930--936},
    title = {Absolute real root separation},
    volume = {124},
    year = {2017}
  }
  

  Abstract

  While the separation (the minimal nonzero distance) between roots of a polynomial is a classical topic, its absolute counterpart (the minimal nonzero distance between their absolute values) does not seem to have been studied much. We present the general context and give tight bounds for the case of real roots.

2016

• A. Bostan, L. Dumont, and B. Salvy, “Efficient Algorithms for Mixed Creative Telescoping,” in ISSAC’16—Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation, 2016, pp. 127–134.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BostanDumontSalvy2016,
    author = {Bostan, Alin and Dumont, Louis and Salvy, Bruno},
    booktitle = {I{SSAC}'16---{P}roceedings of the 2016 {ACM} {I}nternational {S}ymposium on {S}ymbolic and {A}lgebraic {C}omputation},
    doi = {10.1145/2930889.2930907},
    pages = {127--134},
    publisher = {ACM Press},
    title = {Efficient Algorithms for Mixed Creative Telescoping},
    url = {http://dl.acm.org/authorize?N19133},
    year = {2016}
  }
  

  Abstract

  Creative telescoping is a powerful computer algebra paradigm -initiated by Doron Zeilberger in the 90’s- for dealing with definite integrals and sums with parameters. We address the mixed continuous-discrete case, and focus on the integration of bivariate hypergeometric-hyperexponential terms. We design a new creative telescoping algorithm operating on this class of inputs, based on a Hermite-like reduction procedure. The new algorithm has two nice features: it is efficient and it delivers, for a suitable representation of the input, a minimal-order telescoper. Its analysis reveals tight bounds on the sizes of the telescoper it produces.

• S. Melczer and B. Salvy, “Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables,” in ISSAC’16: Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation, New York, NY, USA, 2016, pp. 333–340.
  PDF from ACM (free) doi BibTeX

  @inproceedings{MelczerSalvy2016,
    address = {New York, NY, USA},
    author = {Melczer, Stephen and Salvy, Bruno},
    booktitle = {ISSAC'16: Proceedings of the 2016 {ACM} International Symposium on Symbolic and Algebraic Computation},
    doi = {10.1145/2930889.2930913},
    location = {Waterloo, Ontario, Canada},
    numpages = {8},
    pages = {333--340},
    publisher = {ACM},
    title = {Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables},
    url = {http://dl.acm.org/authorize?N19132},
    year = {2016}
  }
  

  Abstract

  Analytic combinatorics studies the asymptotic behaviour of sequences through the analytic properties of their generating functions. This article provides effective algorithms required for the study of analytic combinatorics in several variables, together with their complexity analyses. Given a multivariate rational function we show how to compute its smooth isolated critical points, with respect to a polynomial map encoding asymptotic behaviour, in complexity singly exponential in the degree of its denominator. We introduce a numerical Kronecker representation for solutions of polynomial systems with rational coefficients and show that it can be used to decide several properties (0 coordinate, equal coordinates, sign conditions for real solutions, and vanishing of a polynomial) in good bit complexity. Among the critical points, those that are minimal—a property governed by inequalities on the moduli of the coordinates—typically determine the dominant asymptotics of the diagonal coefficient sequence. When the Taylor expansion at the origin has all non-negative coefficients (known as the ‘combinatorial case’) and under regularity conditions, we utilize this Kronecker representation to determine probabilistically the minimal critical points in complexity singly exponential in the degree of the denominator, with good control over the exponent in the bit complexity estimate. Generically in the combinatorial case, this allows one to automatically and rigorously determine asymptotics for the diagonal coefficient sequence. Examples obtained with a preliminary implementation show the wide applicability of this approach.

• R. Serra, D. Arzelier, M. Joldes, J.-B. Lasserre, A. Rondepierre, and B. Salvy, “Fast and accurate computation of orbital collision probability for short-term encounters,” Journal of Guidance, Control, and Dynamics, vol. 39, no. 5, pp. 1009–1021, 2016.
  PDF doi BibTeX

  @article{SerraArzelierJoldesLasserreRondepierreSalvy2016,
    author = {Serra, Romain and Arzelier, Denis and Joldes, Mioara and Lasserre, Jean-Bernard and Rondepierre, Aude and Salvy, Bruno},
    doi = {10.2514/1.G001353},
    journal = {Journal of Guidance, Control, and Dynamics},
    number = {5},
    pages = {1009--1021},
    title = {Fast and accurate computation of orbital collision probability for short-term encounters},
    url = {https://hal.archives-ouvertes.fr/hal-01132149v1},
    volume = {39},
    year = {2016}
  }
  

  Abstract

  This article provides a new method for computing the probability of collision between two spherical space objects involved in a short-term encounter under Gaussian-distributed uncertainty. In this model of conjunction, classical assumptions reduce the probability of collision to the integral of a two-dimensional Gaussian probability density function over a disk. The computational method presented here is based on an analytic expression for the integral, derived by use of Laplace transform and D-finite functions properties. The formula has the form of a product between an exponential term and a convergent power series with positive coefficients. Analytic bounds on the truncation error are also derived and are used to obtain a very accurate algorithm. Another contribution is the derivation of analytic bounds on the probability of collision itself, allowing for a very fast and - in most cases - very precise evaluation of the risk. The only other analytical method of the literature - based on an approximation - is shown to be a special case of the new formula. A numerical study illustrates the efficiency of the proposed algorithms on a broad variety of examples and favorably compares the approach to the other methods of the literature.

2015

• M. Bardet, J.-C. Faugère, and B. Salvy, “On the Complexity of the F5 Gröbner basis Algorithm,” Journal of Symbolic Computation, vol. 70, pp. 49–70, 2015.
  arXiv doi BibTeX

  @article{BardetFaugereSalvy2015,
    arxiv = {abs/1312.1655},
    author = {Bardet, Magali and Faug{\`e}re, Jean-Charles and Salvy, Bruno},
    doi = {10.1016/j.jsc.2014.09.025},
    institution = {arXiv},
    journal = {Journal of Symbolic Computation},
    pages = {49--70},
    title = {On the Complexity of the {F}5 {G}r{\"o}bner basis Algorithm},
    volume = {70},
    year = {2015}
  }
  

  Abstract

  We study the complexity of Gröbner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system. We give a bound on the number of polynomials of degree d in a Gröbner basis computed by Faugère’s F_5 algorithm (2002) in this generic case for the grevlex ordering (which is also a bound on the number of polynomials for a reduced Gröbner basis, independently of the algorithm used). Next, we analyse more precisely the structure of the polynomials in the Gröbner bases with signatures that F_5 computes and use it to bound the complexity of the algorithm. Our estimates show that the version of F_5 we analyse, which uses only standard Gaussian elimination techniques, outperforms row reduction of the Macaulay matrix with the best known algorithms for moderate degrees, and even for degrees up to the thousands if Strassen’s multiplication is used. The degree being fixed, the factor of improvement grows exponentially with the number of variables.

• A. Bostan, L. Dumont, and B. Salvy, “Algebraic Diagonals and Walks,” in ISSAC’15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, New York, NY, USA, 2015, pp. 77–84.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BostanDumontSalvy2015,
    acmid = {2756663},
    address = {New York, NY, USA},
    author = {Bostan, Alin and Dumont, Louis and Salvy, Bruno},
    booktitle = {I{SSAC}'15: Proceedings of the 2015 {ACM} International Symposium on Symbolic and Algebraic Computation},
    doi = {10.1145/2755996.2756663},
    isbn = {978-1-4503-3435-8},
    keywords = {algorithms, diagonals, walks},
    location = {Bath, United Kingdom},
    numpages = {8},
    pages = {77--84},
    publisher = {ACM},
    title = {Algebraic Diagonals and Walks},
    url = {http://dl.acm.org/authorize?N02995},
    year = {2015}
  }
  

  Abstract

  The diagonal of a multivariate power series F is the univariate power series DiagF generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case DiagF is an algebraic function. We propose an algorithm that computes an annihilating polynomial for Diag F. Generically, it is its minimal polynomial and is obtained in time quasi-linear in its size. We show that this minimal polynomial has an exponential size with respect to the degree of the input rational function. We then address the related problem of enumerating directed lattice walks. The insight given by our study leads to a new method for expanding the generating power series of bridges, excursions and meanders. We show that their first N terms can be computed in quasi-linear complexity in N, without first computing a very large polynomial equation.

• S. Maulat and B. Salvy, “Formulas for Continued Fractions: An Automated Guess and Prove Approach,” in ISSAC’15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, New York, NY, USA, 2015, pp. 275–282.
  arXiv PDF from ACM (free) doi BibTeX

  @inproceedings{MaulatSalvy2015,
    acmid = {2756660},
    address = {New York, NY, USA},
    arxiv = {abs/1507.04203},
    author = {Maulat, S{\'e}bastien and Salvy, Bruno},
    booktitle = {I{SSAC}'15: Proceedings of the 2015 {ACM} International Symposium on Symbolic and Algebraic Computation},
    doi = {10.1145/2755996.2756660},
    isbn = {978-1-4503-3435-8},
    keywords = {continued fractions, p-recursive sequences, special functions},
    location = {Bath, United Kingdom},
    note = {See accompanying Maple worksheet on arXiv.},
    numpages = {8},
    pages = {275--282},
    publisher = {ACM},
    title = {Formulas for Continued Fractions: An Automated Guess and Prove Approach},
    url = {http://dl.acm.org/authorize?N02984},
    year = {2015}
  }
  

  Abstract

  We describe a simple method that produces automatically closed forms for the coefficients of continued fractions expansions of a large number of special functions. The function is specified by a non-linear differential equation and initial conditions. This is used to generate the first few coefficients and from there a conjectured formula. This formula is then proved automatically thanks to a linear recurrence satisfied by some remainder terms. Extensive experiments show that this simple approach and its straightforward generalization to difference and q-difference equations capture a large part of the formulas in the literature on continued fractions.

  
  See accompanying Maple worksheet on arXiv.

2014

• A. Bostan, K. Raschel, and B. Salvy, “Non-D-finite excursions in the quarter plane,” Journal of Combinatorial Theory, Series A, vol. 121, pp. 45–63, 2014.
  arXiv doi BibTeX

  @article{BostanRaschelSalvy2014,
    arxiv = {abs/1205.3300},
    author = {Bostan, Alin and Raschel, Kilian and Salvy, Bruno},
    doi = {10.1016/j.jcta.2013.09.005},
    eprint = {1205.3300},
    institution = {arXiv},
    journal = {Journal of Combinatorial Theory, Series {A}},
    pages = {45--63},
    title = {Non-{D}-finite excursions in the quarter plane},
    volume = {121},
    year = {2014}
  }
  

  Abstract

  We prove that the sequence (e^\mathfrakS_n)_n≥0 of excursions in the quarter plane corresponding to a nonsingular step set \mathfrakS⊆{0,\pm 1}^2 with infinite group does not satisfy any nontrivial linear recurrence with polynomial coefficients. Accordingly, in those cases, the trivariate generating function of the numbers of walks with given length and prescribed ending point is not D-finite. Moreover, we display the asymptotics of e^\mathfrakS_n.

• R. Serra, D. Arzelier, M. Joldes, J.-B. Lasserre, A. Rondepierre, and B. Salvy, “A New Method to Compute the Probability of Collision for Short-term Space Encounters,” in AIAA/AAS Astrodynamics Specialist Conference, 2014, pp. 1–7.
  doi BibTeX

  @inproceedings{SerraArzelierJoldesLasserreRondepierreSalvy2014,
    author = {Serra, Romain and Arzelier, Denis and Joldes, Mioara and Lasserre, Jean-Bernard and Rondepierre, Aude and Salvy, Bruno},
    booktitle = {{AIAA/AAS} Astrodynamics Specialist Conference},
    doi = {10.2514/6.2014-4366},
    pages = {1--7},
    publisher = {American Institute of Aeronautics and Astronautics},
    title = {A New Method to Compute the Probability of Collision for Short-term Space Encounters},
    year = {2014}
  }
  

  Abstract

  This article provides a new method for computing the probability of collision between two spherical space objects involved in a short-term encounter. In this specific framework of conjunction, classical assumptions reduce the probability of collision to the integral of a 2-D normal distribution over a disk shifted from the peak of the corresponding Gaussian function. Both integrand and domain of integration directly depend on the nature of the short-term encounter. Thus the inputs are the combined sphere radius, the mean relative position in the encounter plane at reference time as well as the relative position covariance matrix representing the uncertainties. The method presented here is based on an analytical expression for the integral. It has the form of a convergent power series whose coefficients verify a linear recurrence. It is derived using Laplace transform and properties of D-finite functions. The new method has been intensively tested on a series of test-cases and compares favorably to other existing works.

2013

• M. Bardet, J.-C. Faugère, B. Salvy, and P.-J. Spaenlehauer, “On the Complexity of Solving Quadratic Boolean Systems,” Journal of Complexity, vol. 29, no. 1, pp. 53–75, 2013.
  arXiv doi BibTeX

  @article{BardetFaugereSalvySpaenlehauer2013,
    arxiv = {abs/1112.6263},
    author = {Bardet, Magali and Faug{\`e}re, Jean-Charles and Salvy, Bruno and Spaenlehauer, Pierre-Jean},
    doi = {10.1016/j.jco.2012.07.001},
    journal = {Journal of Complexity},
    month = {f{\'e}vrier},
    number = {1},
    pages = {53--75},
    title = {On the Complexity of Solving Quadratic Boolean Systems},
    volume = {29},
    year = {2013}
  }
  

  Abstract

  A fundamental problem in computer science is to find all the common zeroes of m quadratic polynomials in n unknowns over F_2. The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in 4\log_2 n 2^n operations. We give an algorithm that reduces the problem to a combination of exhaustive search and sparse linear algebra. This algorithm has several variants depending on the method used for the linear algebra step. Under precise algebraic assumptions, we show that the deterministic variant of our algorithm has complexity bounded by O(2^0.841n) when m=n, while a probabilistic variant of the Las Vegas type has expected complexity O(2^0.792n). Experiments on random systems show that the algebraic assumptions are satisfied with probability very close to 1. We also give a rough estimate for the actual threshold between our method and exhaustive search, which is as low as 200, and thus very relevant for cryptographic applications.

• A. Bostan, P. Lairez, and B. Salvy, “Creative telescoping for rational functions using the Griffiths-Dwork method,” in ISSAC ’13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, 2013, pp. 93–100.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BostanLairezSalvy2013,
    author = {Bostan, Alin and Lairez, Pierre and Salvy, Bruno},
    booktitle = {I{SSAC} '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation},
    doi = {10.1145/2465506.2465935},
    editor = {Kauers, Manuel},
    eprint = {1301.4313},
    pages = {93--100},
    publisher = {ACM Press},
    title = {Creative telescoping for rational functions using the {G}riffiths-{D}work method},
    url = {http://dl.acm.org/authorize?N02996},
    year = {2013}
  }
  

  Abstract

  Creative telescoping algorithms compute linear differential equations satisfied by multiple integrals with parameters. We describe a precise and elementary algorithmic version of the Griffiths–Dwork method for the creative telescoping of rational functions. This leads to bounds on the order and degree of the coefficients of the differential equation, and to the first complexity result which is simply exponential in the number of variables. One of the important features of the algorithm is that it does not need to compute certificates. The approach is vindicated by a prototype implementation.

• B. Salvy, “Asymptotics of linear divide-and-conquer recurrences.” Summary of Philippe Dumas’ talk at the Flajolet seminar, IHP., pp. 1–8, 2013.
  PDF BibTeX

  @misc{Salvy2013a,
    author = {Salvy, Bruno},
    howpublished = {Summary of Philippe Dumas' talk at the Flajolet seminar, IHP.},
    organization = {Flajolet Seminar},
    pages = {1--8},
    title = {Asymptotics of linear divide-and-conquer recurrences},
    url = {http://semflajolet.math.cnrs.fr/uploads/Main/Dumas-synthese-IHP.pdf},
    year = {2013}
  }
  

• B. Salvy, “Philippe Flajolet and Symbolic Computation.” Preprint. To appear in Philippe Flajolet’s collected works., 2013.
  PDF BibTeX

  @misc{Salvy2013,
    author = {Salvy, Bruno},
    howpublished = {Preprint. To appear in Philippe Flajolet's collected works.},
    title = {Philippe {F}lajolet and Symbolic Computation},
    url = {https://sites.google.com/site/pfvolumes/home},
    year = {2013}
  }
  

2012

• A. Bostan, M. F. I. Chowdhury, R. Lebreton, B. Salvy, and É. Schost, “Power Series Solutions of Singular (q)-Differential Equations,” in ISSAC ’12: Proceedings of the twenty-fifth International Symposium on Symbolic and Algebraic Computation, 2012, pp. 107–114.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BostanChowdhuryLebretonSalvySchost2012,
    author = {Bostan, Alin and Chowdhury, Muhammad F. I. and Lebreton, Romain and Salvy, Bruno and Schost, {\'E}ric},
    booktitle = {I{SSAC} '12: Proceedings of the twenty-fifth International Symposium on Symbolic and Algebraic Computation},
    doi = {10.1145/2442829.2442847},
    editor = {van Hoeij, Mark and Van der Hoeven, Joris},
    eprint = {1205.3414},
    pages = {107--114},
    title = {Power Series Solutions of Singular (q)-Differential Equations},
    url = {http://dl.acm.org/authorize?N02998},
    year = {2012}
  }
  

  Abstract

  We provide algorithms computing power series solutions of a large class of differential or q-differential equations or systems. Their number of arithmetic operations grows linearly with the precision, up to logarithmic terms.

• A. Bostan, F. Chyzak, Z. Li, and B. Salvy, “Fast Computation of Common Left Multiples of Linear Ordinary Differential Operators,” in ISSAC ’12: Proceedings of the twenty-fifth International Symposium on Symbolic and Algebraic Computation, 2012, pp. 99–106.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BostanChyzakLiSalvy2012,
    author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Li, Ziming and Salvy, Bruno},
    booktitle = {I{SSAC} '12: Proceedings of the twenty-fifth International Symposium on Symbolic and Algebraic Computation},
    doi = {10.1145/2442829.2442847},
    editor = {van Hoeij, Mark and van der Hoeven, Joris},
    eprint = {1205.0879},
    pages = {99--106},
    title = {Fast Computation of Common Left Multiples of Linear Ordinary Differential Operators},
    url = {http://dl.acm.org/authorize?N02997},
    year = {2012}
  }
  

  Abstract

  We study tight bounds and fast algorithms for LCLMs of several linear differential operators with polynomial coefficients. We analyze the arithmetic complexity of existing algorithms for LCLMs, as well as the size of their outputs. We propose a new algorithm that recasts the LCLM computation in a linear algebra problem on a polynomial matrix. This algorithm yields sharp bounds on the coefficient degrees of the LCLM, improving by one order of magnitude the best bounds obtained using previous algorithms. The complexity of the new algorithm is almost optimal, in the sense that it nearly matches the arithmetic size of the output.

• C. Pivoteau, B. Salvy, and M. Soria, “Algorithms for Combinatorial Structures: Well-founded systems and Newton iterations,” Journal of Combinatorial Theory, Series A, vol. 119, pp. 1711–1773, 2012.
  arXiv doi BibTeX

  @article{PivoteauSalvySoria2012,
    arxiv = {abs/1109.2688},
    author = {Pivoteau, Carine and Salvy, Bruno and Soria, Mich{\`e}le},
    doi = {10.1016/j.jcta.2012.05.007},
    journal = {Journal of Combinatorial Theory, Series A},
    pages = {1711--1773},
    title = {Algorithms for Combinatorial Structures: Well-founded systems and {N}ewton iterations},
    volume = {119},
    year = {2012}
  }
  

  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.

2011

• F. Chyzak, J. H. Davenport, C. Koutschan, and B. Salvy, “On Kahan’s Rules for Determining Branch Cuts,” in Proceedings of the 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2011), 2011, pp. 47–51.
  arXiv doi BibTeX

  @inproceedings{ChyzakDavenportKoutschanSalvy2011,
    arxiv = {abs/1109.2809},
    author = {Chyzak, Fr{\'e}d{\'e}ric and Davenport, James H. and Koutschan, Christoph and Salvy, Bruno},
    booktitle = {Proceedings of the 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2011)},
    doi = {10.1109/SYNASC.2011.51},
    pages = {47--51},
    publisher = {IEEE Computer Society},
    title = {On {K}ahan's Rules for Determining Branch Cuts},
    year = {2011}
  }
  

  Abstract

  In computer algebra there are different ways of approaching the mathematical concept of functions, one of which is by defining them as solutions of differential equations. We compare different such approaches and discuss the occurring problems. The main focus is on the question of determining possible branch cuts. We explore the extent to which the treatment of branch cuts can be rendered (more) algorithmic, by adapting Kahan’s rules to the differential equation setting.

• J.-G. Dumas, L. Fousse, and B. Salvy, “Simultaneous modular reduction and Kronecker substitution for small finite fields,” Journal of Symbolic Computation, vol. 46, no. 7, pp. 823–840, 2011.
  doi BibTeX

  @article{DumasFousseSalvy2011,
    author = {Dumas, Jean-Guillaume and Fousse, Laurent and Salvy, Bruno},
    doi = {10.1016/j.jsc.2010.08.015},
    journal = {Journal of Symbolic Computation},
    month = {juillet},
    number = {7},
    pages = {823--840},
    title = {Simultaneous modular reduction and {K}ronecker substitution for small finite fields},
    volume = {46},
    year = {2011}
  }
  

  Abstract

  We present algorithms to perform modular polynomial multiplication or a modular dot product efficiently in a single machine word. We use a combination of techniques. Polynomials are packed into integers by Kronecker substitution; several modular operations are performed at once with machine integer or floating point arithmetic; normalization of modular images is avoided when possible; some conversions back to polynomial coefficients are avoided; the coefficients are recovered efficiently by preparing them before conversion. We discuss precisely the required control on sizes and degrees. We then present applications to polynomial multiplication, prime field linear algebra and small extension field arithmetic, where these techniques lead to practical gains of quite large constant factors.

2010

• A. Benoit, F. Chyzak, A. Darrasse, S. Gerhold, M. Mezzarobba, and B. Salvy, “The Dynamic Dictionary of Mathematical Functions (DDMF),” in The Third International Congress on Mathematical Software (ICMS 2010), 2010, vol. 6327, pp. 35–41.
  doi BibTeX

  @inproceedings{BenoitChyzakDarrasseGerholdMezzarobbaSalvy2010,
    author = {Benoit, Alexandre and Chyzak, Fr{\'e}d{\'e}ric and Darrasse, Alexis and Gerhold, Stefan and Mezzarobba, Marc and Salvy, Bruno},
    booktitle = {The Third International Congress on Mathematical Software (ICMS 2010)},
    doi = {10.1007/978-3-642-15582-6_7},
    editor = {Fukuda, Komei and van der Hoeven, Joris and Joswig, Michael and Takayama, Nobuki},
    pages = {35--41},
    series = {Lecture Notes in Computer Science},
    title = {The Dynamic Dictionary of Mathematical Functions ({DDMF})},
    volume = {6327},
    year = {2010}
  }
  

  Abstract

  We describe the main features of the Dynamic Dictionary of Mathematical Functions (version 1.5). It is a website consisting of interactive tables of mathematical formulas on elementary and special functions. The formulas are automatically generated by computer algebra routines. The user can ask for more terms of the expansions, more digits of the numerical values, or proofs of some of the formulas.

• A. Bostan, B. Salvy, and É. Schost, “Fast conversion algorithms for orthogonal polynomials,” Linear Algebra and its Applications, vol. 432, no. 1, pp. 249–258, Jan. 2010.
  arXiv doi BibTeX

  @article{BostanSalvySchost2010,
    arxiv = {abs/0804.2373},
    author = {Bostan, Alin and Salvy, Bruno and Schost, {\'E}ric},
    doi = {10.1016/j.laa.2009.08.002},
    journal = {Linear Algebra and its Applications},
    month = jan,
    number = {1},
    pages = {249--258},
    title = {Fast conversion algorithms for orthogonal polynomials},
    volume = {432},
    year = {2010}
  }
  

  Abstract

  We discuss efficient conversion algorithms for orthogonal polynomials. We describe a known conversion algorithm from an arbitrary orthogonal basis to the monomial basis, and deduce a new algorithm of the same complexity for the converse operation.

• A. Bostan, B. Salvy, and K. Tran, “Generating functions of Chebyshev-like polynomials,” International Journal of Number Theory, vol. 6, no. 7, pp. 1659–1667, 2010.
  arXiv doi BibTeX

  @article{BostanSalvyTran2010,
    arxiv = {abs/0907.0291},
    author = {Bostan, Alin and Salvy, Bruno and Tran, Khang},
    doi = {10.1142/S1793042110003691},
    journal = {International Journal of Number Theory},
    number = {7},
    pages = {1659--1667},
    title = {Generating functions of {C}hebyshev-like polynomials},
    volume = {6},
    year = {2010}
  }
  

  Abstract

  In this short note, we give simple proofs of several results and conjectures formulated by Stolarsky and Tran concerning generating functions of some families of Chebyshev-like polynomials.

• P. Flajolet, S. Gerhold, and B. Salvy, “Lindelöf Representations and (Non-)Holonomic Sequences,” The Electronic Journal of Combinatorics, vol. 17, no. 1, pp. 1–28, 2010.
  arXiv PDF BibTeX

  @article{FlajoletGerholdSalvy2010,
    arxiv = {abs/0906.1957},
    author = {Flajolet, Philippe and Gerhold, Stefan and Salvy, Bruno},
    journal = {The Electronic Journal of Combinatorics},
    number = {1},
    pages = {1--28},
    title = {Lindel{\"o}f Representations and (Non-)Holonomic Sequences},
    url = {http://www.combinatorics.org/ojs/index.php/eljc/article/download/v17i1r3/pdf},
    volume = {17},
    year = {2010}
  }
  

  Abstract

  Various sequences that possess explicit analytic expressions can be analysed asymptotically through integral representations due to Lindelöf, which belong to an attractive but largely forgotten chapter of complex analysis. One of the outcomes of such analyses concerns the non-existence of linear recurrences with polynomial coefficients annihilating these sequences, and, accordingly, the non-existence of linear differential equations with polynomial coefficients annihilating their generating functions. In particular, the corresponding generating functions are transcendental. Asymptotics of certain finite difference sequences come out as a byproduct of our approach.

• M. Mezzarobba and B. Salvy, “Effective Bounds for P-Recursive Sequences,” Journal of Symbolic Computation, vol. 45, no. 10, pp. 1075–1096, Oct. 2010.
  arXiv doi BibTeX

  @article{MezzarobbaSalvy2010,
    arxiv = {abs/0904.2452},
    author = {Mezzarobba, Marc and Salvy, Bruno},
    doi = {10.1016/j.jsc.2010.06.024},
    journal = {Journal of Symbolic Computation},
    month = oct,
    number = {10},
    pages = {1075--1096},
    title = {Effective Bounds for {P}-Recursive Sequences},
    volume = {45},
    year = {2010}
  }
  

  Abstract

  We describe an algorithm that takes as input a complex sequence (u_n) given by a linear recurrence relation with polynomial coefficients along with initial values, and outputs a simple explicit upper bound (v_n) such that |u_n| ≤v_n for all n. Generically, the bound is tight, in the sense that its asymptotic behaviour matches that of u_n. We discuss applications to the evaluation of power series with guaranteed precision.

• B. Salvy and J. Shackell, “Measured limits and multiseries,” Journal of the London Mathematical Society, vol. 82, no. 3, pp. 747–762, 2010.
  PDF doi BibTeX

  @article{SalvyShackell2010,
    author = {Salvy, Bruno and Shackell, John},
    doi = {10.1112/jlms/jdq057},
    journal = {Journal of the London Mathematical Society},
    number = {3},
    pages = {747--762},
    title = {Measured limits and multiseries},
    url = {http://jlms.oxfordjournals.org/content/82/3/747},
    volume = {82},
    year = {2010}
  }
  

  Abstract

  We introduce the notion of a measured limit and show how it can give meaning to asymptotic expansions in which the coefficients are variable and may even have poles. We give an algorithm for computing the measured multiseries of a large class of elementary functions.

2009

• A. Benoit and B. Salvy, “Chebyshev Expansions for Solutions of Linear Differential Equations,” in ISSAC ’09: Proceedings of the twenty-second international symposium on Symbolic and algebraic computation, 2009, pp. 23–30.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BenoitSalvy2009,
    author = {Benoit, Alexandre and Salvy, Bruno},
    booktitle = {I{SSAC} '09: Proceedings of the twenty-second international symposium on Symbolic and algebraic computation},
    doi = {10.1145/1576702.1576709},
    editor = {May, John},
    pages = {23--30},
    title = {Chebyshev Expansions for Solutions of Linear Differential Equations},
    url = {http://dl.acm.org/authorize?N02992},
    year = {2009}
  }
  

  Abstract

  A Chebyshev expansion is a series in the basis of Chebyshev polynomials of the first kind. When such a series solves a linear differential equation, its coefficients satisfy a linear recurrence equation. We interpret this equation as the numerator of a fraction of linear recurrence operators. This interpretation lets us give a simple view of previous algorithms, analyze their complexity, and design a faster one for large orders.

• F. Chyzak, M. Kauers, and B. Salvy, “A Non-Holonomic Systems Approach to Special Function Identities,” in ISSAC ’09: Proceedings of the twenty-second international symposium on Symbolic and algebraic computation, 2009, pp. 111–118.
  PDF from ACM (free) doi BibTeX

  @inproceedings{ChyzakKauersSalvy2009,
    author = {Chyzak, Fr{\'e}d{\'e}ric and Kauers, Manuel and Salvy, Bruno},
    booktitle = {I{SSAC} '09: Proceedings of the twenty-second international symposium on Symbolic and algebraic computation},
    doi = {10.1145/1576702.1576720},
    editor = {May, John},
    pages = {111--118},
    title = {A Non-Holonomic Systems Approach to Special Function Identities},
    url = {http://dl.acm.org/authorize?N02993},
    year = {2009}
  }
  

  Abstract

  We extend Zeilberger’s approach to special function identities to cases that are not holonomic. The method of creative telescoping is thus applied to definite sums or integrals involving Stirling or Bernoulli numbers, incomplete Gamma function or polylogarithms, which are not covered by the holonomic framework. The basic idea is to take into account the dimension of appropriate ideals in Ore algebras. This unifies several earlier extensions and provides algorithms for summation and integration in classes that had not been accessible to computer algebra before.

• P. Clote, E. Kranakis, D. Krizanc, and B. Salvy, “Asymptotics of Canonical and Saturated RNA Secondary Structures,” Journal of Bioinformatics and Computational Biology, vol. 7, no. 5, pp. 869–893, Oct. 2009.
  PDF doi BibTeX

  @article{CloteKranakisKrizancSalvy2009,
    author = {Clote, Peter and Kranakis, Evangelos and Krizanc, Danny and Salvy, Bruno},
    doi = {10.1142/S0219720009004333},
    journal = {Journal of Bioinformatics and Computational Biology},
    month = oct,
    number = {5},
    pages = {869--893},
    title = {Asymptotics of Canonical and Saturated RNA Secondary Structures},
    url = {http://www.worldscinet.com/jbcb/07/0705/S0219720009004333.html},
    volume = {7},
    year = {2009}
  }
  

  Abstract

  It is a classical result of Stein and Waterman that the asymptotic number of RNA secondary structures is 1.104366 ⋅n^-3/2⋅2.618034^n. In this paper, we study combinatorial asymptotics for two special subclasses of RNA secondary structures — canonical and saturated structures. Canonical secondary structures are defined to have no lonely (isolated) base pairs. This class of secondary structures was introduced by Bompfünewerer et al., who noted that the run time of Vienna RNA Package is substantially reduced when restricting computations to canonical structures. Here we provide an explanation for the speed-up, by proving that the asymptotic number of canonical RNA secondary structures is 2.1614 ⋅n^-3/2 ⋅1.96798^n and that the expected number of base pairs in a canonical secondary structure is 0.31724 ⋅n. The asymptotic number of canonical secondary structures was obtained much earlier by Hofacker, Schuster and Stadler using a different method. Saturated secondary structures have the property that no base pairs can be added without violating the definition of secondary structure (i.e. introducing a pseudoknot or base triple). Here we show that the asymptotic number of saturated structures is 1.07427 ⋅n^-3/2⋅2.35467^n, the asymptotic expected number of base pairs is 0.337361⋅n, and the asymptotic number of saturated stem-loop structures is 0.323954 ⋅1.69562^n, in contrast to the number 2^n - 2 of (arbitrary) stem-loop structures as classically computed by Stein and Waterman. Finally, we apply the work of Drmota to show that the density of states for [all resp. canonical resp. saturated] secondary structures is asymptotically Gaussian. We introduce a stochastic greedy method to sample random saturated structures, called quasi-random saturated structures, and show that the expected number of base pairs is 0.340633 ⋅n.

2008

• J. M. Borwein and B. Salvy, “A proof of a recursion for Bessel moments,” Experimental Mathematics, vol. 17, no. 2, pp. 223–230, 2008.
  PDF doi BibTeX

  @article{BorweinSalvy2008,
    author = {Borwein, Jonathan M. and Salvy, Bruno},
    doi = {10.1080/10586458.2008.10129032},
    journal = {Experimental Mathematics},
    number = {2},
    pages = {223--230},
    title = {A proof of a recursion for {B}essel moments},
    url = {http://projecteuclid.org/euclid.em/1227118973},
    volume = {17},
    year = {2008}
  }
  

  Abstract

  We provide a proof of a conjecture in (Bailey, Borwein, Borwein, Crandall 2007) on the existence and form of linear recursions for moments of powers of the Bessel function K_0.

• A. Bostan, F. Morain, B. Salvy, and É. Schost, “Fast algorithms for computing isogenies between elliptic curves,” Mathematics of Computation, vol. 77, no. 263, pp. 1755–1778, 2008.
  arXiv doi BibTeX

  @article{BostanMorainSalvySchost2008,
    arxiv = {cs/0609020},
    author = {Bostan, Alin and Morain, Fran\c{c}ois and Salvy, Bruno and Schost, {\'E}ric},
    doi = {10.1090/S0025-5718-08-02066-8},
    journal = {Mathematics of Computation},
    month = {juillet},
    number = {263},
    pages = {1755--1778},
    title = {Fast algorithms for computing isogenies between elliptic curves},
    volume = {77},
    year = {2008}
  }
  

  Abstract

  We survey algorithms for computing isogenies between elliptic curves defined over a field of characteristic either 0 or a large prime. We introduce a new algorithm that computes an isogeny of degree \ell (\ell different from the characteristic) in time quasi-linear with respect to \ell. This is based in particular on fast algorithms for power series expansion of the Weierstrass \wp-function and related functions.

• A. Bostan, B. Salvy, and É. Schost, “Power Series Composition and Change of Basis,” in ISSAC’08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, 2008, pp. 269–276.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BostanSalvySchost2008,
    author = {Bostan, Alin and Salvy, Bruno and Schost, {\'E}ric},
    booktitle = {I{SSAC}'08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation},
    doi = {10.1145/1390768.1390806},
    editor = {Jeffrey, David J.},
    pages = {269--276},
    publisher = {ACM Press},
    title = {Power Series Composition and Change of Basis},
    url = {http://dl.acm.org/authorize?N02994},
    year = {2008}
  }
  

  Abstract

  Efficient algorithms are known for many operations on truncated power series (multiplication, powering, exponential,...). Composition is a more complex task. We isolate a large class of power series for which composition can be performed efficiently. We deduce fast algorithms for converting polynomials between various bases, including Euler, Bernoulli, Fibonacci, and the orthogonal Laguerre, Hermite, Jacobi, Krawtchouk, Meixner and Meixner-Pollaczek.

• J.-G. Dumas, L. Fousse, and B. Salvy, “Compressed Modular Matrix Multiplication,” in Milestones in Computer Algebra (MICA 2008), 2008.
  arXiv BibTeX

  @inproceedings{DumasFousseSalvy2008,
    arxiv = {abs/0803.1975},
    author = {Dumas, Jean-Guillaume and Fousse, Laurent and Salvy, Bruno},
    booktitle = {Milestones in Computer Algebra (MICA 2008)},
    editor = {Moreno Maza, Marc and Watt, Stephen M.},
    month = {mai},
    title = {Compressed Modular Matrix Multiplication},
    year = {2008}
  }
  

  Abstract

  Matrices of integers modulo a small prime can be compressed by storing several entries into a single machine word. Modular addition is performed by addition and possibly subtraction of a word containing several times the modulo. We show how modular multiplication can also be performed. In terms of arithmetic operations, the gain over classical matrix multiplication is equal to the number of integers that are stored inside a machine word. The gain in actual speed is also close to that number. First, modular dot product can be performed via an integer multiplication by the reverse integer. Modular multiplication by a word containing a single residue is also possible. We give bounds on the sizes of primes and matrices for which such a compression is possible. We also make explicit the details of the required compressed arithmetic routines and show some practical performance.

• C. Gomez and B. Salvy, “Calcul Formel,” Les Techniques de l’Ingénieur, vol. Dossier AF1460, pp. 1–20, 2008.
  BibTeX

  @article{GomezSalvy2008,
    author = {Gomez, Claude and Salvy, Bruno},
    journal = {Les Techniques de l'Ing{\'e}nieur},
    pages = {1--20},
    title = {Calcul Formel},
    volume = {Dossier AF1460},
    year = {2008}
  }
  

• C. Pivoteau, B. Salvy, and M. Soria, “Boltzmann Oracle for Combinatorial Systems,” in Algorithms, Trees, Combinatorics and Probabilities, 2008, pp. 475–488.
  PDF BibTeX

  @inproceedings{PivoteauSalvySoria2008,
    author = {Pivoteau, Carine and Salvy, Bruno and Soria, Mich{\`e}le},
    booktitle = {Algorithms, Trees, Combinatorics and Probabilities},
    pages = {475--488},
    publisher = {Discrete Mathematics and Theoretical Computer Science},
    title = {Boltzmann Oracle for Combinatorial Systems},
    url = {https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAI0132/},
    year = {2008}
  }
  

  Abstract

  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.

2007

• A. Bostan, F. Chyzak, G. Lecerf, B. Salvy, and É. Schost, “Differential equations for algebraic functions,” in ISSAC’07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation, 2007, pp. 25–32.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BostanChyzakLecerfSalvySchost2007,
    author = {Bostan, Alin and Chyzak, Fr\'ed\'eric and Lecerf, Gr\'egoire and Salvy, Bruno and Schost, {\'E}ric},
    booktitle = {I{SSAC}'07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation},
    doi = {10.1145/1277548.1277553},
    editor = {Brown, C. W.},
    pages = {25--32},
    publisher = {ACM Press},
    title = {Differential equations for algebraic functions},
    url = {http://dl.acm.org/authorize?N02905},
    year = {2007}
  }
  

  Abstract

  It is classical that univariate algebraic functions satisfy linear differential equations with polynomial coefficients. Linear recurrences follow for the coefficients of their power series expansions. We show that the linear differential equation of minimal order has coefficients whose degree is cubic in the degree of the function. We also show that there exists a linear differential equation of order linear in the degree whose coefficients are only of quadratic degree. Furthermore, we prove the existence of recurrences of order and degree close to optimal. We study the complexity of computing these differential equations and recurrences. We deduce a fast algorithm for the expansion of algebraic series.

• A. Bostan, F. Chyzak, F. Ollivier, B. Salvy, É. Schost, and A. Sedoglavic, “Fast computation of power series solutions of systems of differential equations,” in SODA’07, 2007, pp. 1012–1021.
  arXiv BibTeX

  @inproceedings{BostanChyzakOllivierSalvySchostSedoglavic2007,
    arxiv = {abs/cs/0604101},
    author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Ollivier, Fran{\c c}ois and Salvy, Bruno and Schost, {\'E}ric and Sedoglavic, Alexandre},
    booktitle = {SODA'07},
    month = jan,
    pages = {1012--1021},
    publisher = {Society for Industrial and Applied Mathematics},
    title = {Fast computation of power series solutions of systems of differential equations},
    year = {2007}
  }
  

  Abstract

  We propose new algorithms for the computation of the first N terms of a vector (resp. a basis) of power series solutions of a linear system of differential equations at an ordinary point, using a number of arithmetic operations which is quasi-linear with respect to N. Similar results are also given in the non-linear case. This extends previous results obtained by Brent and Kung for scalar differential equations of order one and two.

• M. Giusti, G. Lecerf, B. Salvy, and J.-C. Yakoubsohn, “On Location and Approximation of Clusters of Zeroes: Case of Embedding Dimension One,” Foundations of Computational Mathematics, vol. 7, no. 1, pp. 1–58, 2007.
  Read at Springer (free) doi BibTeX

  @article{GiustiLecerfSalvyYakoubsohn2007,
    author = {Giusti, Marc and Lecerf, Gr{\'e}goire and Salvy, Bruno and Yakoubsohn, Jean-Claude},
    doi = {10.1007/s10208-004-0159-5},
    journal = {Foundations of Computational Mathematics},
    month = {f{\'e}vrier},
    number = {1},
    pages = {1--58},
    title = {On Location and Approximation of Clusters of Zeroes: Case of Embedding Dimension One},
    url = {https://rdcu.be/bfEfU},
    volume = {7},
    year = {2007}
  }
  

  Abstract

  Isolated multiple zeros or clusters of zeros of analytic maps with several variables are known to be difficult to locate and approximate. This article is in the vein of the α-theory, initiated by M. Shub and S. Smale in the beginning of the eighties. This theory restricts to simple zeros, i.e., where the map has corank zero. In this article we deal with situations where the analytic map has corank one at the multiple isolated zero, which has embedding dimension one in the frame of deformation theory. These situations are the least degenerate ones and therefore most likely to be of practical significance. More generally, we define clusters of embedding dimension one. We provide a criterion for locating such clusters of zeros and a fast algorithm for approximating them, with quadratic convergence. In case of a cluster with positive diameter our algorithm stops at a distance of the cluster which is about its diameter.

2006

• A. Bostan, F. Chyzak, T. Cluzeau, and B. Salvy, “Low Complexity Algorithms for Linear Recurrences,” in ISSAC’06, 2006, pp. 31–38.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BostanChyzakCluzeauSalvy2006,
    author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Cluzeau, Thomas and Salvy, Bruno},
    booktitle = {I{SSAC}'06},
    doi = {10.1145/1145768.1145781},
    editor = {Dumas, Jean-Guillaume},
    pages = {31--38},
    publisher = {ACM Press},
    title = {Low Complexity Algorithms for Linear Recurrences},
    url = {http://dl.acm.org/authorize?N02906},
    year = {2006}
  }
  

  Abstract

  We consider two kinds of problems: the computation of polynomial and rational solutions of linear recurrences with coefficients that are polynomials with integer coefficients; indefinite and definite summation of sequences that are hypergeometric over the rational numbers. The algorithms for these tasks all involve as an intermediate quantity an integer N (dispersion or root of an indicial polynomial) that is potentially exponential in the bit size of their input. Previous algorithms have a bit complexity that is at least quadratic in N. We revisit them and propose variants that exploit the structure of solutions and avoid expanding polynomials of degree N. We give two algorithms: a probabilistic one that detects the existence or absence of nonzero polynomial and rational solutions in O(\sqrtN\log^2N) bit operations; a deterministic one that computes a compact representation of the solution in O(N\log^3N) bit operations. Similar speed-ups are obtained in indefinite and definite hypergeometric summation. We describe the results of an implementation.

• A. Bostan, P. Flajolet, B. Salvy, and É. Schost, “Fast Computation of Special Resultants,” Journal of Symbolic Computation, vol. 41, no. 1, pp. 1–29, Jan. 2006.
  doi BibTeX

  @article{BostanFlajoletSalvySchost2006,
    author = {Bostan, Alin and Flajolet, Philippe and Salvy, Bruno and Schost, {\'E}ric},
    doi = {10.1016/j.jsc.2005.07.001},
    journal = {Journal of Symbolic Computation},
    month = jan,
    number = {1},
    pages = {1--29},
    title = {Fast Computation of Special Resultants},
    volume = {41},
    year = {2006}
  }
  

  Abstract

  We propose fast algorithms for computing composed products and composed sums, as well as diamond products of univariate polynomials. These operations correspond to special multivariate resultants, that we compute using power sums of roots of polynomials, by means of their generating series.

2005

• M. Bardet, J.-C. Faugère, B. Salvy, and B.-Y. Yang, “Asymptotic Behaviour of the Degree of Regularity of Semi-Regular Polynomial Systems,” in MEGA’05, 2005.
  BibTeX

  @inproceedings{BardetFaugereSalvyYang2005,
    author = {Bardet, M. and Faug{\`e}re, J.-C. and Salvy, B. and Yang, B.-Y.},
    booktitle = {MEGA'05},
    title = {Asymptotic Behaviour of the Degree of Regularity of Semi-Regular Polynomial Systems},
    year = {2005}
  }
  

  Abstract

  We compute the asymptotic expansion of the degree of regularity for overdetermined semi-regular sequences of algebraic equations. This degree implies bounds for the generic complexity of Gröbner bases algorithms, in particular Faugère’s F_5 algorithm. Bounds can also be derived for the XL family of algorithms used by the cryptographic community.

• A. Bostan, T. Cluzeau, and B. Salvy, “Fast Algorithms for Polynomial Solutions of Linear Differential Equations,” in ISSAC’05, New York, 2005, pp. 45–52.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BostanCluzeauSalvy2005,
    address = {New York},
    author = {Bostan, Alin and Cluzeau, Thomas and Salvy, Bruno},
    booktitle = {I{SSAC}'05},
    doi = {10.1145/1073884.1073893},
    editor = {Kauers, Manuel},
    note = {Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, July 2005, Beijing, China.},
    pages = {45--52},
    publisher = {ACM Press},
    title = {Fast Algorithms for Polynomial Solutions of Linear Differential Equations},
    url = {http://dl.acm.org/authorize?N02908},
    year = {2005}
  }
  

  Abstract

  We investigate polynomial solutions of homogeneous linear differential equations with coefficients that are polynomials with integer coefficients. The problems we consider are the existence of nonzero polynomial solutions, the determination of the dimension of the vector space of polynomial solutions, the computation of a basis of this space. Previous algorithms have a bit complexity that is at least quadratic in the largest integer valuation N of formal Laurent series solutions at infinity, even for merely detecting the existence of nonzero polynomial solutions. We give a deterministic algorithm that computes a compact representation of a basis of polynomial solutions in O(N\log^3N) bit operations. We also give a probabilistic algorithm that computes the dimension of the space of polynomial solutions in O(N\log^2N) bit operations. In general, the integer N is not polynomially bounded in the bit size of the input differential equation. We isolate a class of equations for which detecting nonzero polynomial solutions can be performed in polynomial complexity. We discuss implementation issues and possible extensions.

  
  Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, July 2005, Beijing, China.
• F. Chyzak, M. Mishna, and B. Salvy, “Effective Scalar Products of D-finite Symmetric Functions,” Journal of Combinatorial Theory. Series A, vol. 112, no. 1, pp. 1–43, Oct. 2005.
  arXiv doi BibTeX

  @article{ChyzakMishnaSalvy2005,
    arxiv = {abs/math/0310132},
    author = {Chyzak, Fr\'ed\'eric and Mishna, Marni and Salvy, Bruno},
    doi = {10.1016/j.jcta.2005.01.001},
    journal = {Journal of Combinatorial Theory. Series A},
    month = oct,
    number = {1},
    pages = {1--43},
    title = {Effective Scalar Products of {D}-finite Symmetric Functions},
    volume = {112},
    year = {2005}
  }
  

  Abstract

  Many combinatorial generating functions can be expressed as combinations of symmetric functions, or extracted as sub-series and specializations from such combinations. Gessel has outlined a large class of symmetric functions for which the resulting generating functions are D-finite. We extend Gessel’s work by providing algorithms that compute differential equations, these generating functions satisfy in the case they are given as a scalar product of symmetric functions in Gessel’s class. Examples of applications to k-regular graphs and Young tableaux with repeated entries are given. Asymptotic estimates are a natural application of our method, which we illustrate on the same model of Young tableaux. We also derive a seemingly new formula for the Kronecker product of the sum of Schur functions with itself.

• P. Flajolet, S. Gerhold, and B. Salvy, “On the non-holonomic character of logarithms, powers, and the nth prime function,” The Electronic Journal of Combinatorics, vol. 11, no. 2, 2005.
  PDF BibTeX

  @article{FlajoletGerholdSalvy2005,
    author = {Flajolet, Philippe and Gerhold, Stefan and Salvy, Bruno},
    journal = {The Electronic Journal of Combinatorics},
    month = {avril},
    number = {2},
    title = {On the non-holonomic character of logarithms, powers, and the nth prime function},
    url = {http://www.combinatorics.org/ojs/index.php/eljc/article/download/v11i2a2/pdf},
    volume = {11},
    year = {2005}
  }
  

  Abstract

  We establish that the sequences formed by logarithms and by “fractional” powers of integers, as well as the sequence of prime numbers, are non-holonomic, thereby answering three open problems of Gerhold [\emphEl. J. Comb. \bf 11 (2004), R87]. Our proofs depend on basic complex analysis, namely a conjunction of the Structure Theorem for singularities of solutions to linear differential equations and of an Abelian theorem. A brief discussion is offered regarding the scope of singularity-based methods and several naturally occurring sequences are proved to be non-holonomic.

• M. Giusti, G. Lecerf, B. Salvy, and J.-C. Yakoubsohn, “On Location and Approximation of Clusters of Zeroes of Analytic Functions,” Foundations of Computational Mathematics, vol. 5, no. 3, pp. 257–311, 2005.
  Read at Springer (free) doi BibTeX

  @article{GiustiLecerfSalvyYakoubsohn2005,
    author = {Giusti, Marc and Lecerf, Gr{\'e}goire and Salvy, Bruno and Yakoubsohn, Jean-Claude},
    doi = {10.1007/s10208-004-0144-z},
    journal = {Foundations of Computational Mathematics},
    month = {juillet},
    number = {3},
    pages = {257--311},
    title = {On Location and Approximation of Clusters of Zeroes of Analytic Functions},
    url = {https://rdcu.be/bfEf4},
    volume = {5},
    year = {2005}
  }
  

  Abstract

  At the beginning of the 1980s, M. Shub and S. Smale developed a quantitative analysis of Newton’s method for multivariate analytic maps. In particular, their α-theory gives an effective criterion that ensures safe convergence to a simple isolated zero. This criterion requires only information concerning the map at the initial point of the iteration. Generalizing this theory to multiple zeros and clusters of zeros is still a challenging problem. In this paper we focus on one complex variable function. We study general criteria for detecting clusters and analyze the convergence of Schröder’s iteration to a cluster. In the case of a multiple root, it is well known that this convergence is quadratic. In the case of a cluster with positive diameter, the convergence is still quadratic provided the iteration is stopped sufficiently early. We propose a criterion for stopping this iteration at a distance from the cluster which is of the order of its diameter.

• B. Salvy, “D-Finiteness: Algorithms and Applications,” in ISSAC’05, 2005, pp. 2–3.
  PDF from ACM (free) doi BibTeX

  @inproceedings{Salvy2005,
    author = {Salvy, Bruno},
    booktitle = {I{SSAC}'05},
    doi = {10.1145/1073884.1073886},
    editor = {Kauers, Manuel},
    note = {Abstract for an invited talk. Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, Beijing, July 2005.},
    pages = {2--3},
    publisher = {ACM Press},
    title = {D-Finiteness: Algorithms and Applications},
    url = {http://dl.acm.org/authorize?N02907},
    year = {2005}
  }
  

  
  Abstract for an invited talk. Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, Beijing, July 2005.

2004

• M. Bardet, J.-C. Faugère, and B. Salvy, “On the Complexity of Gröbner basis computation of Semi-regular Overdetermined algebraic equations,” in International Conference on Polynomial System Solving, 2004, pp. 71–74.
  BibTeX

  @inproceedings{BardetFaugereSalvy2004,
    author = {Bardet, Magali and Faug{\`e}re, Jean-Charles and Salvy, Bruno},
    booktitle = {International Conference on Polynomial System Solving},
    month = nov,
    pages = {71--74},
    title = {On the Complexity of {G}r{\"o}bner basis computation of Semi-regular Overdetermined algebraic equations},
    year = {2004}
  }
  

  Abstract

  We extend Macaulay’s notion of regular sequence to overdetermined system of algebraic equations. We study generic properties of Gröbner bases and analyse precisely the behavior of Faugère’s F5 algorithm. Sharp asymptotic estimates of the degree of regularity are given.

• A. Bostan, G. Lecerf, B. Salvy, É. Schost, and B. Wiebelt, “Complexity Issues in Bivariate Polynomial Factorization,” in Symbolic and Algebraic Computation, 2004, pp. 42–49.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BostanLecerfSalvySchostWiebelt2004,
    author = {Bostan, Alin and Lecerf, Gr{\'e}goire and Salvy, Bruno and Schost, {\'E}ric and Wiebelt, Bernd},
    booktitle = {Symbolic and Algebraic Computation},
    doi = {10.1145/1005285.1005294},
    editor = {Gutierrez, J.},
    note = {Proceedings of I{SSAC}'04, Santander, July 2004},
    pages = {42--49},
    publisher = {ACM Press},
    title = {Complexity Issues in Bivariate Polynomial Factorization},
    url = {http://dl.acm.org/authorize?N02909},
    year = {2004}
  }
  

  Abstract

  Many polynomial factorization algorithms rely on Hensel lifting and factor recombination. For bivariate polynomials we show that lifting the factors up to a precision linear in the total degree of the polynomial to be factored is sufficient to deduce the recombination by linear algebra, using trace recombination. Then, the total cost of the lifting and the recombination stage is subquadratic in the size of the dense representation of the input polynomial. Lifting is often the practical bottleneck of this method: we propose an algorithm based on a faster multi-moduli computation for univariate polynomials and show that it saves a constant factor compared to the classical multifactor lifting algorithm.

  
  Proceedings of ISSAC’04, Santander, July 2004
• P. Flajolet, B. Salvy, and G. Schaeffer, “Airy Phenomena and Analytic Combinatorics of Connected Graphs,” The Electronic Journal of Combinatorics, vol. 11, no. 1, p. R34, 2004.
  PDF BibTeX

  @article{FlajoletSalvySchaeffer2004,
    author = {Flajolet, Philippe and Salvy, Bruno and Schaeffer, Gilles},
    journal = {The Electronic Journal of Combinatorics},
    month = {mai},
    number = {1},
    pages = {R34},
    title = {Airy Phenomena and Analytic Combinatorics of Connected Graphs},
    url = {http://www.combinatorics.org/ojs/index.php/eljc/article/download/v11i1r34/pdf},
    volume = {11},
    year = {2004}
  }
  

  Abstract

  Until now, the enumeration of connected graphs has been dealt with by probabilistic methods, by special combinatorial decompositions or by somewhat indirect formal series manipulations. We show here that it is possible to make analytic sense of the divergent series that expresses the generating function of connected graphs. As a consequence, it becomes possible to derive analytically known enumeration results using only first principles of combinatorial analysis and straight asymptotic analysis—specifically, the saddle-point method. In this perspective, the enumeration of connected graphs by excess (of number of edges over number of vertices) derives from a simple saddle-point analysis. Furthermore, a refined analysis based on coalescent saddle points yields complete asymptotic expansions for the number of graphs of fixed excess, through an explicit connection with Airy functions.

2003

• A. Bostan, B. Salvy, and É. Schost, “Fast Algorithms for Zero-Dimensional Polynomial Systems Using Duality,” Applicable Algebra in Engineering, Communication and Computing, vol. 14, no. 4, pp. 239–272, 2003.
  Read at Springer (free) doi BibTeX

  @article{BostanSalvySchost2003,
    author = {Bostan, Alin and Salvy, Bruno and Schost, {\'E}ric},
    doi = {10.1007/s00200-003-0133-5},
    journal = {Applicable Algebra in Engineering, Communication and Computing},
    number = {4},
    pages = {239--272},
    title = {Fast Algorithms for Zero-Dimensional Polynomial Systems Using Duality},
    url = {https://rdcu.be/bfEgb},
    volume = {14},
    year = {2003}
  }
  

  Abstract

  Many questions concerning a zero-dimensional polynomial system can be reduced to linear algebra operations in the quotient algebra A=k[X_1,…,X_n]/I, where I is the ideal generated by the input system. Assuming that the multiplicative structure of the algebra A is (partly) known, we address the question of speeding up the linear algebra phase for the computation of minimal polynomials and rational parametrizations in A. We present new formulæ for the rational parametrizations, extending those of Rouillier, and algorithms extending ideas introduced by Shoup in the univariate case. Our approach is based on the A-module structure of the dual space \widehatA. An important feature of our algorithms is that we do not require \widehatA to be free and of rank 1. The complexity of our algorithms for computing the minimal polynomial and the rational parametrizations are O(2^nD^5/2) and O(n2^nD^5/2) respectively, where D is the dimension of A. For fixed n, this is better than algorithms based on linear algebra except when the complexity of the available matrix product has exponent less than 5/2.

• L. Meunier and B. Salvy, “ESF: An Automatically Generated Encyclopedia of Special Functions,” in Symbolic and Algebraic Computation, 2003, pp. 199–205.
  PDF from ACM (free) doi BibTeX

  @inproceedings{MeunierSalvy2003,
    author = {Meunier, Ludovic and Salvy, Bruno},
    booktitle = {Symbolic and Algebraic Computation},
    doi = {10.1145/860854.860898},
    editor = {Sendra, J. R.},
    note = {Proceedings of I{SSAC}'03, Philadelphia, August 2003.},
    pages = {199--205},
    publisher = {ACM Press},
    title = {{ESF}: An Automatically Generated Encyclopedia of Special Functions},
    url = {http://dl.acm.org/authorize?N02900},
    year = {2003}
  }
  

  Abstract

  We present our on-going work on the automatic generation of an encyclopedia of special functions on the web, called The Encyclopedia of Special Functions (ESF) http://algo.inria.fr/esf. All mathematical formulæ in the ESF are computed, typeset and displayed without any human intervention. This is achieved by exploiting a collection of computer algebra algorithms in a systematic way, on top of a specially designed data structure for a class of special functions.

  
  Proceedings of ISSAC’03, Philadelphia, August 2003.

2002

• F. Chyzak, M. Mishna, and B. Salvy, “Effective D-finite Symmetric Functions,” in 14th Conference of Formal Power Series and Algebraic Combinatorics, Melbourne, Australia, 2002, pp. 19.1–19.12.
  BibTeX

  @inproceedings{ChyzakMishnaSalvy2002,
    address = {Melbourne, Australia},
    author = {Chyzak, Fr\'ed\'eric and Mishna, Marni and Salvy, Bruno},
    booktitle = {14th Conference of Formal Power Series and Algebraic Combinatorics},
    month = {juillet},
    pages = {19.1--19.12},
    publisher = {University of Melbourne},
    title = {Effective {D}-finite Symmetric Functions},
    year = {2002}
  }
  

• R. Cori, D. Rossin, and B. Salvy, “Polynomial Ideals for Sandpiles and their Gröbner Bases,” Theoretical Computer Science, vol. 276, no. 1, pp. 1–15, 2002.
  doi BibTeX

  @article{CoriRossinSalvy2002,
    author = {Cori, Robert and Rossin, Dominique and Salvy, Bruno},
    doi = {10.1016/S0304-3975(00)00397-2},
    journal = {Theoretical Computer Science},
    number = {1},
    pages = {1--15},
    title = {Polynomial Ideals for Sandpiles and their {G}r{\"o}bner Bases},
    volume = {276},
    year = {2002}
  }
  

  Abstract

  A polynomial ideal encoding topplings in the abelian sandpile model on a graph is introduced. A Gröbner basis of this ideal is interpreted combinatorially in terms of well-connected subgraphs. This gives rise to algorithms to determine the identity and the operation in the group of recurrent configurations.

• P. Nicodème, B. Salvy, and P. Flajolet, “Motif Statistics,” Theoretical Computer Science, vol. 287, no. 2, pp. 593–618, 2002.
  doi BibTeX

  @article{NicodemeSalvyFlajolet2002,
    author = {Nicod{\`e}me, Pierre and Salvy, Bruno and Flajolet, Philippe},
    doi = {10.1016/S0304-3975(01)00264-X},
    journal = {Theoretical Computer Science},
    number = {2},
    pages = {593--618},
    title = {Motif Statistics},
    volume = {287},
    year = {2002}
  }
  

  Abstract

  We present a complete analysis of the statistics of number of occurrences of a regular expression pattern in a random text. This covers “motifs” widely used in computational biology. Our approach is based on: (i) classical constructive results in automata and formal language theory; (ii) analytic combinatorics that is used for deriving asymptotic properties from generating functions; (iii) computer algebra in order to determine generating functions explicitly, analyse generating functions and extract coefficients efficiently. We provide constructions for overlapping or non-overlapping matches of a regular expression. A companion implementation produces: multivariate generating functions for the statistics under study; a fast computation of their Taylor coefficients which yields exact values of the moments with typical application to random texts of size 30,000; precise asymptotic formulæ that allow predictions in texts of arbitrarily large sizes. Our implementation was tested by comparing predictions of the number of occurrences of motifs against the 7 megabytes amino acid database Procite. We handled more than 88% of the standard collection of Prodom motifs with our programs. Such comparisons help detect which motifs are observed in real biological data more or less frequently than theoretically predicted.

2001

• M. Giusti, G. Lecerf, and B. Salvy, “A Gröbner Free Alternative for Polynomial System Solving,” Journal of Complexity, vol. 17, no. 1, pp. 154–211, Mar. 2001.
  doi BibTeX

  @article{GiustiLecerfSalvy2001,
    author = {Giusti, Marc and Lecerf, Gr{\'e}goire and Salvy, Bruno},
    doi = {10.1006/jcom.2000.0571},
    journal = {Journal of Complexity},
    month = mar,
    number = {1},
    pages = {154--211},
    title = {A {G}r{\"o}bner Free Alternative for Polynomial System Solving},
    volume = {17},
    year = {2001}
  }
  

  Abstract

  Given a system of polynomial equations and inequations with coefficients in the field of rational numbers, we show how to compute a geometric resolution of the set of common roots of the system over the field of complex numbers. A geometric resolution consists of a primitive element of the algebraic extension defined by the set of roots, its minimal polynomial, and the parametrizations of the coordinates. Such a representation of the solutions has a long history which goes back to Leopold Kronecker and has been revisited many times in computer algebra. We introduce a new generation of probabilistic algorithms where all the computations use only univariate or bivariate polynomials. We give a new codification of the set of solutions of a positive dimensional algebraic variety relying on a new global version of Newton’s iterator. Roughly speaking the complexity of our algorithm is polynomial in some kind of degree of the system, in its height, and linear in the complexity of evaluation of the system. We present our implementation in the Magma system which is called Kronecker in homage to his method for solving systems of polynomial equations. We show that the theoretical complexity of our algorithm is well reflected in practice and we exhibit some cases for which our program is more efficient than the other available software.

• L. Meunier and B. Salvy, “Automatically Generated Encyclopedia of Special Functions,” in Mathematical Knowledge Management, 2001.
  PDF BibTeX

  @inproceedings{MeunierSalvy2001,
    author = {Meunier, Ludovic and Salvy, Bruno},
    booktitle = {Mathematical Knowledge Management},
    title = {Automatically Generated Encyclopedia of Special Functions},
    url = {http://www.risc.uni-linz.ac.at/about/conferences/MKM2001/Proceedings/printed/meunier.ps},
    year = {2001}
  }
  

  Abstract

  We present our on-going work on creating an automatically generated encyclopedia of special functions. The aim is to exploit recent progress in computer algebra in order to synthesize web pages on special functions and provide some level of interactivity.

• B. Salvy, “Even-Odd Set Partitions, Saddle-Point Method and Wyman Admissibility,” Institut National de Recherche en Informatique et en Automatique, Research Report 4201, 2001.
  BibTeX

  @techreport{Salvy2001,
    author = {Salvy, Bruno},
    institution = {Institut National de Recherche en Informatique et en Automatique},
    number = {4201},
    title = {Even-Odd Set Partitions, Saddle-Point Method and {W}yman Admissibility},
    type = {Research Report},
    year = {2001}
  }
  

2000

• M. Giusti, K. Hägele, G. Lecerf, J. Marchand, and B. Salvy, “Computing the Dimension of a Projective Variety: the Projective Noether Maple Package,” Journal of Symbolic Computation, vol. 30, no. 3, pp. 291–307, Sep. 2000.
  doi BibTeX

  @article{GiustiHageleLecerfMarchandSalvy2000,
    author = {Giusti, Marc and H{\"a}gele, Klemens and Lecerf, Gr{\'e}goire and Marchand, Jo{\"e}l and Salvy, Bruno},
    doi = {10.1006/jsco.2000.0369},
    journal = {Journal of Symbolic Computation},
    month = sep,
    number = {3},
    pages = {291--307},
    title = {Computing the Dimension of a Projective Variety: the Projective {N}oether {M}aple Package},
    volume = {30},
    year = {2000}
  }
  

  Abstract

  Recent theoretical advances in elimination theory use straight-line programs as a data structure to represent multivariate polynomials. We present here the Projective Noether Package which is a Maple implementation of one of these new algorithms, yielding as a byproduct a computation of the dimension of a projective variety. Comparative results on benchmarks for time and space of several families of multivariate polynomial equation systems are given and we point out both weaknesses and advantages of different approaches.

1999

• P. Nicodème, B. Salvy, and P. Flajolet, “Motif Statistics,” in Algorithms – ESA’99, 1999, no. 1643, pp. 194–211.
  PDF doi BibTeX

  @inproceedings{NicodemeSalvyFlajolet1999,
    author = {Nicod{\`e}me, Pierre and Salvy, Bruno and Flajolet, Philippe},
    booktitle = {Algorithms -- ESA'99},
    doi = {10.1007/3-540-48481-7_18},
    editor = {Nesetril, Jaroslav},
    number = {1643},
    pages = {194--211},
    series = {Lecture Notes in Computer Science},
    title = {Motif Statistics},
    url = {http://www.springerlink.com/link.asp?id=kn33ur4g65qcgyhg},
    year = {1999}
  }
  

  Abstract

  We present a complete analysis of the statistics of number of occurrences of a regular expression pattern in a random text. This covers “motifs” widely used in computational biology. Our approach is based on: \em (i)\/ a constructive approach to classical results in theoretical computer science (automata and formal language theory), in particular, the rationality of generating functions of regular languages; \em (ii)\/ analytic combinatorics that is used for deriving asymptotic properties from generating functions; \em (iii)\/ computer algebra for determining generating functions explicitly, analysing generating functions and extracting coefficients efficiently. We provide constructions for overlapping or non-overlapping matches of a regular expression. A companion implementation produces multivariate generating functions for the statistics under study. A fast computation of Taylor coefficients of the generating functions then yields exact values of the moments with typical application to random texts of size 30,000 while precise symptotic formulæ allow predictions in texts of arbitrarily large sizes. Our implementation was tested by comparing predictions of the number of occurrences of motifs against the 7 megabytes amino acid database \sc Prodom. % consensus. We handled more than 88% of the standard collection of \sc Prosite motifs with our programs. Such comparisons help detect which motifs are observed in real biological data more or less frequently than theoretically predicted.

• B. Salvy and J. Shackell, “Symbolic Asymptotics: Multiseries of Inverse Functions,” Journal of Symbolic Computation, vol. 27, no. 6, pp. 543–563, 1999.
  doi BibTeX

  @article{SalvyShackell1999,
    author = {Salvy, Bruno and Shackell, John},
    doi = {10.1006/jsco.1999.0281},
    journal = {Journal of Symbolic Computation},
    month = {juin},
    number = {6},
    pages = {543--563},
    title = {Symbolic Asymptotics: Multiseries of Inverse Functions},
    volume = {27},
    year = {1999}
  }
  

  Abstract

  We give an algorithm to compute an asymptotic expansion of multiseries type for the inverse of any given exp-log function. An example of the use of this algorithm to compute asymptotic expansions in combinatorics via the saddle-point method is then treated in detail.

1998

• F. Chyzak and B. Salvy, “Non-commutative Elimination in Ore Algebras Proves Multivariate Holonomic Identities,” Journal of Symbolic Computation, vol. 26, no. 2, pp. 187–227, 1998.
  doi BibTeX

  @article{ChyzakSalvy1998,
    author = {Chyzak, Fr{\'e}d{\'e}ric and Salvy, Bruno},
    doi = {10.1006/jsco.1998.0207},
    journal = {Journal of Symbolic Computation},
    month = {ao{\^u}t},
    number = {2},
    pages = {187--227},
    title = {Non-commutative Elimination in {O}re Algebras Proves Multivariate Holonomic Identities},
    volume = {26},
    year = {1998}
  }
  

  Abstract

  Many computations involving special functions, combinatorial sequences or theirq-analogues can be performed using linear operators and simple arguments on the dimension of related vector spaces. In this article, we develop a theory of -finite sequences and functions which provides a unified framework to express algorithms for computing sums and integrals and for the proof or discovery of multivariate identities. This approach is vindicated by an implementation.

• P. Flajolet and B. Salvy, “Euler Sums and Contour Integral Representations,” Experimental Mathematics, vol. 7, no. 1, pp. 15–35, 1998.
  PDF BibTeX

  @article{FlajoletSalvy1998,
    author = {Flajolet, Philippe and Salvy, Bruno},
    journal = {Experimental Mathematics},
    number = {1},
    pages = {15--35},
    title = {Euler Sums and Contour Integral Representations},
    url = {http://www.math.ethz.ch/EMIS/journals/EM/restricted/7/7.1/flajolet.ps},
    volume = {7},
    year = {1998}
  }
  

  Abstract

  This paper develops an approach to the evaluation of Euler sums that involve harmonic numbers, either linearly or nonlinearly. We give explicit formulæ for several classes of Euler sums in terms of Riemann zeta values. The approach is based on simple contour integral representations and residue computations.

• B. Salvy and J. Shackell, “Symbolic Asymptotics: Functions of Two Variables, Implicit Functions,” Journal of Symbolic Computation, vol. 25, no. 3, pp. 329–349, Mar. 1998.
  doi BibTeX

  @article{SalvyShackell1998,
    author = {Salvy, Bruno and Shackell, John},
    doi = {10.1006/jsco.1997.0179},
    journal = {Journal of Symbolic Computation},
    month = mar,
    number = {3},
    pages = {329--349},
    title = {Symbolic Asymptotics: Functions of Two Variables, Implicit Functions},
    volume = {25},
    year = {1998}
  }
  

  Abstract

  A number of recent papers have been concerned with algorithms to decide the limiting behaviour of functions of a single variable. Here we make a corresponding study of a class of functions of two variables, namely the exp-log functions. As in the one-variable case, we need to make certain assumptions regarding the handling of constants. Two of the main tools in the one-variable case are Hardy fields and nested forms. Here, we show how to compute some asymptotic estimates for two-variable exp-log functions. This method is then used to give an algorithm for computing the nested forms of real implicit functions.

1997

• P. Flajolet and B. Salvy, “The SIGSAM Challenges: Symbolic Asymptotics in Practice,” SIGSAM Bulletin, vol. 31, no. 4, pp. 36–47, Dec. 1997.
  PDF from ACM (free) doi BibTeX

  @article{FlajoletSalvy1997,
    author = {Flajolet, Philippe and Salvy, Bruno},
    doi = {10.1145/274888.274890},
    journal = {SIGSAM Bulletin},
    month = dec,
    number = {4},
    pages = {36--47},
    title = {The {S}IGSAM Challenges: Symbolic Asymptotics in Practice},
    url = {http://dl.acm.org/authorize?N02901},
    volume = {31},
    year = {1997}
  }
  

  Abstract

  We present answers to 5 out of 10 of the “Problems, Puzzles, Challenges” proposed by G. J. Fee and M. B. Monagan in the March 1997 issue of the Sigsam Bulletin. In all cases, the answer to a seemingly numerical problem is obtained via series expansions and asymptotic methods. This illustrates more generally the crucial role played in the presence of singular behaviours by symbolic asymptotics as a bridge between symbolic computation and numerical computations. All our computations have been performed using MapleV.4 on a Dec Alpha (255/233). The timings indicated correspond to executions on this machine.

• L. Habsieger and B. Salvy, “On Integer Chebyshev Polynomials,” Mathematics of Computation, vol. 66, no. 218, pp. 763–770, 1997.
  PDF doi BibTeX

  @article{HabsiegerSalvy1997,
    author = {Habsieger, Laurent and Salvy, Bruno},
    doi = {10.1090/S0025-5718-97-00829-6},
    journal = {Mathematics of Computation},
    month = {avril},
    number = {218},
    pages = {763--770},
    title = {On Integer {C}hebyshev Polynomials},
    url = {http://www.ams.org/mcom/1997-66-218/S0025-5718-97-00829-6/S0025-5718-97-00829-6.pdf},
    volume = {66},
    year = {1997}
  }
  

  Abstract

  We are concerned with the problem of minimizing the supremum norm on [0,1] of a nonzero polynomial of degree at most n with integer coefficients. We use the structure of such polynomials to derive an efficient algorithm for computing them. We give a table of these polynomials for degree up to 75 and use a value from this table to answer an open problem and improve a lower bound due to Borwein and Erdelyi (1995).

1996

• X. Gourdon and B. Salvy, “Effective asymptotics of linear recurrences with rational coefficients,” Discrete Mathematics, vol. 153, no. 1–3, pp. 145–163, 1996.
  doi BibTeX

  @article{GourdonSalvy1996,
    author = {Gourdon, Xavier and Salvy, Bruno},
    doi = {10.1016/0012-365X(95)00133-H},
    journal = {Discrete Mathematics},
    number = {1--3},
    pages = {145--163},
    title = {Effective asymptotics of linear recurrences with rational coefficients},
    volume = {153},
    year = {1996}
  }
  

  Abstract

  We give algorithms to compute the asymptotic expansion of solutions of linear recurrences with rational coefficients and rational initial conditions in polynomial time in the order of the recurrence.

• D. Richardson, B. Salvy, J. Shackell, and J. Van der Hoeven, “Asymptotic Expansions of exp-log Functions,” in Symbolic and Algebraic Computation, New York, 1996, pp. 309–313.
  PDF from ACM (free) doi BibTeX

  @inproceedings{RichardsonSalvyShackellVan-der-Hoeven1996,
    address = {New York},
    author = {Richardson, Dan and Salvy, Bruno and Shackell, John and Van der Hoeven, Joris},
    booktitle = {Symbolic and Algebraic Computation},
    doi = {10.1145/236869.237089},
    editor = {Lakshman, Y. N.},
    note = {Proceedings I{SSAC}'96, Z{\"u}rich, July 1996},
    pages = {309--313},
    publisher = {ACM Press},
    title = {Asymptotic Expansions of exp-log Functions},
    url = {http://dl.acm.org/authorize?N02902},
    year = {1996}
  }
  

  Abstract

  We give an algorithm to compute asymptotic expansions of exp-log functions. This algorithm automatically computes the necessary asymptotic scale and does not suffer from problems of indefinite cancellation. In particular, an asymptotic equivalent can always be computed for a given exp-log function.

  
  Proceedings ISSAC’96, Zürich, July 1996

1995

• P. Dumas and B. Salvy, “Maple and the Putnam Competition,” The Maple Technical Newsletter, vol. 2, no. 2, pp. 63–68, 1995.
  BibTeX

  @article{DumasSalvy1995,
    author = {Dumas, Philippe and Salvy, Bruno},
    journal = {The Maple Technical Newsletter},
    number = {2},
    pages = {63--68},
    title = {Maple and the {P}utnam Competition},
    volume = {2},
    year = {1995}
  }
  

• P. Flajolet, G. Labelle, L. Laforest, and B. Salvy, “Hypergeometrics and the cost structure of quadtrees,” Random Structures & Algorithms, vol. 7, no. 2, pp. 117–144, 1995.
  doi BibTeX

  @article{FlajoletLabelleLaforestSalvy1995,
    author = {Flajolet, Philippe and Labelle, Gilbert and Laforest, Louise and Salvy, Bruno},
    doi = {10.1002/rsa.3240070203},
    journal = {Random Structures & Algorithms},
    number = {2},
    pages = {117--144},
    title = {Hypergeometrics and the cost structure of quadtrees},
    volume = {7},
    year = {1995}
  }
  

  Abstract

  Several characteristic parameters of randomly grown quadtrees of any dimension are analysed. Additive parameters have expectations whose generating functions are expressible in terms of generalized hypergeometric functions. A complex asymptotic process based on singularity analysis and integral representations akin to Mellin transforms leads to explicit values for various structure constants related to path length, retrieval costs, and storage occupation.

• P. Flajolet and B. Salvy, “Computer Algebra Libraries for Combinatorial Structures,” Journal of Symbolic Computation, vol. 20, no. 5-6, pp. 653–671, 1995.
  doi BibTeX

  @article{FlajoletSalvy1995,
    author = {Flajolet, Philippe and Salvy, Bruno},
    doi = {10.1006/jsco.1995.1070},
    journal = {Journal of Symbolic Computation},
    number = {5-6},
    pages = {653--671},
    title = {Computer Algebra Libraries for Combinatorial Structures},
    volume = {20},
    year = {1995}
  }
  

  Abstract

  This paper introduces the framework of decomposable combinatorial structures and their traversal algorithms. A combinatorial type is decomposable if it admits a specification in terms of unions, products, sequences, sets, and cycles, either in the labelled or in the unlabelled context. Many properties of decomposable structures are decidable. Generating function equations, counting sequences, and random generation algorithms can be compiled from specifications. Asymptotic properties can be determined automatically for a reasonably large subclass. Maple libraries that implement such decision procedures are briefly surveyed (LUO, combstruct, equivalent). In addition, libraries for manipulating holonomic sequences and functions are presented (gfun, Mgfun).

• C. Gomez, B. Salvy, and P. Zimmermann, Calcul formel : mode d’emploi. Exemples en Maple. Masson, 1995.
  BibTeX

  @book{GomezSalvyZimmermann1995,
    author = {Gomez, Claude and Salvy, Bruno and Zimmermann, Paul},
    publisher = {Masson},
    title = {Calcul formel : mode d'emploi. {E}xemples en {M}aple},
    year = {1995}
  }
  

• S. P. Lipshitz, T. C. Scott, and B. Salvy, “On the Acoustic Impedance of Baffled Strip Radiators,” Journal of the Audio Engineering Society, vol. 43, no. 7/8, pp. 573–580, Jul. 1995.
  BibTeX

  @article{LipshitzScottSalvy1995,
    author = {Lipshitz, Stanley P. and Scott, Tony C. and Salvy, Bruno},
    journal = {Journal of the Audio Engineering Society},
    month = jul,
    number = {7/8},
    pages = {573--580},
    title = {On the Acoustic Impedance of Baffled Strip Radiators},
    volume = {43},
    year = {1995}
  }
  

  Abstract

  There appears to be no available expression for the reactive (mass) term in the acoustic impedance of long baffled strip radiators, and the literature contains contradictory graphical data on both the real and the imaginary parts. Reliable data are important for the proper electroacoustic design of ribbon transducers, and also potentially for other long, narrow, low-mass planar radiators, both electrostatic and electrqmagnetic. Analytical expressions and graphical data are presented for the resistive and reactive parts of the acoustic load on an infinite baffled strip radiator.

• B. Salvy and S. Y. Slavyanov, “A Combinatorial Problem in the Classification of Second-Order Linear ODE’s,” Institut National de Recherche en Informatique et en Automatique, Research Report 2600, 1995.
  BibTeX

  @techreport{SalvySlavyanov1995,
    author = {Salvy, Bruno and Slavyanov, Sergey Yu.},
    institution = {Institut National de Recherche en Informatique et en Automatique},
    number = {2600},
    title = {A Combinatorial Problem in the Classification of Second-Order Linear ODE's},
    type = {Research Report},
    year = {1995}
  }
  

• J. Shackell and B. Salvy, “Asymptotic Forms and Algebraic Differential Equations,” Journal of Symbolic Computation, vol. 20, no. 2, pp. 169–177, 1995.
  doi BibTeX

  @article{ShackellSalvy1995,
    author = {Shackell, John and Salvy, Bruno},
    doi = {10.1006/jsco.1995.1044},
    journal = {Journal of Symbolic Computation},
    number = {2},
    pages = {169--177},
    title = {Asymptotic Forms and Algebraic Differential Equations},
    volume = {20},
    year = {1995}
  }
  

  Abstract

  We analyse the complexity of a simple algorithm for computing asymptotic solutions of algebraic differential equations. This analysis is based on a computation of the number of possible asymptotic monomials of a certain order, and on the study of the growth of this number as the order of the equation grows.

1994

• B. Salvy, “Fast Computation of Some Asymptotic Functional Inverses,” Journal of Symbolic Computation, vol. 17, no. 3, pp. 227–236, 1994.
  doi BibTeX

  @article{Salvy1994,
    author = {Salvy, Bruno},
    doi = {10.1006/jsco.1994.1014},
    journal = {Journal of Symbolic Computation},
    number = {3},
    pages = {227--236},
    title = {Fast Computation of Some Asymptotic Functional Inverses},
    volume = {17},
    year = {1994}
  }
  

  Abstract

  G. Robin showed that in several naturally occurring asymptotic expansions of the form \[y(x)≈\sum_n\ge0P_n(\log\log x)\over\log^n\!x,\]the polynomials P_n satisfy a simple relation \[P’_n+1=aP’_n+(bn+c)P_n.\]These results do not give a way to compute these polynomials, since the constant term remains undetermined by this equation. In this note, we give a new derivation of some of Robin’s results, and show how the constant terms can be computed with only manipulations of one-variable formal power series. From there, all the P_n can be computed efficiently.

• B. Salvy and P. Zimmermann, “Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable,” ACM Transactions on Mathematical Software, vol. 20, no. 2, pp. 163–177, 1994.
  PDF from ACM (free) doi BibTeX

  @article{SalvyZimmermann1994,
    author = {Salvy, Bruno and Zimmermann, Paul},
    doi = {10.1145/178365.178368},
    journal = {ACM Transactions on Mathematical Software},
    number = {2},
    owner = {bs},
    pages = {163--177},
    title = {Gfun: a {M}aple package for the manipulation of generating and holonomic functions in one variable},
    url = {http://dl.acm.org/authorize?N02903},
    volume = {20},
    year = {1994}
  }
  

  Abstract

  We describe the GFUN package which contains functions for manipulating sequences, linear recurrences, or differential equations and generating functions of various types. This article is intended both as an elementary introduction to the subject and as a reference manual for the package.

1993

• M. Bronstein and B. Salvy, “Full Partial Fraction Decomposition of Rational Functions,” in ISSAC’93, New York, 1993, pp. 157–160.
  PDF from ACM (free) doi BibTeX

  @inproceedings{BronsteinSalvy1993,
    address = {New York},
    author = {Bronstein, Manuel and Salvy, Bruno},
    booktitle = {I{SSAC}'93},
    doi = {10.1145/164081.164114},
    editor = {Bronstein, Manuel},
    month = jul,
    pages = {157--160},
    publisher = {ACM Press},
    title = {Full Partial Fraction Decomposition of Rational Functions},
    url = {http://dl.acm.org/authorize?N02915},
    year = {1993}
  }
  

  Abstract

  We describe a rational algorithm that computes the full partial fraction expansion of a rational function over the algebraic closure of its field of definition. The algorithm uses only gcd operations over the initial field but the resulting decomposition is expressed with linear denominators. We give examples from its Axiom and Maple implementations.

• P. Flajolet, X. Gourdon, and B. Salvy, “Sur une famille de polynômes issus de l’analyse numérique,” Gazette des Mathématiciens, vol. 55, pp. 67–78, Jan. 1993.
  BibTeX

  @article{FlajoletGourdonSalvy1993,
    author = {Flajolet, Philippe and Gourdon, Xavier and Salvy, Bruno},
    journal = {Gazette des Math{\'e}maticiens},
    month = jan,
    pages = {67--78},
    title = {Sur une famille de polyn{\^o}mes issus de l'analyse num{\'e}rique},
    volume = {55},
    year = {1993}
  }
  

• P. Flajolet and B. Salvy, “A Finite Sum of Products of Binomial Coefficients,” SIAM Review, vol. 35, no. 4, pp. 645–646, 1993.
  PDF doi BibTeX

  @article{FlajoletSalvy1993,
    author = {Flajolet, Philippe and Salvy, Bruno},
    doi = {10.1137/1035147},
    journal = {SIAM Review},
    number = {4},
    pages = {645--646},
    title = {A Finite Sum of Products of Binomial Coefficients},
    url = {http://epubs.siam.org/doi/pdf/10.1137/1035147},
    volume = {35},
    year = {1993}
  }
  

• X. Gourdon and B. Salvy, “Asymptotics of linear recurrences with rational coefficients,” in Formal Power Series and Algebraic Combinatorics, 1993, pp. 253–266.
  BibTeX

  @inproceedings{GourdonSalvy1993,
    author = {Gourdon, Xavier and Salvy, Bruno},
    booktitle = {Formal Power Series and Algebraic Combinatorics},
    editor = {Barlotti, A. and Delest, M. and Pinzani, R.},
    pages = {253--266},
    title = {Asymptotics of linear recurrences with rational coefficients},
    year = {1993}
  }
  

  Abstract

  We give algorithms to compute the asymptotic expansion of solutions of linear recurrences with rational coefficients and initial conditions in polynomial time in the order of the recurrence.

• X. Gourdon and B. Salvy, “Computing one million digits of \sqrt2,” The Maple Technical Newsletter, vol. 10, pp. 66–71, 1993.
  BibTeX

  @article{GourdonSalvy1993a,
    author = {Gourdon, Xavier and Salvy, Bruno},
    journal = {The Maple Technical Newsletter},
    pages = {66--71},
    title = {Computing one million digits of $\sqrt{2}$},
    volume = {10},
    year = {1993}
  }
  

  Abstract

  We describe how the knowledge of Maple’s internal data structure can be used to compute the first million digits of \sqrt2 efficiently.

• M. Petkovšek and B. Salvy, “Finding all hypergeometric solutions of linear differential equations,” in ISSAC’93, New York, 1993, pp. 27–33.
  PDF from ACM (free) doi BibTeX

  @inproceedings{PetkovsekSalvy1993,
    address = {New York},
    author = {Petkov{\v s}ek, Marko and Salvy, Bruno},
    booktitle = {I{SSAC}'93},
    doi = {10.1145/164081.164087},
    editor = {Bronstein, Manuel},
    month = jul,
    pages = {27--33},
    publisher = {ACM Press},
    title = {Finding all hypergeometric solutions of linear differential equations},
    url = {http://dl.acm.org/authorize?N02904},
    year = {1993}
  }
  

  Abstract

  Hypergeometric sequences are such that the quotient of two successive terms is a fixed rational function of the index. We give a generalization of M. Petkovšek’s algorithm to find all hypergeometric sequence solutions of linear recurrences, and we describe a program to find all hypergeometric functions that solve a linear differential equation.

• B. Salvy, “Efficient programming in Maple: a case study,” SIGSAM Bulletin, vol. 27, no. 2, pp. 1–12, Apr. 1993.
  PDF from ACM (free) doi BibTeX

  @article{Salvy1993,
    author = {Salvy, Bruno},
    doi = {10.1145/165474.165477},
    journal = {SIGSAM Bulletin},
    month = apr,
    number = {2},
    pages = {1--12},
    title = {Efficient programming in {M}aple: a case study},
    url = {http://dl.acm.org/authorize?N02916},
    volume = {27},
    year = {1993}
  }
  

  Abstract

  Studying the computation of orbits of some given group acting on a set, we show how successive refinements of a simple program provide a speedup factor of up to 200. The initial program cannot solve the problem at all, it is first converted into a program which needs one c.p.u. week and after all the optimizations have been performed, the computation takes only four hours. Although the problem is specific, we shall show that many of the optimizations we use are of interest for other problems as well.

1992

• F. Bergeron, P. Flajolet, and B. Salvy, “Varieties of Increasing Trees,” in CAAP’92, 1992, vol. 581, pp. 24–48.
  doi BibTeX

  @inproceedings{BergeronFlajoletSalvy1992,
    author = {Bergeron, Fran{\c c}ois and Flajolet, Philippe and Salvy, Bruno},
    booktitle = {CAAP'92},
    doi = {10.1007/3-540-55251-0_2},
    editor = {Raoult, J.-C.},
    pages = {24--48},
    series = {Lecture Notes in Computer Science},
    title = {Varieties of Increasing Trees},
    volume = {581},
    year = {1992}
  }
  

  Abstract

  An increasing tree is a labelled rooted tree in which labels along any branch from the root go in increasing order. Under various guises, such trees have surfaced as tree representations of permutations, as data structures in computer science, and as probabilistic models in diverse applications. We present a unified generating function approach to the enumeration of parameters on such trees. The counting generating functions for several basic parameters are shown to be related to a simple ordinary differential equation $ d\over dzY(z)=φ(Y(z)), which is non linear and autonomous. Singularity analysis applied to the intervening generating functions then permits to analyze asymptotically a number of parameters of the trees, like: root degree, number of leaves, path length, and level of nodes. In this way it is found that various models share common features: path length is O(n\log n)$, the distributions of node levels and number of leaves are asymptotically normal, etc.

• B. Salvy, “General Asymptotic Scales and Computer Algebra,” in Asymptotic and Numerical Methods for Partial Differential Equations, Critical Parameters and Domain Decomposition, 1992.
  BibTeX

  @inproceedings{Salvy1992,
    author = {Salvy, Bruno},
    booktitle = {Asymptotic and Numerical Methods for Partial Differential Equations, Critical Parameters and Domain Decomposition},
    editor = {Kaper, H. and Garbey, M.},
    publisher = {Kluwer Academic Publishers},
    title = {General Asymptotic Scales and Computer Algebra},
    year = {1992}
  }
  

  Abstract

  In many natural applications, one encounters asymptotic expansions of a form more complicated than mere Puiseux series. Existing computer algebra systems lack good algorithms for handling such asymptotic expansions. We present tools that permit the representation and automatic handling of general exp-log asymptotic expansions.

• B. Salvy and J. Shackell, “Asymptotic expansions of functional inverses,” in Symbolic and Algebraic Computation, New York, 1992, pp. 130–137.
  PDF from ACM (free) doi BibTeX

  @inproceedings{SalvyShackell1992,
    address = {New York},
    author = {Salvy, Bruno and Shackell, John},
    booktitle = {Symbolic and Algebraic Computation},
    doi = {10.1145/143242.143292},
    editor = {Wang, Paul S.},
    note = {Proceedings of I{SSAC}'92, Berkeley, July 1992.},
    pages = {130--137},
    publisher = {ACM Press},
    title = {Asymptotic expansions of functional inverses},
    url = {http://dl.acm.org/authorize?N02917},
    year = {1992}
  }
  

  Abstract

  We study the automatic computation of asymptotic expansions of functional inverses. Based on previous work on asymptotic expansions, we give an algorithm which computes Hardy-field solutions of equations f(y)=x, with f belonging to a large class of functions.

  
  Proceedings of ISSAC’92, Berkeley, July 1992.

1991

• P. Flajolet, B. Salvy, and P. Zimmermann, “Automatic Average-case Analysis of Algorithms,” Theoretical Computer Science, vol. 79, no. 1, pp. 37–109, 1991.
  doi BibTeX

  @article{FlajoletSalvyZimmermann1991,
    author = {Flajolet, Philippe and Salvy, Bruno and Zimmermann, Paul},
    doi = {10.1016/0304-3975(91)90145-R},
    journal = {Theoretical Computer Science},
    month = {f{\'e}vrier},
    number = {1},
    pages = {37--109},
    title = {Automatic Average-case Analysis of Algorithms},
    volume = {79},
    year = {1991}
  }
  

  Abstract

  Many probabilistic properties of elementary discrete combinatorial structures of interest for the average-case analysis of algorithms prove to be decidable. This paper presents a general framework in which such decision procedures can be developed. It is based on a combination of generating function techniques for counting, and complex analysis techniques for asymptotic estimations. We expose here the theory of exact analysis in terms of generating functions for four different domains: the iterative/recursive and unlabelled/labelled data type domains. We then present some major components of the associated asymptotic theory and exhibit a class of naturally arising functions that can be automatically analyzed. A fair fragment of this theory is also incorporated into a system called Lambda-Upsilon-Omega. In this way, using computer algebra, one can produce automatically non-trivial average-case analyses of algorithms operating over a variety of “decomposable” combinatorial structures. At a fundamental level, this paper is part of a global attempt at understanding why so many elementary combinatorial problems tend to have elementary asymptotic solutions. In several cases, it proves possible to relate entire classes of elementary combinatorial problems whose structure is well defined with classes of elementary “special” functions and classes of asymptotic forms relative to counting, probabilities, or average-case complexity.

• B. Salvy, “Examples of automatic asymptotic expansions,” SIGSAM Bulletin, vol. 25, no. 2, pp. 4–17, Apr. 1991.
  PDF from ACM (free) doi BibTeX

  @article{Salvy1991,
    author = {Salvy, B.},
    doi = {10.1145/122520.122521},
    journal = {SIGSAM Bulletin},
    month = apr,
    number = {2},
    pages = {4--17},
    title = {Examples of automatic asymptotic expansions},
    url = {http://dl.acm.org/authorize?N02918},
    volume = {25},
    year = {1991}
  }
  

  Abstract

  We describe the current state of a Maple library, gdev, designed to perform asymptotic expansions for a large class of expressions. Many examples are provided, along with a short sketch of the underlying principles. At the time when this report is written, a striking feature of these examples is that none of them can be computed directly with any of today’s most widespread symbolic computation systems (Macsyma (Sun Release 309.6), Mathematica (Version 1.2, beta test), Maple (Version 4.3) or Scratchpad II (Version 4J)).

• B. Salvy, “Three ways to get Stirling’s formula in Maple,” The Maple Technical Newsletter, vol. 5, pp. 32–42, 1991.
  BibTeX

  @article{Salvy1991a,
    author = {Salvy, Bruno},
    journal = {The Maple Technical Newsletter},
    pages = {32--42},
    title = {Three ways to get {S}tirling's formula in {M}aple},
    volume = {5},
    year = {1991}
  }
  

• B. Salvy, “Asymptotique automatique et fonctions génératrices,” Thèse de Doctorat, École polytechnique, 1991.
  BibTeX

  @phdthesis{Salvy1991b,
    author = {Salvy, Bruno},
    school = {{\'E}cole polytechnique},
    title = {Asymptotique automatique et fonctions g{\'e}n{\'e}ratrices},
    type = {Th{\`e}se de Doctorat},
    year = {1991}
  }
  

1989

• P. Flajolet, B. Salvy, and P. Zimmermann, “Lambda-Upsilon-Omega: An Assistant Algorithms Analyzer,” in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 1989, vol. 357, pp. 201–212.
  doi BibTeX

  @inproceedings{FlajoletSalvyZimmermann1989,
    author = {Flajolet, P. and Salvy, B. and Zimmermann, P.},
    booktitle = {Applied Algebra, Algebraic Algorithms and Error-Correcting Codes},
    doi = {10.1007/3-540-51083-4_60},
    editor = {Mora, T.},
    pages = {201--212},
    series = {Lecture Notes in Computer Science},
    title = {{L}ambda-{U}psilon-{O}mega: An Assistant Algorithms Analyzer},
    volume = {357},
    year = {1989}
  }
  

  Abstract

  Lambda-Upsilon-Omega, LUO, is a system designed to perform automatic analysis of well-defined classes of algorithms operating over decomposable data structures. It consists of an Algebraic Analyzer System that compiles algorithms specifications into generating functions of average costs, and an Analytic Analyzer System that extracts asymptotic informations on coefficients of generating functions. The algebraic part relies on recent methodologies in combinatorial analysis based on systematic correspondences between structural type definitions and counting generating functions. The analytic part makes use of partly classical and partly new correspondences between singularities of analytic functions and the growth of their Taylor coefficients. The current version LUO0 of LUO implements as basic data types, term trees as encountered in symbolic algebra systems. The analytic analyzer can treat large classes of functions with explicit expressions. In this way, LUO0 can generate in the current stage about a dozen non-trivial average case analyses of algorithms like: formal differentiation, some algebraic simplification and matching algorithms. Its analytic analyzer can determine asymptotic expansions for large classes of generating functions arising in the analysis of algorithms. The outline of a design for a full system is also discussed here. The long term goal is to include a fairly rich set of data structuring mechanisms including some general recursive type definitions, and have the analytic analyzer treat wide classes of functional equations as may be encountered in combinatorial analysis and the analysis of algorithms.

• P. Flajolet, B. Salvy, and P. Zimmermann, “Lambda-Upsilon-Omega: The 1989 CookBook,” Institut National de Recherche en Informatique et en Automatique, Research Report 1073, 1989.
  BibTeX

  @techreport{FlajoletSalvyZimmermann1989a,
    author = {Flajolet, P. and Salvy, B. and Zimmermann, P.},
    institution = {Institut National de Recherche en Informatique et en Automatique},
    number = {1073},
    title = {{L}ambda-{U}psilon-{O}mega: {T}he 1989 {C}ookBook},
    type = {Research Report},
    year = {1989}
  }
  

1988

• B. Salvy, “Fonctions génératrices et asymptotique automatique,” Université Paris XI, Rapport de DEA, 1988.
  BibTeX

  @techreport{Salvy1988,
    author = {Salvy, B.},
    institution = {Universit{\'e} Paris XI},
    title = {Fonctions g{\'e}n{\'e}ratrices et asymptotique automatique},
    type = {Rapport de {DEA}},
    year = {1988}
  }
  

1987

• B. Salvy, “Calcul automatique du développement asymptotique lorsque leur rang tend vers l’infini des coefficients des développements en série de Laurent de certaines fonctions génératrices,” École polytechnique, Rapport d’option, 1987.
  BibTeX

  @techreport{Salvy1987,
    author = {Salvy, B.},
    institution = {{\'E}cole polytechnique},
    title = {Calcul automatique du d{\'e}veloppement asymptotique lorsque leur rang tend vers l'infini des coefficients des d{\'e}veloppements en s{\'e}rie de {L}aurent de certaines fonctions g{\'e}n{\'e}ratrices},
    type = {Rapport d'option},
    year = {1987}
  }