Welcome

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.

Recent Work

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 [1].
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 bound can be given [2].
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.
See [3].
chan_cover2
multiplebinomialsums_vignette
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 [4].
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. See [5] for more, or [6] for a special class.
tore-cycles
vignette
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 [7].
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 [8, 9].
diagandwalks
  1. 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.
    arXiv:abs/1605.00402
    doi:10.1145/2930889.2930913
    [BibTeX] [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.

    @inproceedings{MelczerSalvy2016,
    Address = {New York, NY, USA},
    Arxiv = {abs/1605.00402},
    Author = {Melczer, Stephen and Salvy, Bruno},
    Booktitle = {I{SSAC}'16: Proceedings of the 2016 {ACM} International Symposium on Symbolic and Algebraic Computation},
    Date-Added = {2016-05-03 06:40:22 +0000},
    Date-Modified = {2016-05-03 06:42:46 +0000},
    Doi = {10.1145/2930889.2930913},
    Location = {Waterloo, Ontario, Canada},
    Numpages = {8},
    Publisher = {ACM},
    Title = {Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables},
    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.
    }}

  2. Y. Bugeaud, A. Dujella, T. Pejkovic, and B. Salvy, “Absolute real root separation,” arXiv 2016.
    arXiv:abs/1606.01131
    [BibTeX] [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.

    @techreport{BugeaudDujellaPejkovicSalvy2016,
    Arxiv = {abs/1606.01131},
    Author = {Bugeaud, Yann and Dujella, Andrej and Pejkovic, Tomislav and Salvy, Bruno},
    Date-Added = {2016-06-06 10:50:24 +0000},
    Date-Modified = {2016-06-06 10:52:55 +0000},
    Eprint = {1606.01131},
    Institution = {arXiv},
    Month = {06},
    Title = {Absolute real root separation},
    Year = {2016},
    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.},
    Bdsk-Url-1 = {http://arxiv.org/abs/1606.01131}}

  3. R. Serra, D. Arzelier, M. Joldes, J. 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, iss. 5, pp. 1009-1021, 2016.
    doi:10.2514/1.G001353
    [BibTeX] [Abstract] [Download PDF]
    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.

    @article{SerraArzelierJoldesLasserreRondepierreSalvy2016,
    Author = {Serra, Romain and Arzelier, Denis and Joldes, Mioara and Lasserre, Jean-Bernard and Rondepierre, Aude and Salvy, Bruno},
    Date-Added = {2015-11-10 13:06:06 +0000},
    Date-Modified = {2016-05-10 06:20:13 +0000},
    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.
    }
    }

  4. A. Bostan, P. Lairez, and B. Salvy, “Multiple binomial sums,” 2015.
    arXiv:abs/1510.07487
    [BibTeX] [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.

    @techreport{BostanLairezSalvy2015,
    Author = {Bostan, Alin and Lairez, Pierre and Salvy, Bruno},
    Date-Added = {2015-11-10 12:46:58 +0000},
    Date-Modified = {2015-11-10 12:50:54 +0000},
    Eprint = {1510.07487},
    arxiv = {abs/1510.07487},
    Month = {10},
    Title = {Multiple binomial sums},
    Year = {2015},
    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.}
    }

  5. 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.
    arXiv:abs/1301.4313
    doi:10.1145/2465506.2465935
    [BibTeX] [Abstract] [Download PDF]
    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.

    @inproceedings{BostanLairezSalvy2013,
    Arxiv = {abs/1301.4313},
    Author = {Bostan, Alin and Lairez, Pierre and Salvy, Bruno},
    Booktitle = {I{SSAC} '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation},
    Date-Added = {2013-03-12 15:59:09 +0000},
    Date-Modified = {2016-05-11 05:24:02 +0000},
    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.}
    }

  6. 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, New York, NY, USA, 2016.
    arXiv:abs/1605.05082
    doi:10.1145/2930889.2930907
    [BibTeX] [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.

    @inproceedings{BostanDumontSalvy2016,
    Address = {New York, NY, USA},
    Arxiv = {abs/1605.05082},
    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},
    Date-Added = {2016-05-19 05:48:47 +0000},
    Date-Modified = {2016-05-19 05:52:37 +0000},
    Doi = {10.1145/2930889.2930907},
    Publisher = {ACM},
    Title = {Efficient Algorithms for Mixed Creative Telescoping},
    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.
    }}

  7. 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:abs/1507.04203
    doi:10.1145/2755996.2756660
    [BibTeX] [Abstract] [Download PDF]
    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.

    @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},
    Date-Added = {2015-07-02 06:19:51 +0000},
    Date-Modified = {2016-05-10 06:28:11 +0000},
    Doi = {10.1145/2755996.2756660},
    Isbn = {978-1-4503-3435-8},
    Keywords = {continued fractions, p-recursive sequences, special functions},
    Url = {http://dl.acm.org/authorize?N02984},
    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},
    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.
    }
    }

  8. 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.
    doi:10.1145/2755996.2756663
    [BibTeX] [Abstract] [Download PDF]
    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$. 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.

    @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},
    Date-Added = {2015-07-02 06:14:59 +0000},
    Date-Modified = {2016-05-11 05:21:14 +0000},
    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 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$. 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.}
    }

  9. A. Bostan, L. Dumont, and B. Salvy, “Algebraic diagonals and walks: algorithms, bounds, complexity,” 2015.
    arXiv:abs/1510.04526
    [BibTeX] [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.

    @techreport{BostanDumontSalvy2015a,
    Author = {Bostan, Alin and Dumont, Louis and Salvy, Bruno},
    Date-Added = {2015-11-10 12:47:01 +0000},
    Date-Modified = {2015-11-10 12:51:27 +0000},
    Eprint = {1510.04526},
    Month = {10},
    Note = {This is an extended version of the I{SSAC}'15 article, with more precise results and more detailed proofs.},
    Title = {Algebraic Diagonals and Walks: Algorithms, Bounds, Complexity},
    arxiv = {abs/1510.04526},
    Year = {2015},
    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.}
    }

The full collection of my recent (and not so recent) papers is here.


Address

LIP – ENS Lyon
46, allée d’Italie
69364 Lyon Cedex 07
France

email: Firstname.Lastname@inria.fr
phone: (+33) (0)4 72 72 85 00

Visitors:
My office is #317
on the 3rd floor.
Here are directions to get there.