Welcome

BS-small 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

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 [1].
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 [2]. tan-cf
diagandwalks 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 [3, 4].
Gröbner bases are a standard tool in the manipulation and resolution of polynomial systems. Currently, the best known algorithm for their computation is Faugère’s F5 algorithm from 2002. By studying the structure of the matrices it constructs, it is possible to gain insight on the shape of a Gröbner basis in a generic situation, as well as bound the complexity of the algorithm [5] mat8
exc100 This is a walk of 100 steps in the quarter plane, starting at the origin, using only steps N,S,E,W,SE, and ending at the origin. The number of such walks (called excursions) of length n does not satisfy a linear recurrence with polynomial coefficients, while it does for other step sets. A computer-aided proof of this and related facts relies on probability theory (eigenvalues of a Laplacian); number theory (G-functions); and an irrationality result. See [6] for more.
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 [7].
chan_cover
tore-cycles 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 [8] for more.
  1. 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.}
    }

  2. 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]
    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 = {{ISSAC} '15: Proceedings of the 2015 {ACM} International Symposium on Symbolic and Algebraic Computation},
    Date-Added = {2015-07-02 06:19:51 +0000},
    Date-Modified = {2015-07-16 05:19:32 +0000},
    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 the accompanying Maple worksheet on arXiv.},
    Numpages = {8},
    Pages = {275--282},
    Publisher = {ACM},
    Series = {ISSAC '15},
    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.}
    }

  3. 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.
    arXiv:abs/1510.04080
    doi:10.1145/2755996.2756663
    [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$. 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 = {{ISSAC} '15: Proceedings of the 2015 {ACM} International Symposium on Symbolic and Algebraic Computation},
    Date-Added = {2015-07-02 06:14:59 +0000},
    Date-Modified = {2015-07-02 06:30:58 +0000},
    Doi = {10.1145/2755996.2756663},
    Isbn = {978-1-4503-3435-8},
    Keywords = {algorithms, diagonals, walks},
    Location = {Bath, United Kingdom},
    arxiv = {abs/1510.04080},
    Numpages = {8},
    Pages = {77--84},
    Publisher = {ACM},
    Series = {ISSAC '15},
    Title = {Algebraic Diagonals and Walks},
    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.}
    }

  4. 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 ISSAC'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.}
    }

  5. M. Bardet, J. 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:abs/1312.1655
    doi:10.1016/j.jsc.2014.09.025
    [BibTeX] [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.

    @article{BardetFaugereSalvy2015,
    Arxiv = {abs/1312.1655},
    Author = {Bardet, Magali and Faug{\`e}re, Jean-Charles and Salvy, Bruno},
    Journal = {Journal of Symbolic Computation},
    Institution = {arXiv},
    Title = {On the Complexity of the {F}5 {G}r{\"o}bner basis Algorithm},
    Year = {2015},
    doi = {10.1016/j.jsc.2014.09.025},
    Volume = 70,
    pages = {49--70},
    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.
    }
    }

  6. 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:abs/1205.3300
    doi:10.1016/j.jcta.2013.09.005
    [BibTeX] [Abstract]
    We prove that the sequence $(e^{\mathfrak{S}}_n)_{n\geq 0}$ of excursions in the quarter plane corresponding to a nonsingular step set $\mathfrak{S}\subseteq\{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^{\mathfrak{S}}_n$.

    @article{BostanRaschelSalvy2014,
    Arxiv = {abs/1205.3300},
    Author = {Bostan, Alin and Raschel, Kilian and Salvy, Bruno},
    Date-Added = {2013-10-04 14:03:46 +0000},
    Date-Modified = {2013-10-04 14:04:09 +0000},
    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^{\mathfrak{S}}_n)_{n\geq 0}$ of excursions in the quarter plane corresponding to a nonsingular step set $\mathfrak{S}\subseteq\{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^{\mathfrak{S}}_n$.
    }}

  7. R. Serra, D. Arzelier, M. Joldes, J. 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:10.2514/6.2014-4366
    [BibTeX] [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.

    @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},
    Date-Added = {2014-09-01 13:54:17 +0000},
    Date-Modified = {2014-09-01 13:58:59 +0000},
    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.}
    }

  8. 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]
    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 = {ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation},
    Date-Added = {2013-07-02 11:35:49 +0000},
    Date-Modified = {2013-07-02 11:35:49 +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},
    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.
    },
    Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QXC4uLy4uLy4uLy4uLy4uLy4uLy4uLy4uLy4uL1VzZXJzL3NhbHZ5L0dvb2dsZSBEcml2ZS9CaWJsaW8vYXJ0aWNsZS9Cb3N0YW5MYWlyZXpTYWx2eTIwMTMucGRm0hcLGBlXTlMuZGF0YU8RAdYAAAAAAdYAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMf841NIKwAAALC1VxlCb3N0YW5MYWlyZXpTYWx2eTIwMTMucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABLevKzWUPbQAAAAAAAAAAAAoABgAACSAAAAAAAAAAAAAAAAAAAAAHYXJ0aWNsZQAAEAAIAADH/MczAAAAEQAIAADNZQFdAAAAAQAUALC1VwCyNyAAsjbnACcergAAk1MAAgBTTWFjaW50b3NoIEhEOlVzZXJzOgBzYWx2eToAR29vZ2xlIERyaXZlOgBCaWJsaW86AGFydGljbGU6AEJvc3RhbkxhaXJlelNhbHZ5MjAxMy5wZGYAAA4ANAAZAEIAbwBzAHQAYQBuAEwAYQBpAHIAZQB6AFMAYQBsAHYAeQAyADAAMQAzAC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgBBVXNlcnMvc2FsdnkvR29vZ2xlIERyaXZlL0JpYmxpby9hcnRpY2xlL0Jvc3RhbkxhaXJlelNhbHZ5MjAxMy5wZGYAABMAAS8AABUAAgAM//8AAIAG0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVQBgAGcAagBsAG4AcQBzAHUAdwCEAI4A7QDyAPoC1ALWAtsC5gLvAv0DAQMIAxEDFgMjAyYDOAM7A0AAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADQg==},
    Bdsk-Url-1 = {http://arxiv.org/abs/1301.4313}}

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.