Frédéric Chyzak's Publications

Here is my full list of publications by reverse chronological order. See the same list by categories. Other lists: HAL, arXiv, dblp, MathSciNet.

2024

  Frédéric Chyzak and Marni Mishna. Differential equations satisfied by generating functions of 5-, 6-, and 7-regular labelled graphs: a reduction-based approach. Preprint, June 2024. [ bib | .pdf ]
By a classic result of Gessel, the exponential generating functions for k-regular graphs are D-finite. 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. First-order factors of linear Mahler operators. Preprint, March 2024. [ bib | .pdf ]
We develop and compare two algorithms for computing first-order right-hand 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$.
The first of our algorithms is adapted from Petkovšek's classical algorithm for the analogous problem in the case of linear recurrences. The second one proceeds by computing a basis of generalized power series solutions of the functional equation and by using Hermite–Padé approximants to detect those linear combinations of the solutions that correspond to first-order factors.
We present implementations of both algorithms and discuss their use in combination with criteria from the literature to prove the differential transcendence of power series solutions of Mahler equations.

2023

  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.

2022

  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 101--110. 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 Bousquet-Mé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 guess-and-prove paradigm. We then design two new algorithms: the first has a geometric flavor, the second blends elimination and guess-and-prove. 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. Symbolic-numeric factorization of differential operators. In Lihong Zhi, editor, ISSAC'22, pages 73--82. ACM Press, 2022. [ bib | .pdf ]
We present a symbolic-numeric Las Vegas algorithm for factoring Fuchsian ordinary differential operators with rational function coefficients. The new algorithm combines ideas of van Hoeij's “local-to-global” method and of the “analytic” approach proposed by van der Hoeven. It essentially reduces to the former in “easy” cases where the local-to-global method succeeds, and to an optimized variant of the latter in the “hardest” cases, while handling intermediate cases more efficiently than both.

2020

  Alin Bostan, Frédéric Chyzak, Antonio Jiménez-Pastor, and Pierre Lairez. The Sage package comb_walks for walks in the quarter plane. ACM Communications in Computer Algebra, 54(2):30--38, 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 half-plane 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 south-east steps. We adapt and generalize it to a bijection between half-plane walks using those three steps in two colours and a quarter-plane model over the symmetrized step set consisting of north, north-west, west, south, south-east, and east. We then generalize our bijections to certain models with large steps: for given $p\geq1$, a bijection is given between the half-plane and quarter-plane models obtained by keeping the small south-east 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 Bousquet-Mélou, Fusy, and Raschel.
  Frédéric Chyzak and Philippe Dumas. A Gröbner-basis theory for divide-and-conquer recurrences. In Anton Leykin, editor, ISSAC'20, pages 99--106. ACM Press, 2020. [ bib | DOI | .pdf ]
Divide-and-conquer 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 divide-and-conquer 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öbner-basis 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.

2019

  Frédéric Chyzak and Frank Nielsen. A closed-form formula for the Kullback-Leibler divergence between Cauchy distributions. https://arxiv.org/abs/1905.10965, May 2019. 8 pages. [ bib | .pdf ]
We report a closed-form expression for the Kullback-Leibler divergence between Cauchy distributions which involves the calculation of a parametric definite integral with 6 parameters. The formula shows that the Kullback-Leibler 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 k-regular power series, then there exists a k-regular rational function R(z) such that F(z)/R(z) satisfies a Mahler-type functional equation with polynomial coefficients where the initial coefficient satisfies a0(z) = 1. In this paper, we prove Becker's conjecture in the best-possible form; we show that the rational function R(z) can be taken to be a polynomial zγ Q(z) for some explicit non-negative integer γ and such that 1/Q(z) is k-regular.

2018

  Alin Bostan, Frédéric Chyzak, Pierre Lairez, and Bruno Salvy. Generalized Hermite reduction, creative telescoping and definite integration of D-finite functions. In Éric Schost, editor, ISSAC'18, pages 95--102. 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 D-finite functions of several continuous or discrete parameters. The resulting algorithm is a generalization of reduction-based 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):2977--3021, 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 divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions. A difficulty in the manipulation of Mahler equations is the exponential blow-up 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 polynomial-time 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.

2017

  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 (self-pub.), Palaiseau, September 2017. 686 pages. Printed by CreateSpace. Also available in electronic format. ISBN: 979-10-699-0947-2. [ 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é.
Cet ouvrage est une synthèse de notes de cours rédigées principalement pour le cours du même nom que nous avons donné pendant plus de dix ans au Master Parisien de Recherche en Informatique de l’Université Paris Diderot, des Écoles Normales Supérieures de Cachan et de Paris, et de l’École polytechnique. La partie concernant les systèmes polynomiaux provient aussi de notes de cours donnés au DEA Méthodes algébriques puis au Master Algèbre et Géométrie de l’Université Pierre-et-Marie-Curie, mais aussi au DEA Informatique Mathématique et Applications de l’École Normale Supérieure de Paris, l’École polytechnique, l’Université Pierre-et-Marie-Curie, l’Université Paris Diderot, et l’Université Paris-Sud. Plusieurs parties ont aussi fait l’objet de mini-cours plus spécialisés donnés à l’occasion des Journées Nationales de Calcul Formel en 2007, 2010, 2011, et 2013.
  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:242--275, 2017. [ bib | DOI | .pdf ]
We study nearest-neighbors walks on the two-dimensional square lattice, that is, models of walks on $\mathbb{Z}^2$ defined by a fixed step set that is a subset of the non-zero 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. Bousquet-Mélou and Mishna [Contemp. Math., pp. 1–39, Amer. Math. Soc., 2010] identified 19 models of walks that possess a D-finite 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.

2015

  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:1--26, 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.

2014

  Frédéric Chyzak. The ABC of Creative Telescoping: Algorithms, Bounds, Complexity. Memoir of accreditation to supervise research (HDR), University Paris-Sud 11, April 2014. 64 pages. [ bib | .pdf ]
  Frédéric Chyzak, Assia Mahboubi, Thomas Sibut-Pinote, and Enrico Tassi. a computer-algebra-based 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 160--176, 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 14-17, 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.

2013

  Alin Bostan, Frédéric Chyzak, and Élie de Panafieu. Complexity estimates for two uncoupling algorithms. In ISSAC 2013, pages 85--92. 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 cyclic-vector method (CVM) and the Danilevski-Barkatou-Zü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 quasi-optimal 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 77--84. ACM, New York, 2013. [ bib | .pdf ]
We present a new reduction algorithm that simultaneously extends Hermite's reduction for rational functions and the Hermite-like 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.

2012

  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 twenty-fifth International Symposium on Symbolic and Algebraic Computation, pages 99--106, 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.

2011

  Frédéric Chyzak, James H. Davenport, Christoph Koutschan, and Bruno Salvy. On Kahan's rules for determining branch cuts. In SYNASC, pages 47--51, September 2011. 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. September 26-29, 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 run-time generation of mathematical contents and their presentation on the web. In Olivier Danvy, editor, ICFP'11 (September 19--21, 2011, Tokyo, Japan), pages 259--265. 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 computer-algebra system as well as fragments of mathematical web documents are embedded directly and naturally inside OCaml code. A DynaMoW-based 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):1--27, 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$ three-dimensional chessboard, assuming that the piece moves closer to the goal cell at each step. We describe the computer-driven 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(2-3w)}{(1-4w)^3}} \right) }{(1-4w)(1-64w)} \, dw . \]

2010

  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 203--210, New York, NY, USA, 2010. ACM. [ bib | DOI | .pdf ]
The long-term 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 complexity-driven 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 well-known 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 35--41, 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.

2009

  Frédéric Chyzak, Manuel Kauers, and Bruno Salvy. A non-holonomic systems approach to special function identities. In John May, editor, ISSAC'09: Proceedings of the twenty-second international symposium on Symbolic and algebraic computation, pages 111--118, 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. Rational-functions telescopers: blending creative telescoping with Hermite reduction. Poster at the conference ISSAC'09 (Seoul, South Korea), 2009. [ bib | .pdf ]

2008

  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):21--59, 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 sub-tree 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 20--23, 2008, Hagenberg, Austria), pages 23--30. 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 previously-known 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.

2007

  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 233--264. Springer Berlin / Heidelberg, 2007. [ bib | DOI | .pdf ]
In the seventies, the study of transfer matrices of time-invariant 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 ACM-SIAM Symposium on Discrete Algorithms, pages 1012--1021, 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 quasi-linear with respect to $N$. Similar results are also given in the non-linear 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 25--32, 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.

2006

  Alin Bostan, Frédéric Chyzak, Thomas Cluzeau, and Bruno Salvy. Low complexity algorithms for linear recurrences. In Jean-Guillaume Dumas, editor, ISSAC'06, pages 31--38. 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 speed-ups are obtained in indefinite and definite hypergeometric summation. We describe the results of an implementation.

2005

  Frédéric Chyzak, editor. Algorithms Seminar, 2002--2004, 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):319--376, 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 time-varying ordinary differential systems (ODEs), differential time-delay 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 D-finite symmetric functions. Journal of Combinatorial Theory. Series A, 112(1):1--43, 2005. [ bib | .pdf ]
Many combinatorial generating functions can be expressed as combinations of symmetric functions, or extracted as sub-series and specializations from such combinations. Gessel has outlined a large class of symmetric functions for which the resulting generating functions are D-finite. 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 k-regular 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 D-Finite Symmetric Functions”.)

2004

  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 5--9, 2004. [ bib | .pdf ]

2003

  Frédéric Chyzak, editor. Algorithms Seminar, 2001--2002, 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 Time-Delay Systems, 2003. Electronic proceedings of an IFAC Workshop, INRIA-Roquencourt (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 time-varying ordinary differential systems (ODEs), differential time-delay 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, 2001--2002, number 5003 in INRIA Research Report, pages 33--36. INRIA, 2003. Summary of a talk by A. Bostan. [ bib | .pdf ]
  Moulay Barkatou, Frédéric Chyzak, and Michèle Loday-Richaud. 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 87--129. 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 sub-series $\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.

2002

  Frédéric Chyzak, Marni Mishna, and Bruno Salvy. Effective D-finite symmetric functions. In 14th Conference of Formal Power Series and Algebraic Combinatorics, pages 19.1--19.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 D-finite. This work extends these results by giving a method for making the D-finite 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, 2000--2001, 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 average-case analysis of algorithms and data structures.
  Frédéric Chyzak. A tutorial on closed difference forms. In F. Chyzak, editor, Algorithms Seminar, 2000--2001, number 4406 in INRIA Research Report, pages 89--94. 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, 2000--2001, number 4406 in INRIA Research Report, pages 105--112. INRIA, 2002. Summary of a talk by A. Quadrat. [ bib | .pdf ]

2001

  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):67--86, 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):468--486, 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.

2000

  Frédéric Chyzak, editor. Algorithms Seminar, 1999--2000, 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 average-case analysis of algorithms and data structures.
  Frédéric Chyzak. About the non-minimality of the outputs of Zeilberger's algorithm. Technical Report 00-08, 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 holonomy-based 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 partial-finite 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, 1999--2000, number 4056 in INRIA Research Report, pages 57--63. 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, 1999--2000, number 4056 in INRIA Research Report, pages 23--26. 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(1-3):115--134, 2000. Proceedings of Formal power series and algebraic combinatorics (Vienna, 1997). [ bib | .pdf ]
We extend Zeilberger's fast algorithm for definite hypergeometric summation to non-hypergeometric 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, 1999--2000, number 4056 in INRIA Research Report, pages 43--46. INRIA, 2000. Summary of a talk by P. Zimmermann. [ bib | .pdf ]

1999

  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:139--151, 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, 1998--1999, number 3830 in INRIA Research Report, pages 43--48. INRIA, 1999. Summary of a talk by J.-A. Weil. [ bib | .pdf ]

1998

  Frédéric Chyzak and Bruno Salvy. Non-commutative elimination in Ore algebras proves multivariate identities. Journal of Symbolic Computation, 26(2):187--227, 1998. [ bib | .pdf ]
Many computations involving special functions, combinatorial sequences or their q-analogues can be performed using linear operators and simple arguments on the dimension of related vector spaces. In this article, we develop a theory of D-finite 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, 1997--1998, number 3504 in INRIA Research Report, pages 79--82. 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 32--60. 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 non-commutative 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 D-modules. The former resort to non-commutative 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.

1997

  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 172--183. Universität Wien, 1997. Conference proceedings. [ bib | .pdf ]
We extend Zeilberger's fast algorithm for definite hypergeometric summation to non-hypergeometric holonomic sequences. The algorithm generalizes to differential and q-cases 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, 1996--1997, number 3267 in INRIA Research Report, pages 41--44. 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, 1996--1997, number 3267 in INRIA Research Report, pages 33--36. INRIA, 1997. Summary of a talk by J.-A. Weil. [ bib | .pdf ]

1996

  Frédéric Chyzak. Zero-one law for maps. In B. Salvy, editor, Algorithms Seminar, 1995--1996, number 2992 in INRIA Research Report, pages 19--22. 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, 1995--1996, number 2992 in INRIA Research Report, pages 59--62. INRIA, September 1996. Summary of a talk by J. Shackell. [ bib | .pdf ]
  Frédéric Chyzak. Matrix-based methods for solving polynomial systems. In B. Salvy, editor, Algorithms Seminar, 1995--1996, number 2992 in INRIA Research Report, pages 51--54. INRIA, September 1996. Summary of a talk by I. Émiris. [ bib | .pdf ]

1995

  Frédéric Chyzak. Polynomial solutions of linear operator equations. In B. Salvy, editor, Algorithms Seminar, 1994--1995, number 2669 in INRIA Research Report, pages 31--34. 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, 1994--1995, number 2669 in INRIA Research Report, pages 47--50. INRIA, October 1995. Summary of a talk by A. Péladan-Germa. [ 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 so-called 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.

1994

  Frédéric Chyzak. Piecewise-constant derivative systems and their algorithmic properties. In B. Salvy, editor, Algorithms Seminar, 1993--1994, number 2381 in INRIA Research Report, pages 133--136. 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 so-called 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.