| Welcome! | Research Topics | People | Publications | Seminars | Software | On-Line Applications | Jobs & Internships |
|
|
Frédéric Chyzak's Publications |
| Ore_algebra, Groebner, Mgfun, and Other Packages | Publications, Notes, and Slides |
| Manuscripts | Publications | Other | Slides, Movies, etc. |
@misc{BoChLiSa11,
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},
journal = {ACM Commun. Comput. Algebra},
year = {2011},
month = {July},
publisher = {ACM},
volume = {45},
address = {New York, NY, USA},
howpublished= {Poster at ISSAC 2011},
pages = {111–112},
doi = {http://doi.acm.org/10.1145/2016567.2016581},
url = {http://doi.acm.org/10.1145/2016567.2016581},
}
@article{Bostan-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ém. Loth. Comb.},
year = {2011},
volume = {B66a},
note = {27 pages},
url = {http://www.emis.de/journals/SLC/wpapers/s66bochhope.html},
abstract = {Let an 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 an xn admits the following explicit expression in terms of
a Gaussian hypergeometric function: G(x) = 1 + 6 ⋅ int _0^x frac
pFq 211/32/32 frac 27 w(2-3w)(1-4w)^3(1-4w)(1-64w) dw.
},
}
@inproceedings{Chyzak-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},
publisher = {ACM},
pages = {259–265},
note = {(An experience report.)},
url = {http://ddmf.msr-inria.inria.fr/download/DynaMoW-ICFP11.pdf},
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.},
}
@inproceedings{ChyzakDavenportKoutschanSalvy2011,
author = {Chyzak, Frédéric and Davenport, James H. and
Koutschan, Christoph and Salvy, Bruno},
title = {On Kahan's Rules for Determining Branch Cuts},
booktitle = {SYNASC},
year = {2011},
month = {September},
note = {5 pages. 13th International Symposium on Symbolic and
Numeric Algorithms for Scientific Computing. September 26-29, 2011.
Timisoara, Romania},
arxiv = {abs/1109.2809},
url = {http://arxiv.org/abs/1109.2809},
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.},
}
@inproceedings{BenoitChyzakDarrasseGerholdMezzarobbaSalvy2010,
author = {Benoit, Alexandre and Chyzak, Fr{\'e}d{\'e}ric and
Darrasse, Alexis and Gerhold, Stefan and Mezzarobba, Marc and Salvy, Bruno},
title = {The Dynamic Dictionary of Mathematical Functions
({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},
doi = {10.1007/978-3-642-15582-6_7},
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.},
}
@inproceedings{BoChChLi10,
author = {Bostan, Alin and Chen, Shaoshi and Chyzak, Fr\'{e}d\'{e}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},
publisher = {ACM},
address = {New York, NY, USA},
pages = {203--210},
doi = {http://doi.acm.org/10.1145/1837934.1837975},
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.},
}
@misc{BoChChLi09,
author = {Bostan, Alin and Chyzak, Frédéric and Chen, Shaoshi
and Li, Ziming},
title = {Rational-functions telescopers: Blending creative
telescoping with Hermite reduction},
year = {2009},
howpublished= {Poster at the conference ISSAC'09 (Seoul, South Korea)},
url = {http://issac2009.kias.re.kr/program_page.html#posters},
}
@inproceedings{ChyzakKauersSalvy2009,
author = {Chyzak, Fr{\'e}d{\'e}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},
doi = {10.1145/1576702.1576720},
arxiv = {abs/0904.2761},
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.},
}
@inproceedings{BoChLR08,
author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}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},
publisher = {ACM},
pages = {23--30},
note = {Conference proceedings},
arxiv = {abs/0804.2181},
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 that 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. This equivalence fails in positive
characteristic and we give an algorithm that multiplies differential
operators in nearly linear time when the characteristic is small. Theoretical
results are validated by intensive experiments.},
}
@article{ChDrKlKo07,
author = {Chyzak, Fr{\'e}d{\'e}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},
pages = {21--59},
doi = {10.1017/S0963548307008425},
arxiv = {abs/cs/0605019},
web-comment = {The 2004 version of this paper was incomplete and removed
from this list.},
abstract = {Let~$T_n$ denote the set of unrooted labeled trees of
size~$n$ and let~$M$ be a particular (finite, unlabeled) tree. Assuming that
every tree of~$T_n$ is equally likely, it is shown that the limiting
distribution as $n$~goes to infinity of the number of occurrences of~$M$ as
an induced subtree is asymptotically normal with mean value and variance
asymptotically equivalent to $\mu n$ and~$\sigma^2n$, respectively, where the
constants $\mu>0$ and~$\sigma\ge 0$ are computable.},
}
@inproceedings{BostanChyzakLecerfSalvySchost2007,
author = {Bostan, Alin and Chyzak, Fr\'ed\'eric and Lecerf,
Gr\'egoire and Salvy, Bruno and Schost, \'Eric},
title = {Differential equations for algebraic functions},
booktitle = {ISSAC'07: Proceedings of the 2007 international symposium
on Symbolic and algebraic computation},
year = {2007},
editor = {Brown, C. W.},
publisher = {ACM Press},
pages = {25--32},
doi = {10.1145/1277548.1277553},
arxiv = {cs.SC/0703121},
abstract = {It is classical that univariate algebraic functions satisfy
linear differential equations with polynomial coefficients. 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. We
deduce a fast algorithm for the expansion of algebraic series.},
}
@inproceedings{BoChOlSaScSe07,
author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Ollivier,
Fran{\c c}ois and Salvy, Bruno and Schost, {\'E}ric and Sedoglavic,
Alexandre},
title = {Fast computation of power series solutions of systems of
differential equations},
booktitle = {SODA'07},
year = {2007},
month = {January},
publisher = {Society for Industrial and Applied Mathematics},
pages = {1012--1021},
note = {Proceedings of the eighteenth annual ACM-SIAM symposium on
Discrete algorithms, New Orleans, Louisiana},
arxiv = {abs/cs/0604101},
abstract = {We propose new algorithms for the computation of the
first~$N$ terms of a vector (resp. a basis) of power series solutions of a
linear system of differential equations at an ordinary point, using a number
of arithmetic operations which 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 one and
two.},
}
@inproceedings{ChQuRo07,
author = {Chyzak, Fr\'ed\'eric and Quadrat, Alban and Robertz,
Daniel},
title = {{OreModules}: A symbolic package for the study of
multidimensional linear systems},
booktitle = {Applications of Time Delay Systems},
year = {2007},
editor = {Chiasson, J. and Loiseau, J. J.},
publisher = {Springer Berlin / Heidelberg},
volume = {352},
series = {Lecture Notes in Control and Information Sciences},
pages = {233--264},
note = {ISBN 978-3-540-49555-0},
doi = {10.1007/978-3-540-49556-7_15},
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\'ezout/Diophantine
equations).},
}
@inproceedings{BoChClSa06,
author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Cluzeau,
Thomas and Salvy, Bruno},
title = {Low Complexity Algorithms for Linear Recurrences},
booktitle = {ISSAC'06},
year = {2006},
editor = {Dumas, Jean-Guillaume},
publisher = {ACM Press},
pages = {31--38},
doi = {10.1145/1145768.1145781},
arxiv = {abs/cs/0605068},
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.},
}
@proceedings{Chyzak05,
title = {Algorithms Seminar, 2002--2004},
year = {2005},
month = {April},
editor = {Chyzak, Fr{\'e}d{\'e}ric},
volume = {5542},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
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.},
}
@incollection{ChPa05,
author = {Chyzak, Frédéric and Paule, Peter},
title = {Computer algebra},
booktitle = {Digital Library of Mathematical Functions},
year = {2005},
editor = {Lozier, Dan and Olver, Frank and Clark, Charles and
Boisvert, Ron},
publisher = {NIST},
note = {40 pages. Under the process of validation by NIST},
web-comment = {This ambitious project, DLMF, is managed by NIST and aims at
providing a new edition for the Handbook of Mathematical Functions,
an
authoritative handbook since 1962.},
abstract = {This chapter focuses on computer algebra techniques which
are tailored primarily for special function applications, that is, for
symbolic manipulation of expressions representing special functions and
sequences. The described methods are algorithms rather than formulas or
identities.},
}
Handbook of Mathematical Functions,an authoritative handbook since 1962.
@article{ChMiSa05,
author = {Chyzak, Fr\'ed\'eric and Mishna, Marni and Salvy, Bruno},
title = {Effective Scalar Products of {D}-finite Symmetric
Functions},
journal = {Journal of Combinatorial Theory, Series A},
number = {1},
year = {2005},
month = {October},
volume = {112},
pages = {1--43},
note = {Extended version of an article published in the proceedings
of the 14th Conference of Formal Power Series and Algebraic Combinatorics
FPSAC'02, Melbourne, July 2002},
doi = {10.1016/j.jcta.2005.01.001},
arxiv = {abs/math/0310132},
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.},
}
@article{ChQuRo05,
author = {Chyzak, Frédéric and Quadrat, Alban and Robertz,
Daniel},
title = {Effective algorithms for parametrizing linear control
systems over Ore algebras},
journal = {Applicable Algebra in Engineering, Communication and
Computing},
number = {5},
year = {2005},
month = {November},
publisher = {Springer Verlag},
volume = {16},
pages = {319–376},
doi = {10.1007/s00200-005-0188-6},
web-comment = {Preliminary
version (INRIA Research Report #5181).},
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), multidi mensional 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.},
}
@inproceedings{ChQuRo04,
author = {Frédéric Chyzak and Alban Quadrat and Daniel Robertz},
title = {OreModules, A symbolic package for the study of
multidimensional linear systems},
booktitle = {Sixteenth International Symposium on Mathematical Theory of
Networks and Systems},
year = {2004},
month = {July},
publisher = {Katholieke Universiteit Leuven},
address = {Leuven, Belgium},
note = {Proceedings MTNS2004, Katholieke Universiteit Leuven,
Belgium, July 5–9, 2004},
url = {http://www.mtns2004.be/database/papersubmission/upload/206.pdf},
web-comment = {More on the package web site.},
}
@inproceedings{BaChLR03,
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 (Journées de
Calcul Formel, Strasbourg, March 22-23, 2002)},
year = {2003},
editor = {Fauvet, F. and Mitschi, C.},
publisher = {de Gruyter},
volume = {3},
series = {IRMA Lectures in Mathematics and Theoretical Physics},
pages = {87–129},
note = {In French. ISBN 3-11-017875-3},
web-comment = {Preliminary
version.},
abstract = {(French) Dans cet article nous décrivons et comparons
différentes méthodes algorithmiques pour résoudre le problème suivant
: étant donnée une série hat f(x)= sum m geq 0umxm solution
d'une équation différentielle linéaire ordinaire et un nombre
entier r>0, construire une équation différentielle vérifiée par les
sous-séries hat fj(x)= sum m geq 0uj+mrxj+mr de ses termes de
r en r. Cette question apparaî t naturellement lors de l'implantation
en calcul formel des solutions formelles et de leurs (multi-)sommes. Les
méthodes proposées sont implantées en sc Maple et nous donnons
l'adresse des programmes correspondants.En appendice nous indiquons une
démarche constructive réaliste pour le calcul effectif des invariants
formels d'une équation ou d'un système. (English) 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 0umxm solution of an ordinary linear
differential equation and given an integer r geq 2 find a differential
equation satisfied by the sub-series hat fj(x)= sum _m geq
0uj+mrxj+mr. These methods have been implemented in sc 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.},
}
@proceedings{Chyzak03,
title = {Algorithms Seminar, 2001–2002},
year = {2003},
month = {November},
editor = {Chyzak, Frédéric},
volume = {5003},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr-5003.html},
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.},
}
@inproceedings{ChQuRo03,
author = {Chyzak, Frédéric and Quadrat, Alban and Robertz,
Daniel},
title = {Linear control systems over Ore algebras: effective
algorithms for the computation of parametrizations},
booktitle = {Time-Delay Systems},
year = {2003},
note = {Electronic proceedings of an IFAC Workshop,
INRIA-Roquencourt (France)},
url = {http://algo.inria.fr/chyzak/Publications/tds03.ps},
web-comment = {Conference web
site.},
}
@proceedings{Chyzak02,
title = {Algorithms Seminar, 2000–2001},
year = {2002},
month = {March},
editor = {Chyzak, Frédéric},
volume = {4406},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr-4406.html},
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.},
}
@inproceedings{ChMiSa02,
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},
month = {July},
publisher = {University of Melbourne},
address = {Melbourne, Australia},
pages = {19.1–19.12},
note = {Extended abstract. Proceedings FPSAC'02. An extended
version has appeared in [Chyzak et al., 2005a]},
web-comment = {Preliminary
version.},
abstract = {Many combinatorial generating functions can be extracted
from symmetric functions. 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. Examples of applications to
k-regular graphs and Young tableaux with repeated entries are given.},
}
@article{AtChDu01,
author = {Atallah, M. J. and Chyzak, F. and Dumas, P.},
title = {A randomized algorithm for approximate string matching},
journal = {Algorithmica},
number = {3},
year = {2001},
volume = {29},
pages = {468–486},
web-comment = {Preliminary
version (INRIA Research Report #3194).},
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.},
}
@article{ChPaScScZi01,
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},
number = {1},
year = {2001},
volume = {10},
pages = {67–86},
web-comment = {Preliminary
version.},
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.},
}
@techreport{Chyzak00a,
author = {Chyzak, Frédéric},
title = {About the non-minimality of the outputs of Zeilberger's
algorithm},
number = {00-08},
year = {2000},
month = {avril},
address = {Linz, Austria},
institution = {Austrian project SFB F013},
note = {Bruno Buchberger and Peter Paule, Eds. 20 pages},
url = {http://www.sfb013.uni-linz.ac.at/reports/2000/ps-files/sfb00-08.ps.gz},
web-comment = {This work is still at a preliminary stage and needs more
thoughts...},
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.},
}
@proceedings{Chyzak00c,
title = {Algorithms Seminar, 1999–2000},
year = {2000},
month = {November},
editor = {Chyzak, Frédéric},
volume = {4056},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr-4056.html},
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.},
}
@article{Chyzak00b,
author = {Frédéric Chyzak},
title = {An Extension of Zeilberger's Fast Algorithm to General
Holonomic Functions},
journal = {Discrete Mathematics},
number = {1-3},
year = {2000},
volume = {217},
pages = {115–134},
note = {Special issue Formal power series and algebraic
combinatorics (Vienna, 1997)},
url = {http://www.inria.fr/rrrt/rr-3195.html},
web-comment = {Preliminary version (INRIA Research Report #3195).},
abstract = {(English) 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. (French) Nous étendons
l'algorithme rapide de Zeilberger pour la sommation
hypergéométrique définie au cas des suites holonomes non
hypergéométriques. L'algorithme se généralise aussi au cas
différentiel et du q-calcul. Sa justification théorique se fonde sur
une description par opérateurs linéaires et sur la théorie de
l'holonomie.},
}
@article{ChGuPa99,
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},
web-comment = {Preliminary
version.},
abstract = {We predict the number of hexagonal systems consisting of 24
and 25 hexagons to be H24=122237774262384
and H25=606259305418149, with 6 and 5 significant digits, respectively.
Further estimates for Hn up to n=31 are also given.},
}
@phdthesis{Chyzak98,
author = {Frédéric Chyzak},
title = {Fonctions holonomes en calcul formel},
year = {1998},
school = {École polytechnique},
note = {INRIA, TU 0531. 227 pages.},
url = {http://algo.inria.fr/chyzak/Publications/these.ps},
abstract = {(French) Cette thèse montre comment le calcul
formel permet la manipulation d'une grande classe de suites et fonctions
solutions d'opérateurs linéaires, la classe des fonctions holonomes.
Celle-ci contient de nombreuses fonctions spéciales, en une ou plusieurs
variables, et de nombreuses suites de la combinatoire. Un cadre théorique
est tout d'abord introduit pour algorithmiser les propriétés de clôture
de la classe holonome, pour y permettre un test à zéro et pour
unifier les calculs différentiels sur les fonctions et les calculs de
récurrences sur les suites. Ces méthodes s'appuient sur des calculs par
une extension de la théorie des bases de Gröbner dans un cadre de
polynômes non commutatifs, les polynômes de Ore. Deux types d'algorithmes
de sommation et d'intégration symboliques définies et indéfinies sont
ensuite développés, dont la justification théorique fait appel à la
théorie des mathcal D-modules holonomes. Les premiers ont recours à
une élimination polynomiale non commutative par bases de Gröbner ; les
seconds à des algorithmes de résolution de systèmes fonctionnels
linéaires en leurs solutions fractions rationnelles. Bien plus que la
recherche de formes closes, l'objectif est de pouvoir continuer à calculer
avec la représentation implicite des objets holonomes même en l'absence
de formes explicites. Ce type de calculs permet en particulier la preuve
automatique d'identités sommatoires et intégrales. Une implantation de
ces algorithmes dans le système de calcul formel sc Maple a permis de
donner la première preuve automatique d'identités jusqu'à présent
inaccessibles par le calcul formel. (English) 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.},
}
@incollection{Chyzak98b,
author = {Frédéric Chyzak},
title = {Gröbner Bases, Symbolic Summation and Symbolic
Integration},
booktitle = {Gröbner Bases and Applications},
year = {1998},
editor = {B. Buchberger and F. Winkler},
publisher = {Cambridge University Press},
volume = {251},
series = {London Mathematical Society Lecture Notes Series},
pages = {32–60},
note = {Proceedings of the Conference 33 Years of Gröbner Bases,
ISBN 0-521-63298-6},
web-comment = {Preliminary
version (INRIA Research Report #3297). Errata.},
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.},
}
@article{ChSa98,
author = {Chyzak, Frédéric and Salvy, Bruno},
title = {Non-commutative Elimination in Ore Algebras Proves
Multivariate Holonomic Identities},
journal = {Journal of Symbolic Computation},
number = {2},
year = {1998},
month = {August},
volume = {26},
pages = {187–227},
doi = {10.1006/jsco.1998.0207},
web-comment = {See the accompanying Maple session and the errata.},
abstract = {Many computations involving special functions,
combinatorial sequences or theirq-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 -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.},
}
@inproceedings{Chyzak97,
author = {Chyzak, Frédéric},
title = {An Extension of Zeilberger's Fast Algorithm to General
Holonomic Functions},
booktitle = {Formal Power Series and Algebraic Combinatorics, 9th
Conference},
year = {1997},
organization= {Universität Wien},
pages = {172–183},
note = {Conference proceedings. Subsumed in [Chyzak, 2000c]},
web-comment = {Preliminary version (INRIA Research Report #3195).},
}
@mastersthesis{Chyzak95,
author = {Chyzak, Fr\'ed\'eric},
title = {Manipulations formelles d'op\'erateurs lin\'eaires et
calculs holonomes},
year = {1995},
month = {June},
school = {\'Ecole Polytechnique},
}
@techreport{Chyzak94,
author = {Frédéric Chyzak},
title = {Holonomic Systems and Automatic Proofs of Identities},
number = {2371},
year = {1994},
month = {October},
institution = {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr-2371.html},
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.},
}
@incollection{Chyzak:2003:FAP,
author = {Chyzak, Frédéric},
title = {Fast Algorithms for Polynomial Systems Solving},
booktitle = {Algorithms Seminar, 2001–2002},
number = {5003},
year = {2003},
editor = {Chyzak, F.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {33–36},
note = {Summary of a talk by A. Bostan},
url = {http://algo.inria.fr/seminars/sem01-02/bostan.ps},
}
@incollection{Chyzak:2002:EAA,
author = {Chyzak, Frédéric},
title = {Effective Algebraic Analysis in Linear Control Theory},
booktitle = {Algorithms Seminar, 2000–2001},
number = {4406},
year = {2002},
editor = {Chyzak, F.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {105–112},
note = {Summary of a talk by A. Quadrat},
url = {http://algo.inria.fr/seminars/sem00-01/quadrat.ps},
}
@incollection{Chyzak:2002:TCD,
author = {Chyzak, Frédéric},
title = {A Tutorial on Closed Difference Forms},
booktitle = {Algorithms Seminar, 2000–2001},
number = {4406},
year = {2002},
editor = {Chyzak, F.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {89–94},
note = {Summary of a talk by B. Zimmermann},
url = {http://algo.inria.fr/seminars/sem00-01/bzimmermann.ps},
}
@article{Chyzak:2001:DES,
author = {Chyzak, Frédéric and Bronstein, Manuel},
title = {Differential Equations, To Solve Or Not To Solve? /
Équations différentielles : résoudre ou manipuler ?},
journal = {INédit},
number = {27},
year = {2001},
url = {http://www.inria.fr/actualites/inedit/inedit27_partf.en.html},
}
@incollection{Chyzak:2000:EAN,
author = {Chyzak, Frédéric},
title = {Efficient Algorithms on Numbers, Polynomials, and Series},
booktitle = {Algorithms Seminar, 1999–2000},
number = {4056},
year = {2000},
editor = {Chyzak, F.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {43–46},
note = {Summary of a talk by P. Zimmermann},
url = {http://algo.inria.fr/seminars/sem99-00/zimmermann.ps},
}
@incollection{Chyzak:2000:TPS,
author = {Chyzak, Frédéric},
title = {Tutte Polynomials in Square Grids},
booktitle = {Algorithms Seminar, 1999–2000},
number = {4056},
year = {2000},
editor = {Chyzak, F.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {23–26},
note = {Summary of a talk by M. Noy},
url = {http://algo.inria.fr/seminars/sem99-00/noy2.ps},
}
@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},
number = {4056},
year = {2000},
editor = {Chyzak, F.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {57–63},
note = {Summary of a talk by R. Bomboy},
url = {http://algo.inria.fr/seminars/sem99-00/bomboy.ps},
}
@incollection{Chyzak:1999:CRD,
author = {Chyzak, Frédéric},
title = {Concrete Resolution of Differential Problems using
Tannakian Categories},
booktitle = {Algorithms Seminar, 1998–1999},
number = {3830},
year = {1999},
editor = {Salvy, B.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {43–48},
note = {Summary of a talk by J.-A. Weil},
url = {http://algo.inria.fr/seminars/sem98-99/weil.ps},
}
@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},
year = {1999},
note = {15 pages. Commissioned by some French administration but
actually no longer needed once written...},
url = {Publications/manipulations.ps},
}
@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},
number = {3504},
year = {1998},
editor = {Salvy, B.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {79–82},
note = {Summary of a talk by E. Pflügel},
url = {http://algo.inria.fr/seminars/sem97-98/pfluegel.ps},
}
@incollection{Chyzak:1997:AFD,
author = {Chyzak, Frédéric},
title = {Absolute Factorization of Differential Operators},
booktitle = {Algorithms Seminar, 1996–1997},
number = {3267},
year = {1997},
editor = {Salvy, B.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {33–36},
note = {Summary of a talk by J.-A. Weil},
url = {http://algo.inria.fr/seminars/sem96-97/weil.ps},
}
@incollection{Chyzak:1997:DEN,
author = {Chyzak, Frédéric},
title = {Differential Equations, Nested Forms and Star Products},
booktitle = {Algorithms Seminar, 1996–1997},
number = {3267},
year = {1997},
editor = {Salvy, B.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {41–44},
note = {Summary of a talk by J. Shackell},
url = {http://algo.inria.fr/seminars/sem96-97/shackell.ps},
}
@incollection{Chyzak:1996:MBM,
author = {Chyzak, Frédéric},
title = {Matrix-Based Methods for Solving Polynomial Systems},
booktitle = {Algorithms Seminar, 1995–1996},
number = {2992},
year = {1996},
month = {September},
editor = {Salvy, B.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {51–54},
note = {Summary of a talk by I. Émiris},
url = {http://algo.inria.fr/seminars/sem95-96/emiris.ps},
}
@incollection{Chyzak:1996:OPR,
author = {Chyzak, Frédéric},
title = {On a Problem of Rubel},
booktitle = {Algorithms Seminar, 1995–1996},
number = {2992},
year = {1996},
month = {September},
editor = {Salvy, B.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {59–62},
note = {Summary of a talk by J. Shackell},
url = {http://algo.inria.fr/seminars/sem95-96/shackell.ps},
}
@incollection{Chyzak:1996:ZOL,
author = {Chyzak, Frédéric},
title = {Zero-One Law for Maps},
booktitle = {Algorithms Seminar, 1995–1996},
number = {2992},
year = {1996},
month = {September},
editor = {Salvy, B.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {19–22},
note = {Summary of a talk by K. Compton},
url = {http://algo.inria.fr/seminars/sem95-96/compton.ps},
}
@incollection{Chyzak:1995:EIT,
author = {Chyzak, Frédéric},
title = {Effective Identity Testing in Extensions of Differential
Fields},
booktitle = {Algorithms Seminar, 1994–1995},
number = {2669},
year = {1995},
month = {October},
editor = {Salvy, B.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {47–50},
note = {Summary of a talk by A. Péladan-Germa},
url = {http://algo.inria.fr/seminars/sem94-95/peladan.ps},
}
@incollection{Chyzak:1995:PSL,
author = {Chyzak, Frédéric},
title = {Polynomial Solutions of Linear Operator Equations},
booktitle = {Algorithms Seminar, 1994–1995},
number = {2669},
year = {1995},
month = {October},
editor = {Salvy, B.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {31–34},
note = {Summary of a talk by M. Petkovsek},
url = {http://algo.inria.fr/seminars/sem94-95/petkovsek.ps},
}
@incollection{Chyzak:1994:PCD,
author = {Chyzak, Frédéric},
title = {Piecewise-Constant Derivative Systems and their Algorithmic
Properties},
booktitle = {Algorithms Seminar, 1993–1994},
number = {2381},
year = {1994},
month = {October},
editor = {Salvy, B.},
publisher = {INRIA},
series = {INRIA Research Report},
pages = {133–136},
note = {Summary of a talk by E. Asarin},
url = {http://algo.inria.fr/seminars/sem93-94/asarin.ps},
}