@comment{{This file has been generated by bib2bib 1.99}}
@comment{{Command line: bib2bib -ob /tmp/fc-publis-1 -c '! keywords : ".*not-on-web.*"' fchyzak-full.bib}}
@comment{{keywords utilisés pour les sous-biblios de la candidature DR : dr-international-journals, dr-reviewed-international-conferences, dr-books-and-book-chapters, dr-theses, dr-informal, dr-submitted}}
@comment{{keywords utilisés de manière intermédiaire dans le dossier DR : contrib-skew, contrib-ct, contrib-ddmf, contrib-proofs, contrib-combi}}
@comment{{keywords utilisés pour ma page web : web-journals, web-books, web-conferences, web-invited, web-posters, web-other, web-summaries, not-on-web}}
@comment{{keywords inutilisés : seminar-proceedings, seminar-summaries}}
@comment{{J'utilise web-posters pour les textes avec un processus de relecture léger.}}
@comment{{J'utilise web-other pour les textes informels et pour les articles avant acceptation (preprints, etc).}}
@techreport{Chyzak-1994-HSA,
author = {Chyzak, Frédéric},
title = {Holonomic systems and automatic proofs of identities},
institution = {INRIA},
year = {1994},
number = {2371},
month = oct,
abstract = {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.},
urlpdf = {Publications/Chyzak-1994-HSA.pdf}
}
@incollection{Chyzak-1994-PCD,
author = {Chyzak, Frédéric},
title = {Piecewise-constant derivative systems and their algorithmic properties},
booktitle = {Algorithms Seminar, 1993--1994},
publisher = {INRIA},
year = {1994},
editor = {Salvy, B.},
number = {2381},
series = {INRIA Research Report},
pages = {133--136},
month = oct,
note = {Summary of a talk by E.~Asarin},
urlpdf = {Publications/seminars/sem93-94/asarin.pdf}
}
@incollection{Chyzak-1995-EIT,
author = {Chyzak, Frédéric},
title = {Effective identity testing in extensions of differential fields},
booktitle = {Algorithms Seminar, 1994--1995},
publisher = {INRIA},
year = {1995},
editor = {Salvy, B.},
number = {2669},
series = {INRIA Research Report},
pages = {47--50},
month = oct,
note = {Summary of a talk by A.~Péladan-Germa},
urlpdf = {Publications/seminars/sem94-95/peladan.pdf}
}
@mastersthesis{Chyzak-1995-MFO,
author = {Chyzak, Frédéric},
title = {Manipulations formelles d'opérateurs linéaires et calculs holonomes},
school = {École polytechnique},
year = {1995},
month = jun,
abstract = {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.},
urlpdf = {Publications/Chyzak-1995-MFO.pdf}
}
@incollection{Chyzak-1995-PSL,
author = {Chyzak, Frédéric},
title = {Polynomial solutions of linear operator equations},
booktitle = {Algorithms Seminar, 1994--1995},
publisher = {INRIA},
year = {1995},
editor = {Salvy, B.},
number = {2669},
series = {INRIA Research Report},
pages = {31--34},
month = oct,
note = {Summary of a talk by M.~Petkov{\v{s}}ek},
urlpdf = {Publications/seminars/sem94-95/petkovsek.pdf}
}
@incollection{Chyzak-1996-MBM,
author = {Chyzak, Frédéric},
title = {Matrix-based methods for solving polynomial systems},
booktitle = {Algorithms Seminar, 1995--1996},
publisher = {INRIA},
year = {1996},
editor = {Salvy, B.},
number = {2992},
series = {INRIA Research Report},
pages = {51--54},
month = sep,
note = {Summary of a talk by I.~Émiris},
urlpdf = {Publications/seminars/sem95-96/emiris.pdf}
}
@incollection{Chyzak-1996-OPR,
author = {Chyzak, Frédéric},
title = {On a problem of {R}ubel},
booktitle = {Algorithms Seminar, 1995--1996},
publisher = {INRIA},
year = {1996},
editor = {Salvy, B.},
number = {2992},
series = {INRIA Research Report},
pages = {59--62},
month = sep,
note = {Summary of a talk by J.~Shackell},
urlpdf = {Publications/seminars/sem95-96/shackell.pdf}
}
@incollection{Chyzak-1996-ZOL,
author = {Chyzak, Frédéric},
title = {Zero-one law for maps},
booktitle = {Algorithms Seminar, 1995--1996},
publisher = {INRIA},
year = {1996},
editor = {Salvy, B.},
number = {2992},
series = {INRIA Research Report},
pages = {19--22},
month = sep,
note = {Summary of a talk by K.~Compton},
urlpdf = {Publications/seminars/sem95-96/compton.pdf}
}
@incollection{Chyzak-1997-AFD,
author = {Chyzak, Frédéric},
title = {Absolute factorization of differential operators},
booktitle = {Algorithms Seminar, 1996--1997},
publisher = {INRIA},
year = {1997},
editor = {Salvy, B.},
number = {3267},
series = {INRIA Research Report},
pages = {33--36},
note = {Summary of a talk by J.-A.~Weil},
urlpdf = {Publications/seminars/sem96-97/weil.pdf}
}
@incollection{Chyzak-1997-DEN,
author = {Chyzak, Frédéric},
title = {Differential equations, nested forms and star products},
booktitle = {Algorithms Seminar, 1996--1997},
publisher = {INRIA},
year = {1997},
editor = {Salvy, B.},
number = {3267},
series = {INRIA Research Report},
pages = {41--44},
note = {Summary of a talk by J.~Shackell},
urlpdf = {Publications/seminars/sem96-97/shackell.pdf}
}
@inproceedings{Chyzak-1997-EZF,
author = {Chyzak, Frédéric},
title = {An extension of {Z}eilberger's fast algorithm to general holonomic functions},
booktitle = {Formal Power Series and Algebraic Combinatorics, 9th Conference},
year = {1997},
pages = {172--183},
organization = {Universität Wien},
note = {Conference proceedings},
abstract = {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.},
urlpdf = {Publications/Chyzak-1997-EZF.pdf}
}
@phdthesis{Chyzak-1998-FHC,
author = {Chyzak, Frédéric},
title = {Fonctions holonomes en Calcul formel},
school = {École polytechnique},
year = {1998},
note = {TU 0531. 227 pages},
abstract = {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~$\mathcal 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 {\sc Maple} has made it possible to give the first automatic proof of identities so far unreachable by computer algebra.},
urlpdf = {Publications/Chyzak-1998-FHC.pdf}
}
@incollection{Chyzak-1998-GBS,
author = {Chyzak, Frédéric},
title = {Gröbner bases, symbolic summation and symbolic integration},
booktitle = {Gröbner Bases and Applications (Linz, 1998)},
publisher = {Cambridge Univ. Press},
year = {1998},
volume = {251},
series = {London Mathematical Society Lecture Note Series},
pages = {32--60},
address = {Cambridge},
note = {Text of an invited tutorial},
abstract = {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.},
mrclass = {68W30 (13P10 33C45 33F10 65-04)},
mrnumber = {MR1699813 (2001a:68115)},
mrreviewer = {Karin Gatermann},
urlpdf = {Publications/Chyzak-1998-GBS.pdf}
}
@incollection{Chyzak-1998-IPC,
author = {Chyzak, Frédéric},
title = {{ISOLDE}, a package for computing invariants of systems of ordinary linear differential equations},
booktitle = {Algorithms Seminar, 1997--1998},
publisher = {INRIA},
year = {1998},
editor = {Salvy, B.},
number = {3504},
series = {INRIA Research Report},
pages = {79--82},
note = {Summary of a talk by E.~Pflügel},
urlpdf = {Publications/seminars/sem97-98/pfluegel.pdf}
}
@article{ChyzakSalvy-1998-NCE,
author = {Chyzak, Frédéric and Salvy, Bruno},
title = {Non-commutative elimination in {O}re algebras proves multivariate identities},
journal = {Journal of Symbolic Computation},
year = {1998},
volume = {26},
number = {2},
pages = {187--227},
issn = {0747-7171},
abstract = {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.},
mrclass = {68Q40 (05A19)},
mrnumber = {MR1635242 (99g:68103)},
mrreviewer = {A. N. Philippou},
urlpdf = {Publications/ChyzakSalvy-1998-NCE.pdf}
}
@incollection{Chyzak-1999-CRD,
author = {Chyzak, Frédéric},
title = {Concrete resolution of differential problems using {T}annakian categories},
booktitle = {Algorithms Seminar, 1998--1999},
publisher = {INRIA},
year = {1999},
editor = {Salvy, B.},
number = {3830},
series = {INRIA Research Report},
pages = {43--48},
note = {Summary of a talk by J.-A.~Weil},
urlpdf = {Publications/seminars/sem98-99/weil.pdf}
}
@unpublished{Chyzak-1999-MCF,
author = {Chyzak, Frédéric},
title = {Manipulations par le calcul formel de représentations implicites de suites et fonctions spéciales},
note = {15 pages},
year = {1999},
abstract = {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.},
urlpdf = {Publications/Chyzak-1999-MCF.pdf}
}
@article{ChyzakGutmanPaule-1999-PNH,
author = {Chyzak, Frédéric and Gutman, Ivan and Paule, Peter},
title = {Predicting the number of hexagonal systems with 24 and 25 hexagons},
journal = {Communications in Mathematical and Computer Chemistry},
year = {1999},
volume = {40},
pages = {139--151},
abstract = {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.},
urlpdf = {Publications/ChyzakGutmanPaule-1999-PNH.pdf}
}
@techreport{Chyzak-2000-ANM,
author = {Chyzak, Frédéric},
title = {About the non-minimality of the outputs of {Z}eilberger's algorithm},
institution = {Austrian project SFB F013},
year = {2000},
number = {00-08},
address = {Linz, Austria},
month = apr,
note = {Bruno Buchberger and Peter Paule, Eds. 20 pages},
abstract = {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.},
urlpdf = {Publications/Chyzak-2000-ANM.pdf}
}
@incollection{Chyzak-2000-EAN,
author = {Chyzak, Frédéric},
title = {Efficient algorithms on numbers, polynomials, and series},
booktitle = {Algorithms Seminar, 1999--2000},
publisher = {INRIA},
year = {2000},
editor = {Chyzak, F.},
number = {4056},
series = {INRIA Research Report},
pages = {43--46},
note = {Summary of a talk by P.~Zimmermann},
urlpdf = {Publications/seminars/sem99-00/zimmermann.pdf}
}
@article{Chyzak-2000-EZF,
author = {Chyzak, Frédéric},
title = {An extension of {Z}eilberger's fast algorithm to general holonomic functions},
journal = {Discrete Mathematics},
year = {2000},
volume = {217},
number = {1-3},
pages = {115--134},
issn = {0012-365X},
note = {Proceedings of Formal power series and algebraic combinatorics (Vienna, 1997)},
abstract = {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.},
coden = {DSMHA4},
mrclass = {33F10 (05A19)},
mrnumber = {MR1766263 (2001m:33041)},
mrreviewer = {Peter Paule},
urlpdf = {Publications/Chyzak-2000-EZF.pdf}
}
@incollection{Chyzak-2000-TPS,
author = {Chyzak, Frédéric},
title = {Tutte polynomials in square grids},
booktitle = {Algorithms Seminar, 1999--2000},
publisher = {INRIA},
year = {2000},
editor = {Chyzak, F.},
number = {4056},
series = {INRIA Research Report},
pages = {23--26},
note = {Summary of a talk by M.~Noy},
urlpdf = {Publications/seminars/sem99-00/noy2.pdf}
}
@incollection{Chyzak-2000-ERD,
author = {Chyzak, Frédéric and Nicodème, Pierre},
title = {Eigenring and reducibility of difference equations},
booktitle = {Algorithms Seminar, 1999--2000},
publisher = {INRIA},
year = {2000},
editor = {Chyzak, F.},
number = {4056},
series = {INRIA Research Report},
pages = {57--63},
note = {Summary of a talk by R.~Bomboy},
urlpdf = {Publications/seminars/sem99-00/bomboy.pdf}
}
@proceedings{Chyzak-2000-AS,
title = {Algorithms Seminar, 1999--2000},
year = {2000},
editor = {Chyzak, Frédéric},
volume = {4056},
series = {INRIA Research Report},
month = nov,
organization = {INRIA},
note = {154 pages},
abstract = {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.},
urlpdf = {Publications/RR-4056.pdf}
}
@article{AtallahChyzakDumas-2001-RAA,
author = {Atallah, M. J. and Chyzak, F. and Dumas, P.},
title = {A randomized algorithm for approximate string matching},
journal = {Algorithmica. An International Journal in Computer Science},
year = {2001},
volume = {29},
number = {3},
pages = {468--486},
issn = {0178-4617},
abstract = {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.},
coden = {ALGOEJ},
mrclass = {68W20 (68W05)},
mrnumber = {MR1799271 (2002h:68240)},
urlpdf = {Publications/AtallahChyzakDumas-2001-RAA.pdf}
}
@article{BronsteinChyzak-2001-DES,
author = {Bronstein, Manuel and Chyzak, Frédéric},
title = {Differential equations: to solve or not to solve? / Équations différentielles~: résoudre ou manipuler~?},
journal = {INédit},
year = {2001},
number = {27},
}
@article{ChyzakPauleScherzerSchoisswohlZimmermann-2001-COW,
author = {Chyzak, Frédéric and Paule, Peter and Scherzer, Otmar and Schoisswohl, Armin and Zimmermann, Burkhard},
title = {The construction of orthonormal wavelets using symbolic methods and a matrix analytical approach for wavelets on the interval},
journal = {Experimental Mathematics},
year = {2001},
volume = {10},
number = {1},
pages = {67--86},
issn = {1058-6458},
abstract = {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.},
mrclass = {42C15 (42C40)},
mrnumber = {MR1822852},
urlpdf = {Publications/ChyzakPauleScherzerSchoisswohlZimmermann-2001-COW.pdf}
}
@incollection{Chyzak-2002-EAA,
author = {Chyzak, Frédéric},
title = {Effective algebraic analysis in linear control theory},
booktitle = {Algorithms Seminar, 2000--2001},
publisher = {INRIA},
year = {2002},
editor = {Chyzak, F.},
number = {4406},
series = {INRIA Research Report},
pages = {105--112},
note = {Summary of a talk by A.~Quadrat},
urlpdf = {Publications/seminars/sem00-01/quadrat.pdf}
}
@incollection{Chyzak-2002-TCD,
author = {Chyzak, Frédéric},
title = {A tutorial on closed difference forms},
booktitle = {Algorithms Seminar, 2000--2001},
publisher = {INRIA},
year = {2002},
editor = {Chyzak, F.},
number = {4406},
series = {INRIA Research Report},
pages = {89--94},
note = {Summary of a talk by B.~Zimmermann},
urlpdf = {Publications/seminars/sem00-01/bzimmermann.pdf}
}
@inproceedings{ChyzakMishnaSalvy-2002-EDF,
author = {Chyzak, Frédéric and Mishna, Marni and Salvy, Bruno},
title = {Effective {D}-finite symmetric functions},
booktitle = {14th Conference of Formal Power Series and Algebraic Combinatorics},
year = {2002},
pages = {19.1--19.12},
address = {Melbourne, Australia},
month = jul,
publisher = {University of Melbourne},
note = {Extended abstract. Proceedings FPSAC'02},
abstract = {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$.},
urlpdf = {Publications/ChyzakMishnaSalvy-2002-EDF.pdf}
}
@proceedings{Chyzak-2002-AS,
title = {Algorithms Seminar, 2000--2001},
year = {2002},
editor = {Chyzak, Frédéric},
volume = {4406},
series = {INRIA Research Report},
month = mar,
organization = {INRIA},
note = {202 pages},
abstract = {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.},
urlpdf = {Publications/RR-4406.pdf}
}
@incollection{BarkatouChyzakLodayRichaud-2003-RAL,
author = {Barkatou, Moulay and Chyzak, Frédéric and Loday-Richaud, Michèle},
title = {Remarques algorithmiques liées au rang d'un opérateur différentiel linéaire},
booktitle = {From Combinatorics to Dynamical Systems},
publisher = {de Gruyter},
year = {2003},
volume = {3},
series = {IRMA Lectures in Mathematics and Theoretical Physics},
pages = {87--129},
address = {Berlin},
abstract = {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 \emph{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.},
mrclass = {34M25 (12H05 12H10 68W30)},
mrnumber = {MR2049423 (2005c:34178)},
mrreviewer = {Pedro Fortuny Ayuso},
urlpdf = {Publications/BarkatouChyzakLodayRichaud-2003-RAL.pdf}
}
@incollection{Chyzak-2003-FAP,
author = {Chyzak, Frédéric},
title = {Fast algorithms for polynomial systems solving},
booktitle = {Algorithms Seminar, 2001--2002},
publisher = {INRIA},
year = {2003},
editor = {Chyzak, F.},
number = {5003},
series = {INRIA Research Report},
pages = {33--36},
note = {Summary of a talk by A.~Bostan},
urlpdf = {Publications/seminars/sem01-02/bostan.pdf}
}
@inproceedings{ChyzakQuadratRobertz-2003-LCS,
author = {Chyzak, Frédéric and Quadrat, Alban and Robertz, Daniel},
title = {Linear control systems over {O}re algebras: effective algorithms for the computation of parametrizations},
booktitle = {Time-Delay Systems},
year = {2003},
note = {Electronic proceedings of an IFAC Workshop, INRIA-Roquencourt (France)},
abstract = {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.},
urlpdf = {Publications/ChyzakQuadratRobertz-2003-LCS.pdf}
}
@proceedings{Chyzak-2003-AS,
title = {Algorithms Seminar, 2001--2002},
year = {2003},
editor = {Chyzak, Frédéric},
volume = {5003},
series = {INRIA Research Report},
month = nov,
organization = {INRIA},
note = {194 pages},
abstract = {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.},
urlpdf = {Publications/RR-5003.pdf}
}
@inproceedings{ChyzakQuadratRobertz-2004-OSP,
author = {Chyzak, Frédéric and Quadrat, Alban and Robertz, Daniel},
title = {{O}re{M}odules, a symbolic package for the study of multidimensional linear systems},
booktitle = {Sixteenth International Symposium on Mathematical Theory of Networks and Systems},
year = {2004},
address = {Leuven, Belgium},
month = jul,
publisher = {Katholieke Universiteit Leuven},
note = {Proceedings MTNS2004, Katholieke Universiteit Leuven, Belgium, July 5--9, 2004},
urlpdf = {Publications/ChyzakQuadratRobertz-2004-OSP.pdf}
}
@article{ChyzakMishnaSalvy-2005-ESP,
author = {Chyzak, Frédéric and Mishna, Marni and Salvy, Bruno},
title = {Effective scalar products of {D}-finite symmetric functions},
journal = {Journal of Combinatorial Theory. Series A},
year = {2005},
volume = {112},
number = {1},
pages = {1--43},
issn = {0097-3165},
abstract = {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''.)},
coden = {JCBTA7},
mrclass = {05E05 (13N10)},
mrnumber = {MR2167474 (2006d:05181)},
mrreviewer = {Grant Walker},
urlpdf = {Publications/ChyzakMishnaSalvy-2005-ESP.pdf}
}
@article{ChyzakQuadratRobertz-2005-EAP,
author = {Chyzak, F. and Quadrat, A. and Robertz, D.},
title = {Effective algorithms for parametrizing linear control systems over {O}re algebras},
journal = {Applicable Algebra in Engineering, Communication and Computing},
year = {2005},
volume = {16},
number = {5},
pages = {319--376},
issn = {0938-1279},
abstract = {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.},
coden = {AAECEW},
mrclass = {93B25 (13P99 93B40)},
mrnumber = {MR2233761 (2007c:93041)},
mrreviewer = {Tomás Sánchez-Giralda},
urlpdf = {Publications/ChyzakQuadratRobertz-2005-EAP.pdf}
}
@proceedings{Chyzak-2005-AS,
title = {Algorithms Seminar, 2002--2004},
year = {2005},
editor = {Chyzak, Frédéric},
volume = {5542},
series = {INRIA Research Report},
month = apr,
organization = {INRIA},
note = {120 pages},
abstract = {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.},
urlpdf = {Publications/RR-5542.pdf}
}
@inproceedings{BostanChyzakCluzeauSalvy-2006-LCA,
author = {Bostan, Alin and Chyzak, Frédéric and Cluzeau, Thomas and Salvy, Bruno},
title = {Low complexity algorithms for linear recurrences},
booktitle = {ISSAC'06},
year = {2006},
editor = {Jean-Guillaume Dumas},
pages = {31--38},
publisher = {ACM Press},
abstract = {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.},
urlpdf = {Publications/BostanChyzakCluzeauSalvy-2006-LCA.pdf}
}
@inproceedings{BostanChyzakLecerfSalvySchost-2007-DEA,
author = {Bostan, Alin and Chyzak, Frédéric and Lecerf, Grégoire and Salvy, Bruno and Schost, Éric},
title = {Differential equations for algebraic functions},
booktitle = {ISSAC'07: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation},
year = {2007},
pages = {25--32},
abstract = {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.},
urlpdf = {Publications/BostanChyzakLecerfSalvySchost-2007-DEA.pdf}
}
@inproceedings{BostanChyzakOllivierSalvySchostSedoglavic-2007-FCP,
author = {Bostan, Alin and Chyzak, Frédéric and Ollivier, François and Salvy, Bruno and Schost, Éric and Sedoglavic, Alexandre},
title = {Fast computation of power series solutions of systems of differential equations},
booktitle = {18th ACM-SIAM Symposium on Discrete Algorithms},
year = {2007},
pages = {1012--1021},
note = {New Orleans, January 2007},
abstract = {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.},
urlpdf = {Publications/BostanChyzakOllivierSalvySchostSedoglavic-2007-FCP.pdf}
}
@incollection{ChyzakQuadratRobertz-2007-OSP,
author = {Chyzak, Frédéric and Quadrat, Alban and Robertz, Daniel},
title = {{O}re{M}odules: a symbolic package for the study of multidimensional linear systems},
booktitle = {Applications of Time Delay Systems},
publisher = {Springer Berlin / Heidelberg},
year = {2007},
volume = {352},
series = {Lecture Notes in Control and Information Sciences},
pages = {233--264},
abstract = {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).},
doi = {10.1007/978-3-540-49556-7_15},
urlpdf = {Publications/ChyzakQuadratRobertz-2007-OSP.pdf}
}
@inproceedings{BostanChyzakLeRoux-2008-POD,
author = {Bostan, Alin and Chyzak, Frédéric and Le Roux, Nicolas},
title = {Products of ordinary differential operators by evaluation and interpolation},
booktitle = {ISSAC'08 (July 20--23, 2008, Hagenberg, Austria)},
year = {2008},
pages = {23--30},
publisher = {ACM},
note = {Conference proceedings},
abstract = {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.},
arxiv = {abs/0804.2181},
urlpdf = {Publications/BostanChyzakLeRoux-2008-POD.pdf}
}
@article{ChyzakDrmotaKlausnerKok-2008-DPR,
author = {Chyzak, Frédéric and Drmota, Michael and Klausner, Thomas and Kok, Gerard},
title = {The distribution of patterns in random trees},
journal = {Combinatorics, Probability \& Computing},
year = {2008},
volume = {17},
number = {1},
pages = {21--59},
abstract = {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$.},
urlpdf = {Publications/ChyzakDrmotaKlausnerKok-2008-DPR.pdf}
}
@unpublished{ChyzakPaule-2008-CA,
author = {Chyzak, Frédéric and Paule, Peter},
title = {Computer algebra},
note = {Draft of a methodological chapter for the NIST's Digital Library of Mathematical Functions. 40 pages},
year = {2008},
}
@misc{BostanChenChyzakLi-2009-RFT,
author = {Bostan, Alin and Chen, Shaoshi and Chyzak, Frédéric and Li, Ziming},
title = {Rational-functions telescopers: blending creative telescoping with {H}ermite reduction},
howpublished = {Poster at the conference ISSAC'09 (Seoul, South Korea)},
year = {2009},
urlpdf = {Publications/BostanChenChyzakLi-2009-RFT.pdf}
}
@inproceedings{ChyzakKauersSalvy-2009-NHS,
author = {Chyzak, Frédéric and Kauers, Manuel and Salvy, Bruno},
title = {A non-holonomic systems approach to special function identities},
booktitle = {ISSAC'09: Proceedings of the twenty-second international symposium on Symbolic and algebraic computation},
year = {2009},
editor = {May, John},
pages = {111--118},
abstract = {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.},
arxiv = {abs/0904.2761},
doi = {10.1145/1576702.1576720},
urlpdf = {Publications/ChyzakKauersSalvy-2009-NHS.pdf}
}
@inproceedings{BenoitChyzakDarrasseGerholdMezzarobbaSalvy-2010-DDMF,
author = {Benoit, Alexandre and Chyzak, Frédéric and Darrasse, Alexis and Gerhold, Stefan and Mezzarobba, Marc and Salvy, Bruno},
title = {The {D}ynamic {D}ictionary of {M}athematical {F}unctions ({DDMF})},
booktitle = {The Third International Congress on Mathematical Software (ICMS 2010)},
year = {2010},
editor = {Fukuda, Komei and van der Hoeven, Joris and Joswig, Michael and Takayama, Nobuki},
volume = {6327},
series = {Lecture Notes in Computer Science},
pages = {35--41},
abstract = {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.},
doi = {10.1007/978-3-642-15582-6_7},
urlpdf = {Publications/BenoitChyzakDarrasseGerholdMezzarobbaSalvy-2010-DDMF.pdf}
}
@inproceedings{BostanChenChyzakLi-2010-CCT,
author = {Bostan, Alin and Chen, Shaoshi and Chyzak, Frédéric and Li, Ziming},
title = {Complexity of creative telescoping for bivariate rational functions},
booktitle = {ISSAC'10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation},
year = {2010},
pages = {203--210},
address = {New York, NY, USA},
publisher = {ACM},
abstract = {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 \emph{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.},
doi = {http://doi.acm.org/10.1145/1837934.1837975},
urlpdf = {Publications/BostanChenChyzakLi-2010-CCT.pdf}
}
@article{BostanChyzakHoeijPech-2011-EFG,
author = {Bostan, Alin and Chyzak, Frédéric and van Hoeij, Mark and Pech, Lucien},
title = {Explicit formula for the generating series of diagonal {3D} rook paths},
journal = {Séminaire Lotharingien de Combinatoire},
year = {2011},
volume = {66},
number = {B66a},
pages = {1--27},
abstract = {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 \emph{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 . \]},
urlpdf = {Publications/BostanChyzakHoeijPech-2011-EFG.pdf}
}
@misc{BostanChyzakLiSalvy-2011-FCC,
author = {Bostan, Alin and Chyzak, Frédéric and Li, Ziming and Salvy, Bruno},
title = {Fast computation of common left multiples of linear ordinary differential operators},
howpublished = {Poster at ISSAC 2011},
month = jul,
year = {2011},
address = {New York, NY, USA},
doi = {http://doi.acm.org/10.1145/2016567.2016581},
journal = {ACM Commun. Comput. Algebra},
urlpdf = {Publications/BostanChyzakLiSalvy-2011-FCC.pdf},
pages = {111--112},
publisher = {ACM},
volume = {45}
}
@inproceedings{ChyzakDarrasse-2011-UCP,
author = {Chyzak, Frédéric and Darrasse, Alexis},
title = {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},
booktitle = {ICFP'11 (September 19--21, 2011, Tokyo, Japan)},
year = {2011},
editor = {Danvy, Olivier},
pages = {259--265},
publisher = {ACM},
note = {(An experience report.)},
abstract = {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.},
urlpdf = {Publications/ChyzakDarrasse-2011-UCP.pdf}
}
@inproceedings{ChyzakDavenportKoutschanSalvy-2011-KRD,
author = {Chyzak, Frédéric and Davenport, James H. and Koutschan, Christoph and Salvy, Bruno},
title = {On {K}ahan's rules for determining branch cuts},
booktitle = {SYNASC},
year = {2011},
pages = {47--51},
month = sep,
note = {13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. September 26-29, 2011. Timisoara, Romania},
abstract = {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.},
arxiv = {abs/1109.2809},
urlpdf = {Publications/ChyzakDavenportKoutschanSalvy-2011-KRD.pdf}
}
@inproceedings{BostanChyzakLiSalvy-2012-FCC,
author = {Bostan, Alin and Chyzak, Frédéric and Li, Ziming and Salvy, Bruno},
title = {Fast computation of common left multiples of linear ordinary differential operators},
booktitle = {ISSAC '12: Proceedings of the twenty-fifth International Symposium on Symbolic and Algebraic Computation},
year = {2012},
editor = {van Hoeij, Mark and van der Hoeven, Joris},
pages = {99--106},
abstract = {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.},
arxiv = {abs/1205.0879},
urlpdf = {Publications/BostanChyzakLiSalvy-2012-FCC.pdf}
}
@incollection{Chyzak-2012-CTP,
author = {Chyzak, Frédéric},
title = {Creative telescoping for parametrised integration and summation},
booktitle = {Journées Nationales de Calcul Formel 2011},
publisher = {Cedram},
year = {2012},
volume = {2},
number = {1},
series = {Les Cours du CIRM},
note = {37 pages. Lecture notes},
doi = {10.5802/ccirm.14},
urlpdf = {Publications/Chyzak-2012-CTP.pdf}
}
@incollection{BostanChenChyzakLiXin-2013-HRC,
author = {Bostan, Alin and Chen, Shaoshi and Chyzak, Frédéric and Li, Ziming and Xin, Guoce},
title = {Hermite reduction and creative telescoping for hyperexponential functions},
booktitle = {ISSAC 2013},
publisher = {ACM},
year = {2013},
pages = {77--84},
address = {New York},
abstract = {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 \emph{DEtools[Zeilberger]\/}. We also derive an order bound on minimal telescopers that is tighter than the known ones.},
urlpdf = {Publications/BostanChenChyzakLiXin-2013-HRC.pdf}
}
@incollection{BostanChyzakPanafieu-2013-CET,
author = {Bostan, Alin and Chyzak, Frédéric and de Panafieu, Élie},
title = {Complexity estimates for two uncoupling algorithms},
booktitle = {ISSAC 2013},
publisher = {ACM},
year = {2013},
pages = {85--92},
address = {New York},
abstract = {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\"urcher 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.},
urlpdf = {Publications/BostanChyzakPanafieu-2013-CET.pdf}
}
@phdthesis{Chyzak-2014-ACT,
author = {Chyzak, Frédéric},
title = {The {ABC} of Creative Telescoping: Algorithms, Bounds, Complexity},
school = {University Paris-Sud 11},
year = {2014},
type = {Memoir of accreditation to supervise research ({HDR})},
month = apr,
note = {64 pages},
urlpdf = {Publications/Chyzak-2014-ACT.pdf}
}
@inproceedings{ChyzakMahboubiSibutPinoteTassi-2014-CAB,
author = {Chyzak, Frédéric and Mahboubi, Assia and Sibut-Pinote, Thomas and Tassi, Enrico},
title = {A computer-algebra-based formal proof of the irrationality of~$\zeta(3)$},
booktitle = {Interactive Theorem Proving},
year = {2014},
editor = {Klein, Gerwin and Gamboa, Ruben},
number = {8558},
series = {Lecture Notes in Computer Science},
pages = {160--176},
address = {Vienna, Austria},
publisher = {Springer},
note = {Proceedings of 5th International Conference, ITP 2014, held as part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014},
abstract = {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.},
urlpdf = {Publications/ChyzakMahboubiSibutPinoteTassi-2014-CAB.pdf}
}
@article{ChenChyzakFengFuLi-2015-ETM,
author = {Chen, Shaoshi and Chyzak, Frédéric and Feng, Ruyong and Fu, Guofeng and Li, Ziming},
title = {On the existence of telescopers for mixed hypergeometric terms},
journal = {Journal of Symbolic Computation},
year = {2015},
volume = {68, Part 1},
pages = {1--26},
issn = {0747-7171},
abstract = {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.},
doi = {10.1016/j.jsc.2014.08.005},
mrclass = {68W30 (33F10)},
urlpdf = {Publications/ChenChyzakFengFuLi-2015-ETM.pdf}
}
@book{BostanChyzakGiustiLebretonLecerfSalvySchost-2017-AECF,
title = {Algorithmes Efficaces en Calcul Formel},
publisher = {Frédéric Chyzak (self-pub.)},
year = {2017},
author = {Bostan, Alin and Chyzak, Frédéric and Giusti, Marc and Lebreton, Romain and Lecerf, Grégoire and Salvy, Bruno and Schost, Éric},
address = {Palaiseau},
month = sep,
isbn = {979-10-699-0947-2},
note = {686 pages. Printed by CreateSpace. Also available in electronic format},
abstract = {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.},
url = {https://hal.archives-ouvertes.fr/AECF/}
}
@article{BostanChyzakHoeijKauersPech-2017-HEG,
author = {Bostan, Alin and Chyzak, Frédéric and van Hoeij, Mark and Kauers, Manuel and Pech, Lucien},
title = {Hypergeometric expressions for generating functions of walks with small steps in the quarter plane},
journal = {European Journal of Combinatorics},
year = {2017},
volume = {61},
pages = {242--275},
abstract = {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.},
doi = {10.1016/j.ejc.2016.10.010},
urlpdf = {Publications/BostanChyzakHoeijKauersPech-2016-HEG.pdf}
}
@article{ChyzakDreyfusDumasMezzarobba-2018-CSL,
author = {Chyzak, Frédéric and Dreyfus, Thomas and Dumas, Philippe and Mezzarobba, Marc},
title = {Computing solutions of linear {M}ahler equations},
journal = {Mathematics of Computation},
year = {2018},
volume = {87},
number = {314},
pages = {2977--3021},
doi = {https://doi.org/10.1090/mcom/3359},
abstract = {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.},
urlpdf = {Publications/ChyzakDreyfusDumasMezzarobba-2018-CSL.pdf}
}
@inproceedings{BostanChyzakLairezSalvy-2018-GHR,
author = {Bostan, Alin and Chyzak, Frédéric and Lairez, Pierre and Salvy, Bruno},
title = {Generalized {H}ermite reduction, creative telescoping and definite integration of {D}-finite functions},
booktitle = {ISSAC'18},
year = {2018},
editor = {Schost, Éric},
pages = {95--102},
publisher = {ACM Press},
abstract = {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.},
doi = {10.1145/3208976.3208992},
urlpdf = {Publications/BostanChyzakLairezSalvy-2018-GHR.pdf}
}
@article{BellChyzakCoonsDumas-2019-BCM,
author = {Bell, Jason P. and Chyzak, Frédéric and Coons, Michael and Dumas, Philippe},
title = {Becker's conjecture on {M}ahler functions},
journal = {Transactions of the American Mathematical Society},
year = 2019,
page = {3405--3423},
arxiv = {abs/1802.08653},
abstract = {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 $a_0(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^\gamma Q(z)$ for some explicit non-negative integer~$\gamma$ and such that $1/Q(z)$~is $k$-regular.},
urlpdf = {Publications/BellChyzakCoonsDumas-2019-BCM.pdf}
}
@article{ChyzakYeats-2020-BBL,
author = {Chyzak, Frédéric and Yeats, Karen},
title = {Bijections between {Ł}ukasiewicz walks and generalized tandem walks},
journal = {The Electronic Journal of Combinatorics},
volume = {27},
number = {2},
month = apr,
year = 2020,
note = {Article number P2.3. 46 pages. Implementation available at \url{https://arxiv.org/abs/1810.04117}},
abstract = {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.},
doi = {10.37236/8261},
urlpdf = {Publications/ChyzakYeats-2020-BBL.pdf}
}
@misc{ChyzakNielsen-2019-CFF,
author = {Chyzak, Frédéric and Nielsen, Frank},
title = {A closed-form formula for the {K}ullback-{L}eibler divergence between {C}auchy distributions},
howpublished = {\url{https://arxiv.org/abs/1905.10965}},
note = {8 pages},
month = may,
year = 2019,
abstract = {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.},
urlpdf = {Publications/ChyzakNielsen-2019-CFF.pdf}
}
@inproceedings{ChyzakDumas-2020-GBT,
author = {Chyzak, Frédéric and Dumas, Philippe},
title = {A {G}röbner-basis theory for divide-and-conquer recurrences},
booktitle = {ISSAC'20},
year = {2020},
editor = {Leykin, Anton},
pages = {99--106},
publisher = {ACM Press},
abstract = {Divide-and-conquer recurrences relate values of a given sequence at indices of the form $b^\ell n + r$ for fixed~$b\geq2$ and various pairs~$(\ell,r)$. Using systems of such recurrences makes it possible to express the behaviour of a quantity according to congruence classes modulo~$b^\ell$. 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.},
doi = {10.1145/3373207.3404055},
urlpdf = {Publications/ChyzakDumas-2020-GBT.pdf}
}
@article{BostanChyzakJimenezPastorLairez-2020-SPC,
author = {Bostan, Alin and Chyzak, Frédéric and Jiménez-Pastor, Antonio and Lairez, Pierre},
title = {The {S}age package \emph{comb\_walks} for walks in the quarter plane},
journal = {ACM Communications in Computer Algebra},
year = {2020},
volume = {54},
number = {2},
pages = {30--38},
month = sep,
note = {Software presentation at ISSAC '20},
abstract = {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.},
doi = {10.1145/3427218.3427220},
urlpdf = {Publications/BostanChyzakJimenezPastorLairez-2020-SPC.pdf}
}
@comment{{jabref-meta: databaseType:bibtex;}}
@comment{{jabref-meta: protectedFlag:true;}}
@comment{{jabref-meta: saveOrderConfig:specified;year;false;author;false;bibtexkey;false;}}
@inproceedings{ChyzakGoyerMezzarobba-2022-SNF,
author = {Chyzak, Frédéric and Goyer, Alexandre and Mezzarobba, Marc},
title = {Symbolic-numeric factorization of differential operators},
booktitle = {ISSAC'22},
year = {2022},
editor = {Lihong Zhi},
pages = {73--82},
publisher = {ACM Press},
abstract = {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.},
urlpdf = {Publications/ChyzakGoyerMezzarobba-2022-SNF.pdf}
}
@inproceedings{BostanChyzakNotarantonioSafeyElDin-2022-ADF,
author = {Bostan, Alin and Chyzak, Frédéric and Notarantonio, Hadrien and Safey El Din, Mohab},
title = {Algorithms for discrete differential equations of order~$1$},
booktitle = {ISSAC'22},
year = {2022},
editor = {Lihong Zhi},
pages = {101--110},
publisher = {ACM Press},
abstract = {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.},
urlpdf = {Publications/BostanChyzakNotarantonioSafeyElDin-2022-ADF.pdf}
}
@misc{BostanChyzakPilaud-2023-RPF,
author = {Bostan, Alin and Chyzak, Frédéric and Pilaud, Vincent},
title = {Refined product formulas for {T}amari intervals},
howpublished = {\url{https://arxiv.org/abs/1905.10965}},
month = mar,
year = {2023},
abstract = {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.},
urlpdf = {Publications/BostanChyzakPilaud-2023-RPF.pdf}
}
@unpublished{ChyzakDreyfusDumasMezzarobba-2024-FOF,
author = {Chyzak, Frédéric and Dreyfus, Thomas and Dumas, Philippe and Mezzarobba, Marc},
title = {First-order factors of linear {M}ahler operators},
note = {Preprint},
month = mar,
year = {2024},
abstract = {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.},
urlpdf = {Publications/ChyzakDreyfusDumasMezzarobba-2024-FOF.pdf}
}
This file was generated by bibtex2html.