I’m an Inria researcher in the AriC project, which is part of the LIP lab in ENS Lyon. I recently moved there after more than 20 years in the stimulating environment of the Algorithms project in Rocquencourt (near Paris). My field of research is computer algebra. It is the study of effective mathematics and their complexity: how much mathematics can be done by a computer, and how fast? In this area, I am mostly interested in applications to classical analysis (asymptotics, special functions) and combinatorics. See the menus “Software” and “Publications” for more information.
In August 2017, we finally published a book version of the notes of the course on efficient algorithms for computer algebra we have been giving for more than 10 years. Click on the cover to reach a page where you can download it for free or order an unexpensive paper version.
Analytic combinatorics in several variables aims at finding the asymptotic behavior of sequences of diagonal coefficients of multivariate analytic functions. The starting point of the computation is the determination of the set of minimal critical points of the set of singularities. These are points where this set comes closest to the origin. In the case of rational functions with nonnegative coefficients, this can be achieved efficiently.
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.
The three complex roots of the polynomial \(17x^3-9x^2-7x+8\), depicted on the picture, lie on two different circles, at distance smaller than 0.000015 and thus indistinguishable on the picture. More generally, only pessimistic bounds are known for the distance between absolute values of roots of polynomials with integer coefficients. It turns out however, that in the case of real roots, tight bounds can be given.
Y. Bugeaud, A. Dujella, T. Pejkovic, and B. Salvy, “Absolute real root separation,” American Mathematical Monthly, 2017.
The picture on the right, from the cover of a book by Kenneth Chan on ``Spacecraft collision probability’’, illustrates the quantity of debris orbiting around Earth and the importance of predicting collisions. We describe a method for the evaluation of the probability of such collisions using a closed form for the Laplace transform, an explicit recurrence for its Taylor coefficients and a technique to evaluate these in a numerically stable way. This method compares favorably to other existing techniques.
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. 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.
Multiple binomial sums turn out to be diagonals of rational power series. This can be made effective, leading to an integral representation from which a linear differential equation for the generating function can be derived and from there finally a linear recurrence for the sum. This is a very efficient approach that avoids the computation of a large certificate.
A. Bostan, P. Lairez, and B. Salvy, “Multiple binomial sums,” Journal of Symbolic Computation, vol. 80, pp. 351–386, 2017.
Definite integrals of rational functions in several variables provide elementary representations for a large number of special functions, or combinatorial sequences through their generating functions. These integrals satisfy linear differential equations from which a lot of information about them can be extracted easily. The computation of these integrals is a classical topic, going back at least to Émile Picard, with recent progress based on creative telescoping.
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. 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.
Continued fractions provide a sequence of approximations to a number or a function in the same way as series expansions or infinite products do. For a large number of special functions, these continued fractions have coefficients given by an explicit rational function of the index. To a large extent, these formulas can be discovered and proved by computer algebra.
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.
Diagonals of multivariate rational functions encode the enumeration sequences of many combinatorial sequences. In the bivariate case, these diagonals are algebraic power series and an alternative representation is by their minimal polynomial. Yet another possibility is to use a linear differential equation they satisfy. Precise estimates of the sizes of these equations and of the complexity of obtaining them can be computed, showing that the differential equation is generally a better choice.
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. A. Bostan, L. Dumont, and B. Salvy, “Algebraic Diagonals and Walks: Algorithms, Bounds, Complexity,” Journal of Symbolic Computation, vol. 83, pp. 68–92, 2017.
The full collection of my recent (and not so recent) papers is here.
46, allée d'Italie
69364 Lyon Cedex 07
phone: (+33) (0)4 72 72 80 09
My office is #374 on the 3rd floor.
Here are directions to get there.