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

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 [1] 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 [2] 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 [3].
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 [4] for more.
A combinatorial version of Newton’s iteration leads to fast routines for the enumeration and random generation of series-parallel graphs. This is just an example of a very general approach to a large family of combinatorial structures that can be defined recursively [5]. circuit100
  1. M. Bardet, J. Faugère, and B. Salvy, “On the complexity of the F5 Gröbner basis algorithm,” Journal of symbolic computation, 2014.
    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{BardetFaugereSalvy2014,
    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 = {2014},
    doi = {10.1016/j.jsc.2014.09.025},
    Note = {To appear.},
    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.
    }
    }

  2. 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$.
    }}

  3. 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.}
    }

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

  5. 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:abs/1109.2688
    doi:10.1016/j.jcta.2012.05.007
    [BibTeX] [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.

    @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.},
    Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.jcta.2012.05.007}}

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 37 28 76 23

Visitors

My office is #274
on the 2nd floor of the LUG.
Here are directions to get there.

 

Call me if you cannot get inside the building.