Here is my full list of publications by reverse chronological order. See the same list by categories. Other lists: HAL, arXiv, dblp, MathSciNet.
Frédéric Chyzak and Marni Mishna.
Differential equations satisfied by generating functions of 5, 6,
and 7regular labelled graphs: a reductionbased approach.
Preprint, June 2024.
[ bib 
.pdf ]
By a classic result of Gessel, the exponential generating functions for kregular graphs are Dfinite. Using Gröbner bases in Weyl algebras, we compute the linear differential equations satisfied by the generating function for 5, 6, and 7 regular graphs. The method is sufficiently robust to consider variants such as graphs with multiple edges, loops, and graphs whose degrees are limited to fixed sets of values. 

Frédéric Chyzak, Thomas Dreyfus, Philippe Dumas, and Marc Mezzarobba.
Firstorder factors of linear Mahler operators.
Preprint, March 2024.
[ bib 
.pdf ]
We develop and compare two algorithms for computing firstorder righthand factors in the ring of linear Mahler operators $\ell_r M^r + \dots + \ell_1 M + \ell_0$ where $\ell_0, \dots, \ell_r$ are polynomials in $x$ and $Mx = x^b M$ for some integer $b \geq 2$. In other words, we give algorithms for finding all formal infinite product solutions of linear functional equations $\ell_r(x) f(x^{b^r}) + \dots + \ell_1(x) f(x^b) + \ell_0(x) f(x) = 0$. 
Alin Bostan, Frédéric Chyzak, and Vincent Pilaud.
Refined product formulas for Tamari intervals.
https://arxiv.org/abs/1905.10965, March 2023.
[ bib 
.pdf ]
We provide short product formulas for the $f$vectors of the canonical complexes of the Tamari lattices and of the cellular diagonals of the associahedra. 
Alin Bostan, Frédéric Chyzak, Hadrien Notarantonio, and Mohab Safey El Din.
Algorithms for discrete differential equations of order 1.
In Lihong Zhi, editor, ISSAC'22, pages 101110. ACM Press,
2022.
[ bib 
.pdf ]
Discrete differential equations of order 1 relate polynomially a power series $F(t,u)$ in $t$ with polynomial coefficients in a “catalytic” variable $u$ and one of its specializations, say $F(t,1)$. Such equations are ubiquitous in combinatorics, notably in the enumeration of maps and walks. When the solution $F$ is unique, a celebrated result by BousquetMélou and Jehanne, reminiscent of Popescu's theorem in commutative algebra, states that $F$ is algebraic. We address algorithmic and complexity questions related to this result. In generic situations, we first revisit and analyze known algorithms, based either on polynomial elimination or on the guessandprove paradigm. We then design two new algorithms: the first has a geometric flavor, the second blends elimination and guessandprove. In the general case (no genericity assumptions), we prove that the total arithmetic size of the algebraic equations for $F(t,1)$ is bounded polynomially in the size of the input discrete differential equation, and that one can compute such equations in polynomial time. 

Frédéric Chyzak, Alexandre Goyer, and Marc Mezzarobba.
Symbolicnumeric factorization of differential operators.
In Lihong Zhi, editor, ISSAC'22, pages 7382. ACM Press, 2022.
[ bib 
.pdf ]
We present a symbolicnumeric Las Vegas algorithm for factoring Fuchsian ordinary differential operators with rational function coefficients. The new algorithm combines ideas of van Hoeij's “localtoglobal” method and of the “analytic” approach proposed by van der Hoeven. It essentially reduces to the former in “easy” cases where the localtoglobal method succeeds, and to an optimized variant of the latter in the “hardest” cases, while handling intermediate cases more efficiently than both. 
Alin Bostan, Frédéric Chyzak, Antonio JiménezPastor, and Pierre Lairez.
The Sage package comb_walks for walks in the quarter
plane.
ACM Communications in Computer Algebra, 54(2):3038, September
2020.
Software presentation at ISSAC '20.
[ bib 
DOI 
.pdf ]
We present in this extended abstract a new software designed to work with generating functions that count walks in the quarter plane. With this software we offer a cohesive package that brings together all the required procedures for manipulating these generating functions, as well as a unified interface to deal with them. We also display results that this package offers on a public webpage. 

Frédéric Chyzak and Karen Yeats.
Bijections between Łukasiewicz walks and generalized tandem walks.
The Electronic Journal of Combinatorics, 27(2), April 2020.
Article number P2.3. 46 pages. Implementation available at
https://arxiv.org/abs/1810.04117.
[ bib 
DOI 
.pdf ]
In this article, we study the enumeration by length of several walk models on the square lattice. We obtain bijections between walks in the upper halfplane returning to the $x$axis and walks in the quarter plane. A recent work by Bostan, Chyzak, and Mahboubi has given a bijection for models using small north, west, and southeast steps. We adapt and generalize it to a bijection between halfplane walks using those three steps in two colours and a quarterplane model over the symmetrized step set consisting of north, northwest, west, south, southeast, and east. We then generalize our bijections to certain models with large steps: for given $p\geq1$, a bijection is given between the halfplane and quarterplane models obtained by keeping the small southeast step and replacing the two steps north and west of length 1 by the $p+1$ steps of length $p$ in directions between north and west. This model is close to, but distinct from, the model of generalized tandem walks studied by BousquetMélou, Fusy, and Raschel. 

Frédéric Chyzak and Philippe Dumas.
A Gröbnerbasis theory for divideandconquer recurrences.
In Anton Leykin, editor, ISSAC'20, pages 99106. ACM Press,
2020.
[ bib 
DOI 
.pdf ]
Divideandconquer recurrences relate values of a given sequence at indices of the form $b^ℓ n + r$ for fixed $b\geq2$ and various pairs $(ℓ,r)$. Using systems of such recurrences makes it possible to express the behaviour of a quantity according to congruence classes modulo $b^ℓ$. The study of such systems is poorly developed so far. In particular, no consistency check is available and no theory of initial values has been developed yet. In an ongoing study in order to fill this gap, we have introduced a noncommutative multivariate polynomial setting to represent divideandconquer systems. This setting involves at the same time variables that behave like words in purely noncommutative algebras and variables governed by commutation rules like in skew polynomial extensions. In the present work, we initiate the study of left ideals of such polynomials and we develop their Gröbnerbasis theory, including the usual division and Buchberger algorithms. Strikingly, the nature of commutations generally prevents the leading monomial of a polynomial product to be the product of the leading monomials. To overcome the difficulty, we consider a specific monomial ordering, together with a restriction to monic divisors in intermediate steps. We also develop a variant of the $F_4$ algorithm with distinguishing features. 
Frédéric Chyzak and Frank Nielsen.
A closedform formula for the KullbackLeibler divergence between
Cauchy distributions.
https://arxiv.org/abs/1905.10965, May 2019.
8 pages.
[ bib 
.pdf ]
We report a closedform expression for the KullbackLeibler divergence between Cauchy distributions which involves the calculation of a parametric definite integral with 6 parameters. The formula shows that the KullbackLeibler divergence between Cauchy densities is always finite and symmetric. 

Jason P. Bell, Frédéric Chyzak, Michael Coons, and Philippe Dumas.
Becker's conjecture on Mahler functions.
Transactions of the American Mathematical Society, 2019.
[ bib 
.pdf ]
In 1994, Becker conjectured that if F(z) is a kregular power series, then there exists a kregular rational function R(z) such that F(z)/R(z) satisfies a Mahlertype functional equation with polynomial coefficients where the initial coefficient satisfies a_{0}(z) = 1. In this paper, we prove Becker's conjecture in the bestpossible form; we show that the rational function R(z) can be taken to be a polynomial z^{γ} Q(z) for some explicit nonnegative integer γ and such that 1/Q(z) is kregular. 
Alin Bostan, Frédéric Chyzak, Pierre Lairez, and Bruno Salvy.
Generalized Hermite reduction, creative telescoping and definite
integration of Dfinite functions.
In Éric Schost, editor, ISSAC'18, pages 95102. ACM Press,
2018.
[ bib 
DOI 
.pdf ]
Hermite reduction is a classical algorithmic tool in symbolic integration. It is used to decompose a given rational function as a sum of a function with simple poles and the derivative of another rational function. We extend Hermite reduction to arbitrary linear differential operators instead of the pure derivative, and develop efficient algorithms for this reduction. We then apply the generalized Hermite reduction to the computation of linear operators satisfied by single definite integrals of Dfinite functions of several continuous or discrete parameters. The resulting algorithm is a generalization of reductionbased methods for creative telescoping. 

Frédéric Chyzak, Thomas Dreyfus, Philippe Dumas, and Marc Mezzarobba.
Computing solutions of linear Mahler equations.
Mathematics of Computation, 87(314):29773021, 2018.
[ bib 
DOI 
.pdf ]
Mahler equations relate evaluations of the same function $f$ at iterated $b$th powers of the variable. They arise in particular in the study of automatic sequences and in the complexity analysis of divideandconquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with numbertheoretic questions. A difficulty in the manipulation of Mahler equations is the exponential blowup of degrees when applying a Mahler operator to a polynomial. In this work, we present algorithms for solving linear Mahler equations for series, polynomials, and rational functions, and get polynomialtime complexity under a mild assumption. Incidentally, we develop an algorithm for computing the gcrd of a family of linear Mahler operators with nonzero constant terms. 
Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Grégoire Lecerf,
Bruno Salvy, and Éric Schost.
Algorithmes Efficaces en Calcul Formel.
Frédéric Chyzak (selfpub.), Palaiseau, September 2017.
686 pages. Printed by CreateSpace. Also available in electronic
format.
ISBN: 9791069909472.
[ bib 
http ]
Le calcul formel traite des objets mathématiques exacts d’un point de vue informatique. Cet ouvrage « Algorithmes efficaces en calcul formel » explore deux directions : la calculabilité et la complexité. La calculabilité étudie les classes d’objets mathématiques sur lesquelles des réponses peuvent être obtenues algorithmiquement. La complexité donne ensuite des outils pour comparer des algorithmes du point de vue de leur efficacité. 

Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Manuel Kauers, and Lucien Pech.
Hypergeometric expressions for generating functions of walks with
small steps in the quarter plane.
European Journal of Combinatorics, 61:242275, 2017.
[ bib 
DOI 
.pdf ]
We study nearestneighbors walks on the twodimensional square lattice, that is, models of walks on $\mathbb{Z}^2$ defined by a fixed step set that is a subset of the nonzero vectors with coordinates 0, 1 or $1$. We concern ourselves with the enumeration of such walks starting at the origin and constrained to remain in the quarter plane $\mathbb{N}^2$, counted by their length and by the position of their ending point. BousquetMélou and Mishna [Contemp. Math., pp. 1–39, Amer. Math. Soc., 2010] identified 19 models of walks that possess a Dfinite generating function; linear differential equations have then been guessed in these cases by Bostan and Kauers [FPSAC 2009, Discrete Math. Theor. Comput. Sci. Proc., pp. 201–215, 2009]. We give here the first proof that these equations are indeed satisfied by the corresponding generating functions. As a first corollary, we prove that all these 19 generating functions can be expressed in terms of Gauss' hypergeometric functions that are intimately related to elliptic integrals. As a second corollary, we show that all the 19 generating functions are transcendental, and that among their $19\times4$ combinatorially meaningful specializations only four are algebraic functions. 
Shaoshi Chen, Frédéric Chyzak, Ruyong Feng, Guofeng Fu, and Ziming Li.
On the existence of telescopers for mixed hypergeometric terms.
Journal of Symbolic Computation, 68, Part 1:126, 2015.
[ bib 
DOI 
.pdf ]
We present a criterion for the existence of telescopers for mixed hypergeometric terms, which is based on additive and multiplicative decompositions. The criterion enables us to determine the termination of Zeilberger's algorithms for mixed hypergeometric inputs, and to verify that certain indefinite sums do not satisfy any polynomial differential equation. 
Frédéric Chyzak. The ABC of Creative Telescoping: Algorithms, Bounds, Complexity. Memoir of accreditation to supervise research (HDR), University ParisSud 11, April 2014. 64 pages. [ bib  .pdf ]  
Frédéric Chyzak, Assia Mahboubi, Thomas SibutPinote, and Enrico Tassi.
a computeralgebrabased formal proof of the
irrationality of $\zeta(3)$.
In Gerwin Klein and Ruben Gamboa, editors, Interactive Theorem
Proving, number 8558 in Lecture Notes in Computer Science, pages 160176,
Vienna, Austria, 2014. Springer.
Proceedings of 5th International Conference, ITP 2014, held as part
of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 1417, 2014.
[ bib 
.pdf ]
This paper describes the formal verification of an irrationality proof of $\zeta(3)$, the evaluation of the Riemann zeta function, using the Coq proof assistant. This result was first proved by Apéry in 1978, and the proof we have formalized follows the path of his original presentation. The crux of this proof is to establish that some sequences satisfy a common recurrence. We formally prove this result by an a posteriori verification of calculations performed by computer algebra algorithms in a Maple session. The rest of the proof combines arithmetical ingredients and some asymptotic analysis that we conduct by extending the Mathematical Components libraries. The formalization of this proof is complete up to a weak corollary of the Prime Number Theorem. 
Alin Bostan, Frédéric Chyzak, and Élie de Panafieu.
Complexity estimates for two uncoupling algorithms.
In ISSAC 2013, pages 8592. ACM, New York, 2013.
[ bib 
.pdf ]
Uncoupling algorithms transform a linear differential system of first order into one or several scalar differential equations. We examine two approaches to uncoupling: the cyclicvector method (CVM) and the DanilevskiBarkatouZürcher algorithm (DBZ). We give tight size bounds on the scalar equations produced by CVM, and design a fast variant of CVM whose complexity is quasioptimal with respect to the output size. We exhibit a strong structural link between CVM and DBZ enabling to show that, in the generic case, DBZ has polynomial complexity and that it produces a single equation, strongly related to the output of CVM. We prove that algorithm CVM is faster than DBZ by almost two orders of magnitude, and provide experimental results that validate the theoretical complexity analyses. 

Alin Bostan, Shaoshi Chen, Frédéric Chyzak, Ziming Li, and Guoce Xin.
Hermite reduction and creative telescoping for hyperexponential
functions.
In ISSAC 2013, pages 7784. ACM, New York, 2013.
[ bib 
.pdf ]
We present a new reduction algorithm that simultaneously extends Hermite's reduction for rational functions and the Hermitelike reduction for hyperexponential functions. It yields a unique additive decomposition that allows to decide hyperexponential integrability. Based on this reduction algorithm, we design a new algorithm to compute minimal telescopers for bivariate hyperexponential functions. One of its main features is that it can avoid the costly computation of certificates. Its implementation outperforms Maple's function DEtools[Zeilberger]. We also derive an order bound on minimal telescopers that is tighter than the known ones. 
Frédéric Chyzak. Creative telescoping for parametrised integration and summation. In Journées Nationales de Calcul Formel 2011, volume 2 of Les Cours du CIRM. Cedram, 2012. 37 pages. Lecture notes. [ bib  DOI  .pdf ]  
Alin Bostan, Frédéric Chyzak, Ziming Li, and Bruno Salvy.
Fast computation of common left multiples of linear ordinary
differential operators.
In Mark van Hoeij and Joris van der Hoeven, editors, ISSAC '12:
Proceedings of the twentyfifth International Symposium on Symbolic and
Algebraic Computation, pages 99106, 2012.
[ bib 
.pdf ]
We study tight bounds and fast algorithms for LCLMs of several linear differential operators with polynomial coefficients. We analyze the arithmetic complexity of existing algorithms for LCLMs, as well as the size of their outputs. We propose a new algorithm that recasts the LCLM computation in a linear algebra problem on a polynomial matrix. This algorithm yields sharp bounds on the coefficient degrees of the LCLM, improving by one order of magnitude the best bounds obtained using previous algorithms. The complexity of the new algorithm is almost optimal, in the sense that it nearly matches the arithmetic size of the output. 
Frédéric Chyzak, James H. Davenport, Christoph Koutschan, and Bruno Salvy.
On Kahan's rules for determining branch cuts.
In SYNASC, pages 4751, September 2011.
13th International Symposium on Symbolic and Numeric Algorithms for
Scientific Computing. September 2629, 2011. Timisoara, Romania.
[ bib 
.pdf ]
In computer algebra there are different ways of approaching the mathematical concept of functions, one of which is by defining them as solutions of differential equations. We compare different such approaches and discuss the occurring problems. The main focus is on the question of determining possible branch cuts. We explore the extent to which the treatment of branch cuts can be rendered (more) algorithmic, by adapting Kahan's rules to the differential equation setting. 

Alin Bostan, Frédéric Chyzak, Ziming Li, and Bruno Salvy. Fast computation of common left multiples of linear ordinary differential operators. Poster at ISSAC 2011, July 2011. [ bib  DOI  .pdf ]  
Frédéric Chyzak and Alexis Darrasse.
Using Camlp4 for presenting dynamic mathematics on the web:
DynaMoW, an OCaml language extension for the runtime generation of
mathematical contents and their presentation on the web.
In Olivier Danvy, editor, ICFP'11 (September 1921, 2011,
Tokyo, Japan), pages 259265. ACM, 2011.
(An experience report.).
[ bib 
.pdf ]
We report on the design and implementation of a programming tool, DynaMoW, to control interactive and incremental mathematical calculations to be presented on the web. This tool is implemented as a language extension of OCaml using Camlp4. Fragments of mathematical code written for a computeralgebra system as well as fragments of mathematical web documents are embedded directly and naturally inside OCaml code. A DynaMoWbased application is made of independent web services, whose parameter types are checked by the OCaml extension. The approach is illustrated by two implementations of online mathematical encyclopedias on top of DynaMoW. 

Alin Bostan, Frédéric Chyzak, Mark van Hoeij, and Lucien Pech.
Explicit formula for the generating series of diagonal 3D rook
paths.
Séminaire Lotharingien de Combinatoire, 66(B66a):127, 2011.
[ bib 
.pdf ]
Let $a_n$ denote the number of ways in which a chess rook can move from a corner cell to the opposite corner cell of an $n \times n \times n$ threedimensional chessboard, assuming that the piece moves closer to the goal cell at each step. We describe the computerdriven discovery and proof of the fact that the generating series $G(x)= \sum_{n \geq 0} a_n x^n$ admits the following explicit expression in terms of a Gaussian hypergeometric function: \[ G(x) = 1 + 6 \cdot \int_0^x \frac{ {}_2F_1\left(1/3,2/3;2; {\frac{27 w(23w)}{(14w)^3}} \right) }{(14w)(164w)} \, dw . \] 
Alin Bostan, Shaoshi Chen, Frédéric Chyzak, and Ziming Li.
Complexity of creative telescoping for bivariate rational functions.
In ISSAC'10: Proceedings of the 2010 International Symposium on
Symbolic and Algebraic Computation, pages 203210, New York, NY, USA, 2010.
ACM.
[ bib 
DOI 
.pdf ]
The longterm goal initiated in this work is to obtain fast algorithms and implementations for definite integration in Almkvist and Zeilberger's framework of (differential) creative telescoping. Our complexitydriven approach is to obtain tight degree bounds on the various expressions involved in the method. To make the problem more tractable, we restrict to bivariate rational functions. By considering this constrained class of inputs, we are able to blend the general method of creative telescoping with the wellknown Hermite reduction. We then use our new method to compute diagonals of rational power series arising from combinatorics. 

Alexandre Benoit, Frédéric Chyzak, Alexis Darrasse, Stefan Gerhold, Marc
Mezzarobba, and Bruno Salvy.
The Dynamic Dictionary of Mathematical Functions (DDMF).
In Komei Fukuda, Joris van der Hoeven, Michael Joswig, and Nobuki
Takayama, editors, The Third International Congress on Mathematical
Software (ICMS 2010), volume 6327 of Lecture Notes in Computer
Science, pages 3541, 2010.
[ bib 
DOI 
.pdf ]
We describe the main features of the Dynamic Dictionary of Mathematical Functions (version 1.5). It is a website consisting of interactive tables of mathematical formulas on elementary and special functions. The formulas are automatically generated by computer algebra routines. The user can ask for more terms of the expansions, more digits of the numerical values, or proofs of some of the formulas. 
Frédéric Chyzak, Manuel Kauers, and Bruno Salvy.
A nonholonomic systems approach to special function identities.
In John May, editor, ISSAC'09: Proceedings of the twentysecond
international symposium on Symbolic and algebraic computation, pages
111118, 2009.
[ bib 
DOI 
.pdf ]
We extend Zeilberger's approach to special function identities to cases that are not holonomic. The method of creative telescoping is thus applied to definite sums or integrals involving Stirling or Bernoulli numbers, incomplete Gamma function or polylogarithms, which are not covered by the holonomic framework. The basic idea is to take into account the dimension of appropriate ideals in Ore algebras. This unifies several earlier extensions and provides algorithms for summation and integration in classes that had not been accessible to computer algebra before. 

Alin Bostan, Shaoshi Chen, Frédéric Chyzak, and Ziming Li. Rationalfunctions telescopers: blending creative telescoping with Hermite reduction. Poster at the conference ISSAC'09 (Seoul, South Korea), 2009. [ bib  .pdf ] 
Frédéric Chyzak and Peter Paule. Computer algebra. Draft of a methodological chapter for the NIST's Digital Library of Mathematical Functions. 40 pages, 2008. [ bib ]  
Frédéric Chyzak, Michael Drmota, Thomas Klausner, and Gerard Kok.
The distribution of patterns in random trees.
Combinatorics, Probability & Computing, 17(1):2159, 2008.
[ bib 
.pdf ]
Let ${\mathcal T}_n$ denote the set of unrooted labeled trees of size $n$ and let $\mathcal M$ be a particular (finite) tree. Assuming that every tree of ${\mathcal T}_n$ is equally likely, it is shown that the limiting distribution of the number of occurrences of $\mathcal M$ as an induced subtree is asymptotically normal with mean value $\sim\mu n$ and variance $\sim\sigma^2n$ with computable constants $\mu>0$ and $\sigma\ge 0$. 

Alin Bostan, Frédéric Chyzak, and Nicolas Le Roux.
Products of ordinary differential operators by evaluation and
interpolation.
In ISSAC'08 (July 2023, 2008, Hagenberg, Austria), pages
2330. ACM, 2008.
Conference proceedings.
[ bib 
.pdf ]
It is known that multiplication of linear differential operators over ground fields of characteristic zero can be reduced to a constant number of matrix products. We give a new algorithm by evaluation and interpolation which is faster than the previouslyknown one by a constant factor, and prove that in characteristic zero, multiplication of differential operators and of matrices are computationally equivalent problems. In positive characteristic, we show that differential operators can be multiplied in nearly optimal time. Theoretical results are validated by intensive experiments. 
Frédéric Chyzak, Alban Quadrat, and Daniel Robertz.
OreModules: a symbolic package for the study of multidimensional
linear systems.
In Applications of Time Delay Systems, volume 352 of
Lecture Notes in Control and Information Sciences, pages 233264. Springer
Berlin / Heidelberg, 2007.
[ bib 
DOI 
.pdf ]
In the seventies, the study of transfer matrices of timeinvariant linear systems of ordinary differential equations (ODEs) led to the development of the polynomial approach. In particular, the univariate polynomial matrices play a central role in this approach (e.g., Hermite, Smith and Popov forms, invariant factors, primeness, Bézout/Diophantine equations). 

Alin Bostan, Frédéric Chyzak, François Ollivier, Bruno Salvy, Éric Schost,
and Alexandre Sedoglavic.
Fast computation of power series solutions of systems of differential
equations.
In 18th ACMSIAM Symposium on Discrete Algorithms, pages
10121021, 2007.
New Orleans, January 2007.
[ bib 
.pdf ]
We propose algorithms for the computation of the first $N$ terms of a vector (or a full basis) of power series solutions of a linear system of differential equations at an ordinary point, using a number of arithmetic operations that is quasilinear with respect to $N$. Similar results are also given in the nonlinear case. This extends previous results obtained by Brent and Kung for scalar differential equations of order 1 and 2. 

Alin Bostan, Frédéric Chyzak, Grégoire Lecerf, Bruno Salvy, and Éric
Schost.
Differential equations for algebraic functions.
In ISSAC'07: Proceedings of the 2007 International Symposium on
Symbolic and Algebraic Computation, pages 2532, 2007.
[ bib 
.pdf ]
It is classical that univariate algebraic functions satisfy linear differential equations with polynomial coefficients. From there, linear recurrences follow for the coefficients of their power series expansions. We show that the linear differential equation of minimal order has coefficients whose degree is cubic in the degree of the function. We also show that there exists a linear differential equation of order linear in the degree whose coefficients are only of quadratic degree. Furthermore, we prove the existence of recurrences of order and degree close to optimal. We study the complexity of computing these differential equations and recurrences. 
Alin Bostan, Frédéric Chyzak, Thomas Cluzeau, and Bruno Salvy.
Low complexity algorithms for linear recurrences.
In JeanGuillaume Dumas, editor, ISSAC'06, pages 3138. ACM
Press, 2006.
[ bib 
.pdf ]
We consider two kinds of problems: the computation of polynomial and rational solutions of linear recurrences with coefficients that are polynomials with integer coefficients; indefinite and definite summation of sequences that are hypergeometric over the rational numbers. The algorithms for these tasks all involve as an intermediate quantity an integer $N$ (dispersion or root of an indicial polynomial) that is potentially exponential in the bit size of their input. Previous algorithms have a bit complexity that is at least quadratic in $N$. We revisit them and propose variants that exploit the structure of solutions and avoid expanding polynomials of degree $N$. We give two algorithms: a probabilistic one that detects the existence or absence of nonzero polynomial and rational solutions in $O(\sqrt{N}\log^{2}N)$ bit operations; a deterministic one that computes a compact representation of the solution in $O(N\log^{3}N)$ bit operations. Similar speedups are obtained in indefinite and definite hypergeometric summation. We describe the results of an implementation. 
Frédéric Chyzak, editor.
Algorithms Seminar, 20022004, volume 5542 of INRIA
Research Report. INRIA, April 2005.
120 pages.
[ bib 
.pdf ]
These seminar notes constitute the proceedings of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include combinatorics, symbolic computation, and the asymptotic analysis of algorithms, data structures, and network protocols. 

F. Chyzak, A. Quadrat, and D. Robertz.
Effective algorithms for parametrizing linear control systems over
Ore algebras.
Applicable Algebra in Engineering, Communication and Computing,
16(5):319376, 2005.
[ bib 
.pdf ]
In this paper, we study linear control systems over Ore algebras. Within this mathematical framework, we can simultaneously deal with different classes of linear control systems such as timevarying ordinary differential systems (ODEs), differential timedelay systems, partial differential equations (PDEs), multidimensional discrete systems, multidimensional codes etc. We give effective algorithms which check whether or not a linear control system over some Ore algebra is controllable, parametrizable, flat or $\pi$free. 

Frédéric Chyzak, Marni Mishna, and Bruno Salvy.
Effective scalar products of Dfinite symmetric functions.
Journal of Combinatorial Theory. Series A, 112(1):143, 2005.
[ bib 
.pdf ]
Many combinatorial generating functions can be expressed as combinations of symmetric functions, or extracted as subseries and specializations from such combinations. Gessel has outlined a large class of symmetric functions for which the resulting generating functions are Dfinite. We extend Gessel's work by providing algorithms that compute differential equations these generating functions satisfy in the case they are given as a scalar product of symmetric functions in Gessel's class. Examples of applications to kregular graphs and Young tableaux with repeated entries are given. Asymptotic estimates are a natural application of our method, which we illustrate on the same model of Young tableaux. We also derive a seemingly new formula for the Kronecker product of the sum of Schur functions with itself. (This article completes the extended abstract published in the proceedings of FPSAC'02 under the title “Effective DFinite Symmetric Functions”.) 
Frédéric Chyzak, Alban Quadrat, and Daniel Robertz. OreModules, a symbolic package for the study of multidimensional linear systems. In Sixteenth International Symposium on Mathematical Theory of Networks and Systems, Leuven, Belgium, July 2004. Katholieke Universiteit Leuven. Proceedings MTNS2004, Katholieke Universiteit Leuven, Belgium, July 59, 2004. [ bib  .pdf ] 
Frédéric Chyzak, editor.
Algorithms Seminar, 20012002, volume 5003 of INRIA
Research Report. INRIA, November 2003.
194 pages.
[ bib 
.pdf ]
These seminar notes constitute the proceedings of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include combinatorics, symbolic computation, asymptotic analysis, number theory, as well as the analysis of algorithms, data structures, and network protocols. 

Frédéric Chyzak, Alban Quadrat, and Daniel Robertz.
Linear control systems over Ore algebras: effective algorithms for
the computation of parametrizations.
In TimeDelay Systems, 2003.
Electronic proceedings of an IFAC Workshop, INRIARoquencourt
(France).
[ bib 
.pdf ]
In this paper, we study linear control systems over Ore algebras. Within this mathematical framework, we can simultaneously deal with different classes of linear control systems such as timevarying ordinary differential systems (ODEs), differential timedelay systems, partial differential equations (PDEs), multidimensional discrete systems, multidimensional codes etc. We give effective algorithms which check whether or not a linear control system over some Ore algebra is controllable, parametrizable, flat or πfree. 

Frédéric Chyzak. Fast algorithms for polynomial systems solving. In F. Chyzak, editor, Algorithms Seminar, 20012002, number 5003 in INRIA Research Report, pages 3336. INRIA, 2003. Summary of a talk by A. Bostan. [ bib  .pdf ]  
Moulay Barkatou, Frédéric Chyzak, and Michèle LodayRichaud.
Remarques algorithmiques liées au rang d'un opérateur différentiel
linéaire.
In From Combinatorics to Dynamical Systems, volume 3 of
IRMA Lectures in Mathematics and Theoretical Physics, pages 87129. de
Gruyter, Berlin, 2003.
[ bib 
.pdf ]
This paper aims at introducing and comparing various methods for solving the following problem which arises naturally in computer algebra for differential equations: given a series $\hat f(x)=\sum_{m\geq 0}u_mx^m$ solution of an ordinary linear differential equation and given an integer $r\geq 2$ find a differential equation satisfied by the subseries $\hat f^{(j)}(x)=\sum_{m\geq 0}u_{j+mr}x^{j+mr}$. These methods have been implemented in Maple. References are given to the corresponding programs. Possible realistic algorithms to effectively calculate the formal invariants of an ordinary linear differential system of order one and arbitrary rank are sketched in an Appendix. 
Frédéric Chyzak, Marni Mishna, and Bruno Salvy.
Effective Dfinite symmetric functions.
In 14th Conference of Formal Power Series and Algebraic
Combinatorics, pages 19.119.12, Melbourne, Australia, July 2002.
University of Melbourne.
Extended abstract. Proceedings FPSAC'02.
[ bib 
.pdf ]
Some combinatorial generating functions can be expressed in terms of coefficients of symmetric functions. In simple cases these can be determined directly however, the general case is ``too unwieldly to be useful''. Gessel describes conditions in which the resulting generating functions are Dfinite. This work extends these results by giving a method for making the Dfinite effective by determining the differential equation satisfied by the generating functions. Two examples of the method are given: the equations satisfied by $k$regular graphs for $k=2,3,4$ and the equations satisfied by Young tableaux with each entry appearing $k$ times, for $k=2,3,4$. 

Frédéric Chyzak, editor.
Algorithms Seminar, 20002001, volume 4406 of INRIA
Research Report. INRIA, March 2002.
202 pages.
[ bib 
.pdf ]
These seminar notes constitute the proceedings of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include combinatorics, symbolic computation, asymptotic analysis, computational biology, and averagecase analysis of algorithms and data structures. 

Frédéric Chyzak. A tutorial on closed difference forms. In F. Chyzak, editor, Algorithms Seminar, 20002001, number 4406 in INRIA Research Report, pages 8994. INRIA, 2002. Summary of a talk by B. Zimmermann. [ bib  .pdf ]  
Frédéric Chyzak. Effective algebraic analysis in linear control theory. In F. Chyzak, editor, Algorithms Seminar, 20002001, number 4406 in INRIA Research Report, pages 105112. INRIA, 2002. Summary of a talk by A. Quadrat. [ bib  .pdf ] 
Frédéric Chyzak, Peter Paule, Otmar Scherzer, Armin Schoisswohl, and Burkhard
Zimmermann.
The construction of orthonormal wavelets using symbolic methods and a
matrix analytical approach for wavelets on the interval.
Experimental Mathematics, 10(1):6786, 2001.
[ bib 
.pdf ]
In this paper we discuss closed form representations of filter coefficients of wavelets on the real line, half real line and on compact intervals. We show that computer algebra can be applied to achieve this task. Moreover, we present a matrix analytical approach that unifies constructions of wavelets on the interval. 

Manuel Bronstein and Frédéric Chyzak. Differential equations: to solve or not to solve? / Équations différentielles : résoudre ou manipuler ? INédit, (27), 2001. [ bib ]  
M. J. Atallah, F. Chyzak, and P. Dumas.
A randomized algorithm for approximate string matching.
Algorithmica. An International Journal in Computer Science,
29(3):468486, 2001.
[ bib 
.pdf ]
We give a randomized algorithm in deterministic time $O(N\log M)$ for estimating the score vector of matches between a text string of length $N$ and a pattern string of length $M$, i.e., the vector obtained when the pattern is slid along the text, and the number of matches is counted for each position. A direct application is approximate string matching. The randomized algorithm bases on convolution to find an estimator of the scores; the variance of the estimator is particularly small for scores that are close to $M$, i.e., for approximate occurrences of the pattern in the text. No assumption is made about the probabilistic characteristics of the input, or about the size of the alphabet. The solution extends to string matching with classes, class complements, ``never match'' and ``always match'' symbols, to the weighted case and to higher dimensions. 
Frédéric Chyzak, editor.
Algorithms Seminar, 19992000, volume 4056 of INRIA
Research Report. INRIA, November 2000.
154 pages.
[ bib 
.pdf ]
These seminar notes constitute the proceedings of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include combinatorics, symbolic computation, asymptotic analysis, computational biology, and averagecase analysis of algorithms and data structures. 

Frédéric Chyzak.
About the nonminimality of the outputs of Zeilberger's algorithm.
Technical Report 0008, Austrian project SFB F013, Linz, Austria,
April 2000.
Bruno Buchberger and Peter Paule, Eds. 20 pages.
[ bib 
.pdf ]
We report on case studies where Zeilberger's fast algorithm and the other holonomybased algorithms known so far for definite hypergeometric summation fail to find the minimal annihilating recurrence satisfied by the sum. To explain the phenomenon we propose a new elimination paradigm, together with a promising heuristic method which we hope to turn into an algorithm in the future. The approach applies to partialfinite functions as well and extends to the related algorithms. 

Frédéric Chyzak and Pierre Nicodème. Eigenring and reducibility of difference equations. In F. Chyzak, editor, Algorithms Seminar, 19992000, number 4056 in INRIA Research Report, pages 5763. INRIA, 2000. Summary of a talk by R. Bomboy. [ bib  .pdf ]  
Frédéric Chyzak. Tutte polynomials in square grids. In F. Chyzak, editor, Algorithms Seminar, 19992000, number 4056 in INRIA Research Report, pages 2326. INRIA, 2000. Summary of a talk by M. Noy. [ bib  .pdf ]  
Frédéric Chyzak.
An extension of Zeilberger's fast algorithm to general holonomic
functions.
Discrete Mathematics, 217(13):115134, 2000.
Proceedings of Formal power series and algebraic combinatorics
(Vienna, 1997).
[ bib 
.pdf ]
We extend Zeilberger's fast algorithm for definite hypergeometric summation to nonhypergeometric holonomic sequences. The algorithm generalizes to the differential case and to $q$calculus as well. Its theoretical justification is based on a description by linear operators and on the theory of holonomy. 

Frédéric Chyzak. Efficient algorithms on numbers, polynomials, and series. In F. Chyzak, editor, Algorithms Seminar, 19992000, number 4056 in INRIA Research Report, pages 4346. INRIA, 2000. Summary of a talk by P. Zimmermann. [ bib  .pdf ] 
Frédéric Chyzak, Ivan Gutman, and Peter Paule.
Predicting the number of hexagonal systems with 24 and 25 hexagons.
Communications in Mathematical and Computer Chemistry,
40:139151, 1999.
[ bib 
.pdf ]
We predict the number of hexagonal systems consisting of 24 and 25 hexagons to be $H_{24}=122237774262384$ and $H_{25}=606259305418149$, with 6 and 5 significant digits, respectively. Further estimates for $H_n$ up to ${n=31}$ are also given. 

Frédéric Chyzak.
Manipulations par le calcul formel de représentations implicites de
suites et fonctions spéciales.
15 pages, 1999.
[ bib 
.pdf ]
Une grande classe de fonctions spéciales et de suites combinatoires d'entiers qui sont représentées sous forme implicite par des systèmes d'équations fonctionnelles linéaires est sujette à un traitement par des méthodes de calcul formel. Les applications en sont la simplification d'expressions en termes de fonctions et suites spéciales, l'évaluation d'intégrales et de sommes paramétrées, les développements en série et asymptotiques, et la preuve automatique d'identités. La classe considérée jouit de nombreuses propriétés de clôture qui ont été étudiée depuis le début des années 1990 et qui ont récemment été transcrites en algorithmes. L'approche est la suivante. Pour prendre en compte un type d'opérateurs linéaires généraux, une classe d'algèbres de polynômes multivariés non commutatifs est introduite, à savoir les algèbres de Ore. Dans ce cadre, les fonctions spéciales et les suites combinatoires sont vues comme les zéros d'idéaux à gauche particuliers des algèbres de Ore. Des algorithmes pour la manipulation des fonctions et suites spéciales font alors appel à de l'élimination polynomiale dans ces algèbres d'opérateurs linéaires, pour lesquels des méthodes de bases de Gröbner non commutatives ont été developpées. 

Frédéric Chyzak. Concrete resolution of differential problems using Tannakian categories. In B. Salvy, editor, Algorithms Seminar, 19981999, number 3830 in INRIA Research Report, pages 4348. INRIA, 1999. Summary of a talk by J.A. Weil. [ bib  .pdf ] 
Frédéric Chyzak and Bruno Salvy.
Noncommutative elimination in Ore algebras proves multivariate
identities.
Journal of Symbolic Computation, 26(2):187227, 1998.
[ bib 
.pdf ]
Many computations involving special functions, combinatorial sequences or their qanalogues can be performed using linear operators and simple arguments on the dimension of related vector spaces. In this article, we develop a theory of Dfinite sequences and functions which provides a unified framework to express algorithms for computing sums and integrals and for the proof or discovery of multivariate identities. This approach is vindicated by an implementation. 

Frédéric Chyzak. ISOLDE, a package for computing invariants of systems of ordinary linear differential equations. In B. Salvy, editor, Algorithms Seminar, 19971998, number 3504 in INRIA Research Report, pages 7982. INRIA, 1998. Summary of a talk by E. Pflügel. [ bib  .pdf ]  
Frédéric Chyzak.
Gröbner bases, symbolic summation and symbolic integration.
In Gröbner Bases and Applications (Linz, 1998), volume 251 of
London Mathematical Society Lecture Note Series, pages 3260.
Cambridge Univ. Press, Cambridge, 1998.
Text of an invited tutorial.
[ bib 
.pdf ]
The treatment of combinatorial expressions and special functions by linear operators is amenable to Gröbner basis methods. In this tutorial, we illustrate the applications of Gröbner bases to symbolic summation and integration. 

Frédéric Chyzak.
Fonctions holonomes en Calcul formel.
PhD thesis, École polytechnique, 1998.
TU 0531. 227 pages.
[ bib 
.pdf ]
This thesis shows how computer algebra makes it possible to manipulate a large class of sequences and functions that are solutions of linear operators, namely that of holonomic functions. This class contains numerous special functions, in one or several variables, as well as numerous combinatorial sequences. First, a theoretical framework is introduced in order to give algorithms for the closure properties of the holonomic class, to permit a zero test in this class, and to unify differential calculations with functions and calculations of recurrences with sequences. These methods are based on calculations by an extension of the theory of Gröbner bases in a framework of noncommutative polynomials, namely Ore polynomials. Two kinds of algorithms for symbolic definite and indefinite summation and integration are then developed, whose theoretical justification appeals to the theory of holonomic Dmodules. The former resort to noncommutative polynomial elimination by Gröbner bases; the latter to algorithms to solve linear functional systems for their rational function solutions. Much more than the search for closed forms, the aim is to be able to continue to compute with the implicit representation of holonomic objects even when no explicit form is available. In particular, this type of calculation makes the automatic proof of summatory and integral identities possible. An implementation of these algorithms for the computer algebra system Maple has made it possible to give the first automatic proof of identities so far unreachable by computer algebra. 
Frédéric Chyzak.
An extension of Zeilberger's fast algorithm to general holonomic
functions.
In Formal Power Series and Algebraic Combinatorics, 9th
Conference, pages 172183. Universität Wien, 1997.
Conference proceedings.
[ bib 
.pdf ]
We extend Zeilberger's fast algorithm for definite hypergeometric summation to nonhypergeometric holonomic sequences. The algorithm generalizes to differential and qcases as well. Its theoretical justification is based on a description by linear operators and on the theory of holonomy. 

Frédéric Chyzak. Differential equations, nested forms and star products. In B. Salvy, editor, Algorithms Seminar, 19961997, number 3267 in INRIA Research Report, pages 4144. INRIA, 1997. Summary of a talk by J. Shackell. [ bib  .pdf ]  
Frédéric Chyzak. Absolute factorization of differential operators. In B. Salvy, editor, Algorithms Seminar, 19961997, number 3267 in INRIA Research Report, pages 3336. INRIA, 1997. Summary of a talk by J.A. Weil. [ bib  .pdf ] 
Frédéric Chyzak. Zeroone law for maps. In B. Salvy, editor, Algorithms Seminar, 19951996, number 2992 in INRIA Research Report, pages 1922. INRIA, September 1996. Summary of a talk by K. Compton. [ bib  .pdf ]  
Frédéric Chyzak. On a problem of Rubel. In B. Salvy, editor, Algorithms Seminar, 19951996, number 2992 in INRIA Research Report, pages 5962. INRIA, September 1996. Summary of a talk by J. Shackell. [ bib  .pdf ]  
Frédéric Chyzak. Matrixbased methods for solving polynomial systems. In B. Salvy, editor, Algorithms Seminar, 19951996, number 2992 in INRIA Research Report, pages 5154. INRIA, September 1996. Summary of a talk by I. Émiris. [ bib  .pdf ] 
Frédéric Chyzak. Polynomial solutions of linear operator equations. In B. Salvy, editor, Algorithms Seminar, 19941995, number 2669 in INRIA Research Report, pages 3134. INRIA, October 1995. Summary of a talk by M. Petkovšek. [ bib  .pdf ]  
Frédéric Chyzak. Effective identity testing in extensions of differential fields. In B. Salvy, editor, Algorithms Seminar, 19941995, number 2669 in INRIA Research Report, pages 4750. INRIA, October 1995. Summary of a talk by A. PéladanGerma. [ bib  .pdf ]  
Frédéric Chyzak.
Manipulations formelles d'opérateurs linéaires et calculs
holonomes.
Master's thesis, École polytechnique, June 1995.
[ bib 
.pdf ]
We present a computer algebra package in the Maple language for the symbolic manipulation of linear systems of differential and recurrence equations. This programme is especially designed to deal with socalled holonomic systems. This report also gives a theoretical justification to our implementation. The set of holonomic functions and sequences is a large class of objects. It forms an algebra and is closed under algebraic substitution and diagonal. An implementation of these properties makes it possible to perform computer assisted proofs of holonomic identities in a simple way, since a holonomic system has a normal form obtained by an extension of the Gröbner basis algorithm. For instance, combinatorial problems often lead to holonomic systems and to identities involving binomial coefficients. Many identities involving special functions are also captured by the theory of holonomy. Examples are given to show how some interesting identities are proved by our system. 
Frédéric Chyzak. Piecewiseconstant derivative systems and their algorithmic properties. In B. Salvy, editor, Algorithms Seminar, 19931994, number 2381 in INRIA Research Report, pages 133136. INRIA, October 1994. Summary of a talk by E. Asarin. [ bib  .pdf ]  
Frédéric Chyzak.
Holonomic systems and automatic proofs of identities.
Technical Report 2371, INRIA, October 1994.
[ bib 
.pdf ]
This report presents three computer algebra packages in the Maple language for the symbolic manipulation of linear systems of differential and recurrence equations. They are especially designed to deal with socalled holonomic systems. We also give a theoretical justification to our implementation. The set of holonomic functions and sequences is a large class of objects. It forms an algebra and is closed under algebraic substitution and diagonal. An implementation of these properties makes it possible to perform computer assisted proofs of holonomic identities in a simple way, since any holonomic system has a normal form obtained by an extension of the Gröbner basis algorithm. For instance, combinatorial problems often lead to holonomic systems and to identities involving binomial coefficients. Many identities involving special functions are also captured by the theory of holonomy. Examples are given to show how some interesting identities are proved by our system. 
This file was generated by bibtex2html.