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

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

- 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

[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 F5 algorithm in this generic case for the grevlex ordering (which is also a bound on the number of polynomials for a reduced Gröbner basis), and use it to bound the exponent of the complexity of the F5 algorithm.

`@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}, Note = {To appear.}, Abstract = {We study the complexity of Gr{\"o}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{\"o}bner basis computed by Faug{\`e}re's F5 algorithm in this generic case for the grevlex ordering (which is also a bound on the number of polynomials for a reduced Gr{\"o}bner basis), and use it to bound the exponent of the complexity of the F5 algorithm.} }`

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

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

- 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}}`

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

## AddressLIP – ENS Lyon email: Firstname.Lastname@inria.fr |
## VisitorsMy office is #274
Call me if you cannot get inside the building. |