
@inproceedings{BostanChowdhuryLebretonSalvySchost2012,
author = {Bostan, Alin and Chowdhury, Muhammad F. I. and Lebreton,
Romain and Salvy, Bruno and Schost, {\'E}ric},
title = {Power Series Solutions of Singular (q)Differential
Equations},
booktitle = {ISSAC '12: Proceedings of the twentyfifth International
Symposium on Symbolic and Algebraic Computation},
year = {2012},
editor = {van Hoeij, Mark and Van der Hoeven, Joris},
pages = {107114},
arxiv = {abs/1205.3414},
abstract = {We provide algorithms computing power series solutions of a
large class of differential or $q$differential equations or systems. Their
number of arithmetic operations grows linearly with the precision, up to
logarithmic terms.},
}
Alin Bostan, Muhammad F. I. Chowdhury, Romain Lebreton,
Bruno Salvy, and Éric Schost
. —
Power series solutions of singular (q)differential equations. —
In Mark van Hoeij and Joris Van der Hoeven, editors,
ISSAC '12:
Proceedings of the twentyfifth International Symposium on Symbolic and
Algebraic Computation, pages 107–114, 2012. —
Reprint.
(
arXiv:abs/1205.3414)
We provide algorithms computing power series solutions of a
large class of differential or qdifferential equations or systems. Their
number of arithmetic operations grows linearly with the precision, up to
logarithmic terms.

@inproceedings{BostanChyzakLiSalvy2012,
author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}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 twentyfifth International
Symposium on Symbolic and Algebraic Computation},
year = {2012},
editor = {van Hoeij, Mark and van der Hoeven, Joris},
pages = {99106},
arxiv = {abs/1205.0879},
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.},
}
Alin Bostan, Frédéric Chyzak, Ziming Li, and Bruno
Salvy
. —
Fast computation of common left multiples of linear ordinary differential
operators. —
In Mark van Hoeij and Joris van der Hoeven, editors,
ISSAC '12:
Proceedings of the twentyfifth International Symposium on Symbolic and
Algebraic Computation, pages 99–106, 2012. —
Reprint.
(
arXiv:abs/1205.0879)
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.

@techreport{BostanRaschelSalvy2012,
author = {Bostan, Alin and Raschel, Kilian and Salvy, Bruno},
title = {Non{D}finite excursions in the quarter plane},
number = {1205.3300},
year = {2012},
institution = {arXiv},
arxiv = {abs/1205.3300},
abstract = {We prove that the sequence $(e^{\mathfrak{S}}_n)_{n\geq 0}$
of excursions in the quarter plane corresponding to a nonsingular step set
$\mathfrak{S}\subseteq{0,\pm 1}^2$ with infinite group does not satisfy any
nontrivial linear recurrence with polynomial coefficients. Accordingly, in
those cases, the trivariate generating function of the numbers of walks with
given length and prescribed ending point is not Dfinite. Moreover, we
display the asymptotics of $e^{\mathfrak{S}}_n$.},
}
Alin Bostan, Kilian Raschel, and Bruno Salvy
. —
NonDfinite excursions in the quarter plane. —
Technical Report n°1205.3300, arXiv, 2012.
(
arXiv:abs/1205.3300)
We prove that the sequence (e mathfrak Sn)n geq 0
of excursions in the quarter plane corresponding to a nonsingular step set
mathfrak S subseteq {0, pm 1}2 with infinite group does not satisfy any
nontrivial linear recurrence with polynomial coefficients. Accordingly, in
those cases, the trivariate generating function of the numbers of walks with
given length and prescribed ending point is not Dfinite. Moreover, we
display the asymptotics of e mathfrak Sn.

@article{PivoteauSalvySoria2012,
author = {Pivoteau, Carine and Salvy, Bruno and Soria, Mich{\`e}le},
title = {Algorithms for Combinatorial Structures: Wellfounded
systems and {N}ewton iterations},
journal = {Journal of Combinatorial Theory, Series A},
year = {2012},
volume = {119},
institution = {arXiv},
pages = {17111773},
keywords = {Species theory; analytic combinatorics; generating series;
complexity.},
note = {62 pages},
doi = {10.1016/j.jcta.2012.05.007},
arxiv = {abs/1109.2688},
abstract = {We consider systems of recursively defined combinatorial
structures. We give algorithms checking that these systems are well founded,
computing generating series and providing numerical values. Our framework is
an articulation of the constructible classes of Flajolet and Sedgewick with
Joyal's species theory. We extend the implicit species theorem to structures
of size zero. A quadratic iterative Newton method is shown to solve
wellfounded systems combinatorially. From there, truncations of the
corresponding generating series are obtained in quasioptimal complexity.
This iteration transfers to a numerical scheme that converges unconditionally
to the values of the generating series inside their disk of convergence.
These results provide important subroutines in random generation. Finally,
the approach is extended to combinatorial differential systems.},
}
Carine Pivoteau, Bruno Salvy, and Michèle
Soria
. —
Algorithms for combinatorial structures: Wellfounded systems and Newton
iterations. —
Journal of Combinatorial Theory, Series A, 119:1711–1773,
2012. —
62 pages,
Reprint.
(
arXiv:abs/1109.2688)
(
doi:10.1016/j.jcta.2012.05.007)
We consider systems of recursively defined combinatorial
structures. We give algorithms checking that these systems are well founded,
computing generating series and providing numerical values. Our framework is
an articulation of the constructible classes of Flajolet and Sedgewick with
Joyal's species theory. We extend the implicit species theorem to structures
of size zero. A quadratic iterative Newton method is shown to solve
wellfounded systems combinatorially. From there, truncations of the
corresponding generating series are obtained in quasioptimal complexity.
This iteration transfers to a numerical scheme that converges unconditionally
to the values of the generating series inside their disk of convergence.
These results provide important subroutines in random generation. Finally,
the approach is extended to combinatorial differential
systems.

@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},
}

@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},
pages = {47–51},
note = {13th International Symposium on Symbolic and Numeric
Algorithms for Scientific Computing. September 2629, 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.},
}
Frédéric Chyzak, James H. Davenport, Christoph
Koutschan, and Bruno Salvy
. —
On Kahan's rules for determining
branch cuts. —
In
SYNASC, pages 47–51, September 2011. —
13th International Symposium on Symbolic and Numeric Algorithms for Scientific
Computing. September 2629, 2011. Timisoara, Romania.
(
arXiv:abs/1109.2809)
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.

@article{DumasFousseSalvy2011,
author = {Dumas, JeanGuillaume and Fousse, Laurent and Salvy,
Bruno},
title = {Simultaneous modular reduction and {K}ronecker substitution
for small finite fields},
journal = {Journal of Symbolic Computation},
number = {7},
year = {2011},
month = {July},
volume = {46},
pages = {823840},
keywords = {Compressed matrix multiplication},
doi = {10.1016/j.jsc.2010.08.015},
abstract = {We present algorithms to perform modular polynomial
multiplication or a modular dot product efficiently in a single machine word.
We use a combination of techniques. Polynomials are packed into integers by
Kronecker substitution; several modular operations are performed at once with
machine integer or floating point arithmetic; normalization of modular images
is avoided when possible; some conversions back to polynomial coefficients
are avoided; the coefficients are recovered efficiently by preparing them
before conversion. We discuss precisely the required control on sizes and
degrees. We then present applications to polynomial multiplication, prime
field linear algebra and small extension field arithmetic, where these
techniques lead to practical gains of quite large constant factors.},
}
JeanGuillaume Dumas, Laurent Fousse, and Bruno
Salvy
. —
Simultaneous modular reduction and Kronecker substitution for small finite
fields. —
Journal of Symbolic Computation, 46 n°7:823–840, July
2011. —
Reprint.
(
doi:10.1016/j.jsc.2010.08.015)
We present algorithms to perform modular polynomial
multiplication or a modular dot product efficiently in a single machine word.
We use a combination of techniques. Polynomials are packed into integers by
Kronecker substitution; several modular operations are performed at once with
machine integer or floating point arithmetic; normalization of modular images
is avoided when possible; some conversions back to polynomial coefficients
are avoided; the coefficients are recovered efficiently by preparing them
before conversion. We discuss precisely the required control on sizes and
degrees. We then present applications to polynomial multiplication, prime
field linear algebra and small extension field arithmetic, where these
techniques lead to practical gains of quite large constant
factors.

@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 = {3541},
doi = {10.1007/9783642155826_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.},
}
Alexandre Benoit, Frédéric Chyzak, Alexis Darrasse,
Stefan Gerhold, Marc Mezzarobba, and Bruno Salvy
. —
The dynamic dictionary of mathematical functions (DDMF). —
In Komei Fukuda, Joris van der Hoeven, Michael Joswig, and Nobuki Takayama,
editors,
The Third International Congress on Mathematical Software
(ICMS 2010),
Lecture Notes in Computer Science, vol.
6327, pages 35–41, 2010. —
Reprint.
(
doi:10.1007/9783642155826_7)
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.

@article{BostanSalvySchost2010,
author = {Bostan, Alin and Salvy, Bruno and Schost, {\'E}ric},
title = {Fast conversion algorithms for orthogonal polynomials},
journal = {Linear Algebra and its Applications},
number = {1},
year = {2010},
month = {January},
volume = {432},
pages = {249258},
doi = {10.1016/j.laa.2009.08.002},
arxiv = {abs/0804.2373},
abstract = {We discuss efficient conversion algorithms for orthogonal
polynomials. We describe a known conversion algorithm from an arbitrary
orthogonal basis to the monomial basis, and deduce a new algorithm of the
same complexity for the converse operation.},
}
Alin Bostan, Bruno Salvy, and Éric Schost
. —
Fast conversion algorithms for orthogonal polynomials. —
Linear Algebra and its Applications, 432 n°1:249–258,
January 2010. —
Reprint.
(
arXiv:abs/0804.2373)
(
doi:10.1016/j.laa.2009.08.002)
We discuss efficient conversion algorithms for orthogonal
polynomials. We describe a known conversion algorithm from an arbitrary
orthogonal basis to the monomial basis, and deduce a new algorithm of the
same complexity for the converse operation.

@article{BostanSalvyTran2010,
author = {Bostan, Alin and Salvy, Bruno and Tran, Khang},
title = {Generating functions of {C}hebyshevlike polynomials},
journal = {International Journal of Number Theory},
number = {7},
year = {2010},
volume = {6},
pages = {16591667},
doi = {10.1142/S1793042110003691},
arxiv = {abs/0907.0291},
abstract = {In this short note, we give simple proofs of several
results and conjectures formulated by Stolarsky and Tran concerning
generating functions of some families of Chebyshevlike polynomials.},
}
Alin Bostan, Bruno Salvy, and Khang Tran
. —
Generating functions of Chebyshevlike polynomials. —
International Journal of Number Theory, 6 n°7:1659–1667,
2010.
(
arXiv:abs/0907.0291)
(
doi:10.1142/S1793042110003691)
In this short note, we give simple proofs of several
results and conjectures formulated by Stolarsky and Tran concerning
generating functions of some families of Chebyshevlike
polynomials.

@article{FlajoletGerholdSalvy2010,
author = {Flajolet, Philippe and Gerhold, Stefan and Salvy, Bruno},
title = {Lindelöf Representations and (Non)Holonomic
Sequences},
journal = {The Electronic Journal of Combinatorics},
number = {1},
year = {2010},
volume = {17},
pages = {1–28},
arxiv = {abs/0906.1957},
url = {http://www.combinatorics.org/Volume_17/PDF/v17i1r3.pdf},
abstract = {Various sequences that possess explicit analytic
expressions can be analysed asymptotically through integral representations
due to Lindelöf, which belong to an attractive but largely forgotten
chapter of complex analysis. One of the outcomes of such analyses concerns
the nonexistence of linear recurrences with polynomial coefficients
annihilating these sequences, and, accordingly, the nonexistence of linear
differential equations with polynomial coefficients annihilating their
generating functions. In particular, the corresponding generating functions
are transcendental. Asymptotics of certain finite difference sequences come
out as a byproduct of our approach.},
}
Philippe Flajolet, Stefan Gerhold, and Bruno
Salvy
. —
Lindelöf
representations and (non)holonomic sequences. —
The Electronic Journal of Combinatorics, 17 n°1:1–28,
2010.
(
arXiv:abs/0906.1957)
Various sequences that possess explicit analytic
expressions can be analysed asymptotically through integral representations
due to Lindelöf, which belong to an attractive but largely forgotten
chapter of complex analysis. One of the outcomes of such analyses concerns
the nonexistence of linear recurrences with polynomial coefficients
annihilating these sequences, and, accordingly, the nonexistence of linear
differential equations with polynomial coefficients annihilating their
generating functions. In particular, the corresponding generating functions
are transcendental. Asymptotics of certain finite difference sequences come
out as a byproduct of our approach.

@article{MezzarobbaSalvy2010,
author = {Mezzarobba, Marc and Salvy, Bruno},
title = {Effective Bounds for {P}Recursive Sequences},
journal = {Journal of Symbolic Computation},
number = {10},
year = {2010},
month = {October},
volume = {45},
pages = {10751096},
doi = {10.1016/j.jsc.2010.06.024},
arxiv = {abs/0904.2452},
abstract = {We describe an algorithm that takes as input a complex
sequence $(u_n)$ given by a linear recurrence relation with polynomial
coefficients along with initial values, and outputs a simple explicit upper
bound $(v_n)$ such that $u_n \leq v_n$ for all $n$. Generically, the bound
is tight, in the sense that its asymptotic behaviour matches that of $u_n$.
We discuss applications to the evaluation of power series with guaranteed
precision.},
}
Marc Mezzarobba and Bruno Salvy
. —
Effective bounds for Precursive sequences. —
Journal of Symbolic Computation, 45 n°10:1075–1096,
October 2010. —
Reprint.
(
arXiv:abs/0904.2452)
(
doi:10.1016/j.jsc.2010.06.024)
We describe an algorithm that takes as input a complex
sequence (un) given by a linear recurrence relation with polynomial
coefficients along with initial values, and outputs a simple explicit upper
bound (vn) such that un leq vn for all n. Generically, the bound
is tight, in the sense that its asymptotic behaviour matches that of un.
We discuss applications to the evaluation of power series with guaranteed
precision.

@article{SalvyShackell2010,
author = {Salvy, Bruno and Shackell, John},
title = {Measured limits and multiseries},
journal = {Journal of the London Mathematical Society},
number = {3},
year = {2010},
volume = {82},
pages = {747–762},
doi = {10.1112/jlms/jdq057},
url = {http://jlms.oxfordjournals.org/content/82/3/747},
abstract = {We introduce the notion of a measured limit and show how it
can give meaning to asymptotic expansions in which the coefficients are
variable and may even have poles. We give an algorithm for computing the
measured multiseries of a large class of elementary functions.},
}
Bruno Salvy and John Shackell
. —
Measured limits and
multiseries. —
Journal of the London Mathematical Society, 82
n°3:747–762, 2010. —
Reprint.
(
doi:10.1112/jlms/jdq057)
We introduce the notion of a measured limit and show how it
can give meaning to asymptotic expansions in which the coefficients are
variable and may even have poles. We give an algorithm for computing the
measured multiseries of a large class of elementary
functions.

@inproceedings{BenoitSalvy2009,
author = {Benoit, Alexandre and Salvy, Bruno},
title = {Chebyshev Expansions for Solutions of Linear Differential
Equations},
booktitle = {ISSAC '09: Proceedings of the twentysecond international
symposium on Symbolic and algebraic computation},
year = {2009},
editor = {May, John},
pages = {2330},
doi = {10.1145/1576702.1576709},
arxiv = {abs/0906.2888},
abstract = {A Chebyshev expansion is a series in the basis of Chebyshev
polynomials of the first kind. When such a series solves a linear
differential equation, its coefficients satisfy a linear recurrence equation.
We interpret this equation as the numerator of a fraction of linear
recurrence operators. This interpretation lets us give a simple view of
previous algorithms, analyze their complexity, and design a faster one for
large orders.},
}
Alexandre Benoit and Bruno Salvy
. —
Chebyshev expansions for solutions of linear differential equations. —
In John May, editor,
ISSAC '09: Proceedings of the twentysecond
international symposium on Symbolic and algebraic computation, pages
23–30, 2009. —
Reprint.
(
arXiv:abs/0906.2888)
(
doi:10.1145/1576702.1576709)
A Chebyshev expansion is a series in the basis of Chebyshev
polynomials of the first kind. When such a series solves a linear
differential equation, its coefficients satisfy a linear recurrence equation.
We interpret this equation as the numerator of a fraction of linear
recurrence operators. This interpretation lets us give a simple view of
previous algorithms, analyze their complexity, and design a faster one for
large orders.

@inproceedings{ChyzakKauersSalvy2009,
author = {Chyzak, Fr{\'e}d{\'e}ric and Kauers, Manuel and Salvy,
Bruno},
title = {A NonHolonomic Systems Approach to Special Function
Identities},
booktitle = {ISSAC '09: Proceedings of the twentysecond international
symposium on Symbolic and algebraic computation},
year = {2009},
editor = {May, John},
pages = {111118},
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.},
}
Frédéric Chyzak, Manuel Kauers, and Bruno
Salvy
. —
A nonholonomic systems approach to special function identities. —
In John May, editor,
ISSAC '09: Proceedings of the twentysecond
international symposium on Symbolic and algebraic computation, pages
111–118, 2009. —
Reprint.
(
arXiv:abs/0904.2761)
(
doi:10.1145/1576702.1576720)
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.

@article{CloteKranakisKrizancSalvy2009,
author = {Clote, Peter and Kranakis, Evangelos and Krizanc, Danny and
Salvy, Bruno},
title = {Asymptotics of Canonical and Saturated RNA Secondary
Structures},
journal = {Journal of Bioinformatics and Computational Biology},
number = {5},
year = {2009},
month = {October},
volume = {7},
pages = {869–893},
doi = {10.1142/S0219720009004333},
arxiv = {abs/0908.4003},
url = {http://www.worldscinet.com/jbcb/07/0705/S0219720009004333.html},
abstract = {It is a classical result of Stein and Waterman that the
asymptotic number of RNA secondary structures is 1.104366 ⋅
n3/2⋅ 2.618034n. In this paper, we study combinatorial asymptotics
for two special subclasses of RNA secondary structures — canonical and
saturated structures. Canonical secondary structures are defined to have no
lonely (isolated) base pairs. This class of secondary structures was
introduced by Bompfünewerer et al., who noted that the run time of Vienna
RNA Package is substantially reduced when restricting computations to
canonical structures. Here we provide an explanation for the speedup, by
proving that the asymptotic number of canonical RNA secondary structures is
2.1614 ⋅ n3/2 ⋅ 1.96798n and that the expected number of base
pairs in a canonical secondary structure is 0.31724 ⋅ n. The asymptotic
number of canonical secondary structures was obtained much earlier by
Hofacker, Schuster and Stadler using a different method. Saturated secondary
structures have the property that no base pairs can be added without
violating the definition of secondary structure (i.e. introducing a
pseudoknot or base triple). Here we show that the asymptotic number of
saturated structures is 1.07427 ⋅ n3/2⋅ 2.35467n, the
asymptotic expected number of base pairs is 0.337361⋅ n, and the
asymptotic number of saturated stemloop structures is 0.323954 ⋅
1.69562n, in contrast to the number 2n  2 of (arbitrary) stemloop
structures as classically computed by Stein and Waterman. Finally, we apply
the work of Drmota to show that the density of states for [all resp.
canonical resp. saturated] secondary structures is asymptotically Gaussian.
We introduce a stochastic greedy method to sample random saturated
structures, called quasirandom saturated structures, and show that the
expected number of base pairs is 0.340633 ⋅ n.},
}
Peter Clote, Evangelos Kranakis, Danny Krizanc, and Bruno
Salvy
. —
Asymptotics of canonical and saturated rna secondary structures. —
Journal of Bioinformatics and Computational Biology, 7
n°5:869–893, October 2009. —
Reprint.
(
arXiv:abs/0908.4003)
(
doi:10.1142/S0219720009004333)
It is a classical result of Stein and Waterman that the
asymptotic number of RNA secondary structures is 1.104366 ⋅
n3/2⋅ 2.618034n. In this paper, we study combinatorial asymptotics
for two special subclasses of RNA secondary structures — canonical and
saturated structures. Canonical secondary structures are defined to have no
lonely (isolated) base pairs. This class of secondary structures was
introduced by Bompfünewerer et al., who noted that the run time of Vienna
RNA Package is substantially reduced when restricting computations to
canonical structures. Here we provide an explanation for the speedup, by
proving that the asymptotic number of canonical RNA secondary structures is
2.1614 ⋅ n3/2 ⋅ 1.96798n and that the expected number of base
pairs in a canonical secondary structure is 0.31724 ⋅ n. The asymptotic
number of canonical secondary structures was obtained much earlier by
Hofacker, Schuster and Stadler using a different method. Saturated secondary
structures have the property that no base pairs can be added without
violating the definition of secondary structure (i.e. introducing a
pseudoknot or base triple). Here we show that the asymptotic number of
saturated structures is 1.07427 ⋅ n3/2⋅ 2.35467n, the
asymptotic expected number of base pairs is 0.337361⋅ n, and the
asymptotic number of saturated stemloop structures is 0.323954 ⋅
1.69562n, in contrast to the number 2n  2 of (arbitrary) stemloop
structures as classically computed by Stein and Waterman. Finally, we apply
the work of Drmota to show that the density of states for [all resp.
canonical resp. saturated] secondary structures is asymptotically Gaussian.
We introduce a stochastic greedy method to sample random saturated
structures, called quasirandom saturated structures, and show that the
expected number of base pairs is 0.340633 ⋅ n.

@article{BorweinSalvy2008,
author = {Borwein, Jonathan M. and Salvy, Bruno},
title = {A proof of a recursion for {B}essel moments},
journal = {Experimental Mathematics},
number = {2},
year = {2008},
volume = {17},
pages = {223230},
arxiv = {abs/0706.1409},
abstract = {We provide a proof of a conjecture in (Bailey, Borwein,
Borwein, Crandall 2007) on the existence and form of linear recursions for
moments of powers of the Bessel function $K_0$.},
}
Jonathan M. Borwein and Bruno Salvy
. —
A proof of a recursion for Bessel moments. —
Experimental Mathematics, 17 n°2:223–230, 2008.
(
arXiv:abs/0706.1409)
We provide a proof of a conjecture in (Bailey, Borwein,
Borwein, Crandall 2007) on the existence and form of linear recursions for
moments of powers of the Bessel function K0.

@article{BoMoSaSc08,
author = {Bostan, Alin and Morain, Fran\c{c}ois and Salvy, Bruno and
Schost, {\'E}ric},
title = {Fast algorithms for computing isogenies between elliptic
curves},
journal = {Mathematics of Computation},
number = {263},
year = {2008},
month = {July},
volume = {77},
pages = {17551778},
doi = {10.1090/S0025571808020668},
arxiv = {abs/cs/0609020},
abstract = {We survey algorithms for computing isogenies between
elliptic curves defined over a field of characteristic either 0 or a large
prime. We introduce a new algorithm that computes an isogeny of degree $\ell$
($\ell$ different from the characteristic) in time quasilinear with respect
to $\ell$. This is based in particular on fast algorithms for power series
expansion of the Weierstrass $\wp$function and related functions.},
}
Alin Bostan, François Morain, Bruno Salvy, and Éric
Schost
. —
Fast algorithms for computing isogenies between elliptic curves. —
Mathematics of Computation, 77 n°263:1755–1778, July
2008. —
Reprint.
(
arXiv:abs/cs/0609020)
(
doi:10.1090/S0025571808020668)
We survey algorithms for computing isogenies between
elliptic curves defined over a field of characteristic either 0 or a large
prime. We introduce a new algorithm that computes an isogeny of degree l
(l different from the characteristic) in time quasilinear with respect
to l. This is based in particular on fast algorithms for power series
expansion of the Weierstrass ℘function and related
functions.

@inproceedings{BostanSalvySchost2008,
author = {Bostan, Alin and Salvy, Bruno and Schost, {\'E}ric},
title = {Power Series Composition and Change of Basis},
booktitle = {ISSAC'08: Proceedings of the twentyfirst international
symposium on Symbolic and algebraic computation},
year = {2008},
editor = {Jeffrey, David J.},
publisher = {ACM Press},
pages = {269276},
doi = {10.1145/1390768.1390806},
arxiv = {abs/0804.2337},
abstract = {Efficient algorithms are known for many operations on
truncated power series (multiplication, powering, exponential,...).
Composition is a more complex task. We isolate a large class of power series
for which composition can be performed efficiently. We deduce fast algorithms
for converting polynomials between various bases, including Euler, Bernoulli,
Fibonacci, and the orthogonal Laguerre, Hermite, Jacobi, Krawtchouk, Meixner
and MeixnerPollaczek.},
}
Alin Bostan, Bruno Salvy, and Éric Schost
. —
Power series composition and change of basis. —
In David J. Jeffrey, editor,
ISSAC'08: Proceedings of the twentyfirst
international symposium on Symbolic and algebraic computation, pages
269–276. ACM Press, 2008. —
Reprint.
(
arXiv:abs/0804.2337)
(
doi:10.1145/1390768.1390806)
Efficient algorithms are known for many operations on
truncated power series (multiplication, powering, exponential,...).
Composition is a more complex task. We isolate a large class of power series
for which composition can be performed efficiently. We deduce fast algorithms
for converting polynomials between various bases, including Euler, Bernoulli,
Fibonacci, and the orthogonal Laguerre, Hermite, Jacobi, Krawtchouk, Meixner
and MeixnerPollaczek.

@inproceedings{DuFoSa08,
author = {Dumas, JeanGuillaume and Fousse, Laurent and Salvy,
Bruno},
title = {Compressed Modular Matrix Multiplication},
booktitle = {Milestones in Computer Algebra (MICA 2008)},
year = {2008},
month = {May},
editor = {Moreno Maza, Marc and Watt, Stephen M.},
note = {Proceedings of a conference in honour of Keith Geddes' 60th
birthday. Stonehaven Bay, Trinidad and Tobago, 13 May 2008},
arxiv = {abs/0803.1975},
url = {http://algo.inria.fr/papers/pdf/DumasFousseSalvy2008.pdf},
abstract = {Matrices of integers modulo a small prime can be compressed
by storing several entries into a single machine word. Modular addition is
performed by addition and possibly subtraction of a word containing several
times the modulo. We show how modular multiplication can also be performed.
In terms of arithmetic operations, the gain over classical matrix
multiplication is equal to the number of integers that are stored inside a
machine word. The gain in actual speed is also close to that number. First,
modular dot product can be performed via an integer multiplication by the
reverse integer. Modular multiplication by a word containing a single residue
is also possible. We give bounds on the sizes of primes and matrices for
which such a compression is possible. We also make explicit the details of
the required compressed arithmetic routines and show some practical
performance.},
}
JeanGuillaume Dumas, Laurent Fousse, and Bruno
Salvy
. —
Compressed
modular matrix multiplication. —
In Marc Moreno Maza and Stephen M. Watt, editors,
Milestones in Computer
Algebra (MICA 2008), May 2008. —
Proceedings of a conference in honour of Keith Geddes' 60th birthday.
Stonehaven Bay, Trinidad and Tobago, 13 May 2008.
(
arXiv:abs/0803.1975)
Matrices of integers modulo a small prime can be compressed
by storing several entries into a single machine word. Modular addition is
performed by addition and possibly subtraction of a word containing several
times the modulo. We show how modular multiplication can also be performed.
In terms of arithmetic operations, the gain over classical matrix
multiplication is equal to the number of integers that are stored inside a
machine word. The gain in actual speed is also close to that number. First,
modular dot product can be performed via an integer multiplication by the
reverse integer. Modular multiplication by a word containing a single residue
is also possible. We give bounds on the sizes of primes and matrices for
which such a compression is possible. We also make explicit the details of
the required compressed arithmetic routines and show some practical
performance.

@article{GoSa08,
author = {Gomez, Claude and Salvy, Bruno},
title = {Calcul Formel},
journal = {Les Techniques de l'Ing{\'e}nieur},
year = {2008},
volume = {Dossier AF1460},
pages = {120},
}
Claude Gomez and Bruno Salvy
. —
Calcul formel. —
Les Techniques de l'Ingénieur, Dossier AF1460:1–20, 2008. —
Reprint.

@inproceedings{PivoteauSalvySoria2008,
author = {Pivoteau, Carine and Salvy, Bruno and Soria, Michèle},
title = {Boltzmann Oracle for Combinatorial Systems},
booktitle = {Algorithms, Trees, Combinatorics and Probabilities},
year = {2008},
publisher = {Discrete Mathematics and Theoretical Computer Science},
pages = {475–488},
note = {Proceedings of the Fifth Colloquium on Mathematics and
Computer Science. Blaubeuren, Germany. September 2226, 2008},
url = {http://www.dmtcs.org/dmtcsojs/index.php/proceedings/article/view/dmAI0132},
abstract = {Boltzmann random generation applies to welldefined systems
of recursive combinatorial equations. It relies on oracles giving values of
the enumeration generating series inside their disk of convergence. We show
that the combinatorial systems translate into numerical iteration schemes
that provide such oracles. In particular, we give a fast oracle based on
Newton iteration.},
}
Carine Pivoteau, Bruno Salvy, and Michèle
Soria
. —
Boltzmann oracle for combinatorial systems. —
In
Algorithms, Trees, Combinatorics and Probabilities, pages
475–488. Discrete Mathematics and Theoretical Computer Science, 2008. —
Proceedings of the Fifth Colloquium on Mathematics and Computer Science.
Blaubeuren, Germany. September 2226, 2008.
Boltzmann random generation applies to welldefined systems
of recursive combinatorial equations. It relies on oracles giving values of
the enumeration generating series inside their disk of convergence. We show
that the combinatorial systems translate into numerical iteration schemes
that provide such oracles. In particular, we give a fast oracle based on
Newton iteration.

@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 = {2532},
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.},
}
Alin Bostan, Frédéric Chyzak, Grégoire Lecerf, Bruno
Salvy, and Éric Schost
. —
Differential equations for algebraic functions. —
In C. W. Brown, editor,
ISSAC'07: Proceedings of the 2007 international
symposium on Symbolic and algebraic computation, pages 25–32. ACM
Press, 2007. —
Reprint.
(
arXiv:cs.SC/0703121)
(
doi:10.1145/1277548.1277553)
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 = {10121021},
note = {Proceedings of the eighteenth annual ACMSIAM 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 quasilinear with respect to~$N$. Similar
results are also given in the nonlinear case. This extends previous results
obtained by Brent and Kung for scalar differential equations of order one and
two.},
}
Alin Bostan, Frédéric Chyzak, François
Ollivier, Bruno Salvy, Éric Schost, and Alexandre Sedoglavic
. —
Fast computation of power series solutions of systems of differential
equations. —
In
SODA'07, pages 1012–1021. Society for Industrial and Applied
Mathematics, January 2007. —
Proceedings of the eighteenth annual ACMSIAM symposium on Discrete algorithms,
New Orleans, Louisiana,
Reprint.
(
arXiv:abs/cs/0604101)
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 quasilinear with respect to N. Similar
results are also given in the nonlinear case. This extends previous results
obtained by Brent and Kung for scalar differential equations of order one and
two.

@article{GiLeSaYa07,
author = {Giusti, Marc and Lecerf, Gr{\'e}goire and Salvy, Bruno and
Yakoubsohn, JeanClaude},
title = {On Location and Approximation of Clusters of Zeroes: Case
of Embedding Dimension One},
journal = {Foundations of Computational Mathematics},
number = {1},
year = {2007},
month = {February},
volume = {7},
pages = {158},
doi = {10.1007/s1020800401595},
abstract = {Isolated multiple zeros or clusters of zeros of analytic
maps with several variables are known to be difficult to locate and
approximate. This article is in the vein of the $\alpha$theory, initiated by
M.~Shub and S.~Smale in the beginning of the eighties. This theory restricts
to simple zeros, i.e., where the map has corank zero. In this article we deal
with situations where the analytic map has corank one at the multiple
isolated zero, which has embedding dimension one in the frame of deformation
theory. These situations are the least degenerate ones and therefore most
likely to be of practical significance. More generally, we define clusters of
embedding dimension one. We provide a criterion for locating such clusters of
zeros and a fast algorithm for approximating them, with quadratic
convergence. In case of a cluster with positive diameter our algorithm stops
at a distance of the cluster which is about its diameter.},
}
Marc Giusti, Grégoire Lecerf, Bruno Salvy, and
JeanClaude Yakoubsohn
. —
On location and approximation of clusters of zeroes: Case of embedding
dimension one. —
Foundations of Computational Mathematics, 7 n°1:1–58,
February 2007. —
Reprint.
(
doi:10.1007/s1020800401595)
Isolated multiple zeros or clusters of zeros of analytic
maps with several variables are known to be difficult to locate and
approximate. This article is in the vein of the αtheory, initiated by
M. Shub and S. Smale in the beginning of the eighties. This theory restricts
to simple zeros, i.e., where the map has corank zero. In this article we deal
with situations where the analytic map has corank one at the multiple
isolated zero, which has embedding dimension one in the frame of deformation
theory. These situations are the least degenerate ones and therefore most
likely to be of practical significance. More generally, we define clusters of
embedding dimension one. We provide a criterion for locating such clusters of
zeros and a fast algorithm for approximating them, with quadratic
convergence. In case of a cluster with positive diameter our algorithm stops
at a distance of the cluster which is about its diameter.

@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, JeanGuillaume},
publisher = {ACM Press},
pages = {3138},
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 speedups are obtained in indefinite and definite hypergeometric
summation. We describe the results of an implementation.},
}
Alin Bostan, Frédéric Chyzak, Thomas Cluzeau, and
Bruno Salvy
. —
Low complexity algorithms for linear recurrences. —
In JeanGuillaume Dumas, editor,
ISSAC'06, pages 31–38. ACM
Press, 2006. —
Reprint.
(
arXiv:abs/cs/0605068)
(
doi:10.1145/1145768.1145781)
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 2N) bit operations; a deterministic one that computes a
compact representation of the solution in O(N log 3N) bit operations.
Similar speedups are obtained in indefinite and definite hypergeometric
summation. We describe the results of an implementation.

@article{BoFlSaSc06,
author = {Bostan, Alin and Flajolet, Philippe and Salvy, Bruno and
Schost, {\'E}ric},
title = {Fast Computation of Special Resultants},
journal = {Journal of Symbolic Computation},
number = {1},
year = {2006},
month = {January},
volume = {41},
pages = {129},
doi = {10.1016/j.jsc.2005.07.001},
abstract = {We propose fast algorithms for computing composed products
and composed sums, as well as diamond products of univariate polynomials.
These operations correspond to special multivariate resultants, that we
compute using power sums of roots of polynomials, by means of their
generating series.},
}
Alin Bostan, Philippe Flajolet, Bruno Salvy, and Éric
Schost
. —
Fast computation of special resultants. —
Journal of Symbolic Computation, 41 n°1:1–29, January
2006. —
Reprint.
(
doi:10.1016/j.jsc.2005.07.001)
We propose fast algorithms for computing composed products
and composed sums, as well as diamond products of univariate polynomials.
These operations correspond to special multivariate resultants, that we
compute using power sums of roots of polynomials, by means of their
generating series.

@inproceedings{BaFaSaYa05,
author = {Bardet, M. and Faug{\`e}re, J.C. and Salvy, B. and Yang,
B.Y.},
title = {Asymptotic Behaviour of the Degree of Regularity of
SemiRegular Polynomial Systems},
booktitle = {MEGA'05},
year = {2005},
note = {Eighth International Symposium on Effective Methods in
Algebraic Geometry, Porto Conte, Alghero, Sardinia (Italy), May 27th  June
1st},
abstract = {We compute the asymptotic expansion of the degree of
regularity for overdetermined semiregular sequences of algebraic equations.
This degree implies bounds for the generic complexity of Gr{\"o}bner bases
algorithms, in particular Faug{\`e}re's $F_5$ algorithm. Bounds can also be
derived for the XL family of algorithms used by the cryptographic
community.},
}
M. Bardet, J.C. Faugère, B. Salvy, and B.Y.
Yang
. —
Asymptotic behaviour of the degree of regularity of semiregular polynomial
systems. —
In
MEGA'05, 2005. —
Eighth International Symposium on Effective Methods in Algebraic Geometry,
Porto Conte, Alghero, Sardinia (Italy), May 27th – June 1st.
We compute the asymptotic expansion of the degree of
regularity for overdetermined semiregular sequences of algebraic equations.
This degree implies bounds for the generic complexity of Gröbner bases
algorithms, in particular Faugère's F5 algorithm. Bounds can also be
derived for the XL family of algorithms used by the cryptographic
community.

@inproceedings{BoClSa05,
author = {Bostan, Alin and Cluzeau, Thomas and Salvy, Bruno},
title = {Fast Algorithms for Polynomial Solutions of Linear
Differential Equations},
booktitle = {ISSAC'05},
year = {2005},
editor = {Kauers, Manuel},
publisher = {ACM Press},
address = {New York},
pages = {4552},
note = {Proceedings of the 2005 International Symposium on Symbolic
and Algebraic Computation, July 2005, Beijing, China.},
doi = {10.1145/1073884.1073893},
abstract = {We investigate polynomial solutions of homogeneous linear
differential equations with coefficients that are polynomials with integer
coefficients. The problems we consider are the existence of nonzero
polynomial solutions, the determination of the dimension of the vector space
of polynomial solutions, the computation of a basis of this space. Previous
algorithms have a bit complexity that is at least quadratic in the largest
integer valuation $N$ of formal Laurent series solutions at infinity, even
for merely detecting the existence of nonzero polynomial solutions. We give a
deterministic algorithm that computes a compact representation of a basis of
polynomial solutions in $O(N\log^3N)$ bit operations. We also give a
probabilistic algorithm that computes the dimension of the space of
polynomial solutions in $O(N\log^2N)$ bit operations. In general, the integer
$N$ is not polynomially bounded in the bit size of the input differential
equation. We isolate a class of equations for which detecting nonzero
polynomial solutions can be performed in polynomial complexity. We discuss
implementation issues and possible extensions.},
}
Alin Bostan, Thomas Cluzeau, and Bruno Salvy
. —
Fast algorithms for polynomial solutions of linear differential equations. —
In Manuel Kauers, editor,
ISSAC'05, pages 45–52, New York, 2005.
ACM Press. —
Proceedings of the 2005 International Symposium on Symbolic and Algebraic
Computation, July 2005, Beijing, China.,
Reprint.
(
doi:10.1145/1073884.1073893)
We investigate polynomial solutions of homogeneous linear
differential equations with coefficients that are polynomials with integer
coefficients. The problems we consider are the existence of nonzero
polynomial solutions, the determination of the dimension of the vector space
of polynomial solutions, the computation of a basis of this space. Previous
algorithms have a bit complexity that is at least quadratic in the largest
integer valuation N of formal Laurent series solutions at infinity, even
for merely detecting the existence of nonzero polynomial solutions. We give a
deterministic algorithm that computes a compact representation of a basis of
polynomial solutions in O(N log 3N) bit operations. We also give a
probabilistic algorithm that computes the dimension of the space of
polynomial solutions in O(N log 2N) bit operations. In general, the integer
N is not polynomially bounded in the bit size of the input differential
equation. We isolate a class of equations for which detecting nonzero
polynomial solutions can be performed in polynomial complexity. We discuss
implementation issues and possible extensions.

@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 = {143},
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 subseries and
specializations from such combinations. Gessel has outlined a large class of
symmetric functions for which the resulting generating functions are
Dfinite. We extend Gessel's work by providing algorithms that compute
differential equations, these generating functions satisfy in the case they
are given as a scalar product of symmetric functions in Gessel's class.
Examples of applications to kregular graphs and Young tableaux with repeated
entries are given. Asymptotic estimates are a natural application of our
method, which we illustrate on the same model of Young tableaux. We also
derive a seemingly new formula for the Kronecker product of the sum of Schur
functions with itself.},
}
Frédéric Chyzak, Marni Mishna, and Bruno
Salvy
. —
Effective scalar products of Dfinite symmetric functions. —
Journal of Combinatorial Theory, Series A, 112 n°1:1–43,
October 2005. —
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,
Reprint.
(
arXiv:abs/math/0310132)
(
doi:10.1016/j.jcta.2005.01.001)
Many combinatorial generating functions can be expressed as
combinations of symmetric functions, or extracted as subseries and
specializations from such combinations. Gessel has outlined a large class of
symmetric functions for which the resulting generating functions are
Dfinite. We extend Gessel's work by providing algorithms that compute
differential equations, these generating functions satisfy in the case they
are given as a scalar product of symmetric functions in Gessel's class.
Examples of applications to kregular graphs and Young tableaux with repeated
entries are given. Asymptotic estimates are a natural application of our
method, which we illustrate on the same model of Young tableaux. We also
derive a seemingly new formula for the Kronecker product of the sum of Schur
functions with itself.

@article{FlGeSa05,
author = {Flajolet, Philippe and Gerhold, Stefan and Salvy, Bruno},
title = {On the nonholonomic character of logarithms, powers, and
the nth prime function},
journal = {The Electronic Journal of Combinatorics},
number = {2},
year = {2005},
month = {April},
volume = {11},
note = {A2, 16 pages},
arxiv = {abs/math/0501379},
url = {http://www.combinatorics.org/Volume_11/PDF/v11i2a2.pdf},
abstract = {We establish that the sequences formed by logarithms and by
``fractional'' powers of integers, as well as the sequence of prime numbers,
are nonholonomic, thereby answering three open problems of Gerhold
[El. J. Comb. 11 (2004), R87]. Our proofs depend on basic
complex analysis, namely a conjunction of the Structure Theorem for
singularities of solutions to linear differential equations and of an Abelian
theorem. A brief discussion is offered regarding the scope of
singularitybased methods and several naturally occurring sequences are
proved to be nonholonomic.},
}
Philippe Flajolet, Stefan Gerhold, and Bruno
Salvy
. —
On the
nonholonomic character of logarithms, powers, and the nth prime
function. —
The Electronic Journal of Combinatorics, 11 n°2, April
2005. —
A2, 16 pages.
(
arXiv:abs/math/0501379)
We establish that the sequences formed by logarithms and by
``fractional'' powers of integers, as well as the sequence of prime numbers,
are nonholonomic, thereby answering three open problems of Gerhold
[El. J. Comb. 11 (2004), R87]. Our proofs depend on basic
complex analysis, namely a conjunction of the Structure Theorem for
singularities of solutions to linear differential equations and of an Abelian
theorem. A brief discussion is offered regarding the scope of
singularitybased methods and several naturally occurring sequences are
proved to be nonholonomic.

@article{GiLeSaYa05,
author = {Giusti, Marc and Lecerf, Gr{\'e}goire and Salvy, Bruno and
Yakoubsohn, JeanClaude},
title = {On Location and Approximation of Clusters of Zeroes of
Analytic Functions},
journal = {Foundations of Computational Mathematics},
number = {3},
year = {2005},
month = {July},
volume = {5},
pages = {257311},
doi = {10.1007/s102080040144z},
abstract = {At the beginning of the 1980s, M. Shub and S. Smale
developed a quantitative analysis of Newton's method for multivariate
analytic maps. In particular, their $\alpha$theory gives an effective
criterion that ensures safe convergence to a simple isolated zero. This
criterion requires only information concerning the map at the initial point
of the iteration. Generalizing this theory to multiple zeros and clusters of
zeros is still a challenging problem. In this paper we focus on one complex
variable function. We study general criteria for detecting clusters and
analyze the convergence of Schr{\"o}der's iteration to a cluster. In the case
of a multiple root, it is well known that this convergence is quadratic. In
the case of a cluster with positive diameter, the convergence is still
quadratic provided the iteration is stopped sufficiently early. We propose a
criterion for stopping this iteration at a distance from the cluster which is
of the order of its diameter.},
}
Marc Giusti, Grégoire Lecerf, Bruno Salvy, and
JeanClaude Yakoubsohn
. —
On location and approximation of clusters of zeroes of analytic functions. —
Foundations of Computational Mathematics, 5 n°3:257–311,
July 2005. —
Reprint.
(
doi:10.1007/s102080040144z)
At the beginning of the 1980s, M. Shub and S. Smale
developed a quantitative analysis of Newton's method for multivariate
analytic maps. In particular, their αtheory gives an effective
criterion that ensures safe convergence to a simple isolated zero. This
criterion requires only information concerning the map at the initial point
of the iteration. Generalizing this theory to multiple zeros and clusters of
zeros is still a challenging problem. In this paper we focus on one complex
variable function. We study general criteria for detecting clusters and
analyze the convergence of Schröder's iteration to a cluster. In the case
of a multiple root, it is well known that this convergence is quadratic. In
the case of a cluster with positive diameter, the convergence is still
quadratic provided the iteration is stopped sufficiently early. We propose a
criterion for stopping this iteration at a distance from the cluster which is
of the order of its diameter.

@inproceedings{Salvy05,
author = {Salvy, Bruno},
title = {DFiniteness: Algorithms and Applications},
booktitle = {ISSAC'05},
year = {2005},
editor = {Kauers, Manuel},
publisher = {ACM Press},
pages = {23},
note = {Abstract for an invited talk. Proceedings of the 2005
International Symposium on Symbolic and Algebraic Computation, Beijing, July
2005.},
doi = {10.1145/1073884.1073886},
}
Bruno Salvy
. —
Dfiniteness: Algorithms and applications. —
In Manuel Kauers, editor,
ISSAC'05, pages 2–3. ACM Press,
2005. —
Abstract for an invited talk. Proceedings of the 2005 International Symposium
on Symbolic and Algebraic Computation, Beijing, July 2005.,
Reprint.
(
doi:10.1145/1073884.1073886)

@inproceedings{BaFaSa04,
author = {Bardet, Magali and Faugère, JeanCharles and Salvy,
Bruno},
title = {On the Complexity of Gröbner basis computation of
Semiregular Overdetermined algebraic equations},
booktitle = {International Conference on Polynomial System Solving},
year = {2004},
month = {November},
pages = {71–74},
note = {Proceedings of a conference held in Paris, France in honor
of Daniel Lazard},
url = {http://wwwcalfor.lip6.fr/ICPSS/papers/43BF/43bf.htm},
abstract = {We extend Macaulay's notion of regular sequence to
overdetermined system of algebraic equations. We study generic properties of
Gröbner bases and analyse precisely the behavior of Faugère's F5
algorithm. Sharp asymptotic estimates of the degree of regularity are
given.},
}
Magali Bardet, JeanCharles Faugère, and Bruno
Salvy
. —
On the
complexity of Gröbner basis computation of semiregular overdetermined
algebraic equations. —
In
International Conference on Polynomial System Solving, pages
71–74, November 2004. —
Proceedings of a conference held in Paris, France in honor of Daniel Lazard.
We extend Macaulay's notion of regular sequence to
overdetermined system of algebraic equations. We study generic properties of
Gröbner bases and analyse precisely the behavior of Faugère's F5
algorithm. Sharp asymptotic estimates of the degree of regularity are
given.

@inproceedings{BoLeSaScWi04,
author = {Bostan, Alin and Lecerf, Gr{\'e}goire and Salvy, Bruno and
Schost, {\'E}ric and Wiebelt, Bernd},
title = {Complexity Issues in Bivariate Polynomial Factorization},
booktitle = {Symbolic and Algebraic Computation},
year = {2004},
editor = {Gutierrez, J.},
publisher = {ACM Press},
pages = {4249},
note = {Proceedings of ISSAC'04, Santander, July 2004},
doi = {10.1145/1005285.1005294},
abstract = {Many polynomial factorization algorithms rely on Hensel
lifting and factor recombination. For bivariate polynomials we show that
lifting the factors up to a precision linear in the total degree of the
polynomial to be factored is sufficient to deduce the recombination by linear
algebra, using trace recombination. Then, the total cost of the lifting and
the recombination stage is subquadratic in the size of the dense
representation of the input polynomial. Lifting is often the practical
bottleneck of this method: we propose an algorithm based on a faster
multimoduli computation for univariate polynomials and show that it saves a
constant factor compared to the classical multifactor lifting algorithm.},
}
Alin Bostan, Grégoire Lecerf, Bruno Salvy, Éric
Schost, and Bernd Wiebelt
. —
Complexity issues in bivariate polynomial factorization. —
In J. Gutierrez, editor,
Symbolic and Algebraic Computation, pages
42–49. ACM Press, 2004. —
Proceedings of ISSAC'04, Santander, July 2004,
Reprint.
(
doi:10.1145/1005285.1005294)
Many polynomial factorization algorithms rely on Hensel
lifting and factor recombination. For bivariate polynomials we show that
lifting the factors up to a precision linear in the total degree of the
polynomial to be factored is sufficient to deduce the recombination by linear
algebra, using trace recombination. Then, the total cost of the lifting and
the recombination stage is subquadratic in the size of the dense
representation of the input polynomial. Lifting is often the practical
bottleneck of this method: we propose an algorithm based on a faster
multimoduli computation for univariate polynomials and show that it saves a
constant factor compared to the classical multifactor lifting
algorithm.

@article{FlSaSc04,
author = {Flajolet, Philippe and Salvy, Bruno and Schaeffer,
Gilles},
title = {Airy Phenomena and Analytic Combinatorics of Connected
Graphs},
journal = {The Electronic Journal of Combinatorics},
number = {1},
year = {2004},
month = {May},
volume = {11},
pages = {R34},
note = {30 pages},
url = {http://www.combinatorics.org/Volume_11/PDF/v11i1r34.pdf},
abstract = {Until now, the enumeration of connected graphs has been
dealt with by probabilistic methods, by special combinatorial decompositions
or by somewhat indirect formal series manipulations. We show here that it is
possible to make analytic sense of the divergent series that expresses the
generating function of connected graphs. As a consequence, it becomes
possible to derive analytically known enumeration results using only first
principles of combinatorial analysis and straight asymptotic
analysis—specifically, the saddlepoint method. In this perspective, the
enumeration of connected graphs by excess (of number of edges over number of
vertices) derives from a simple saddlepoint analysis. Furthermore, a refined
analysis based on coalescent saddle points yields complete asymptotic
expansions for the number of graphs of fixed excess, through an explicit
connection with Airy functions.},
}
Philippe Flajolet, Bruno Salvy, and Gilles
Schaeffer
. —
Airy
phenomena and analytic combinatorics of connected graphs. —
The Electronic Journal of Combinatorics, 11 n°1:R34, May
2004. —
30 pages.
Until now, the enumeration of connected graphs has been
dealt with by probabilistic methods, by special combinatorial decompositions
or by somewhat indirect formal series manipulations. We show here that it is
possible to make analytic sense of the divergent series that expresses the
generating function of connected graphs. As a consequence, it becomes
possible to derive analytically known enumeration results using only first
principles of combinatorial analysis and straight asymptotic
analysis—specifically, the saddlepoint method. In this perspective, the
enumeration of connected graphs by excess (of number of edges over number of
vertices) derives from a simple saddlepoint analysis. Furthermore, a refined
analysis based on coalescent saddle points yields complete asymptotic
expansions for the number of graphs of fixed excess, through an explicit
connection with Airy functions.

@article{BoSaSc03,
author = {Bostan, Alin and Salvy, Bruno and Schost, {\'E}ric},
title = {Fast Algorithms for ZeroDimensional Polynomial Systems
Using Duality},
journal = {Applicable Algebra in Engineering, Communication and
Computing},
number = {4},
year = {2003},
volume = {14},
pages = {239272},
doi = {10.1007/s0020000301335},
abstract = {Many questions concerning a zerodimensional polynomial
system can be reduced to linear algebra operations in the quotient
algebra~$A=k[X_1,\dots,X_n]/I$, where~$I$ is the ideal generated by the input
system. Assuming that the multiplicative structure of the algebra $A$ is
(partly) known, we address the question of speeding up the linear algebra
phase for the computation of minimal polynomials and rational
parametrizations in $A$. We present new formul{\ae}\ for the rational
parametrizations, extending those of Rouillier, and algorithms extending
ideas introduced by Shoup in the univariate case. Our approach is based on
the~$A$module structure of the dual space~$\widehat{A}$. An important
feature of our algorithms is that we do not require~$\widehat{A}$ to be free
and of rank~1. The complexity of our algorithms for computing the minimal
polynomial and the rational parametrizations are~$O(2^nD^{5/2})$
and~$O(n2^nD^{5/2})$ respectively, where~$D$ is the dimension of~$A$. For
fixed~$n$, this is better than algorithms based on linear algebra except when
the complexity of the available matrix product has exponent less than~5/2.},
}
Alin Bostan, Bruno Salvy, and Éric Schost
. —
Fast algorithms for zerodimensional polynomial systems using duality. —
Applicable Algebra in Engineering, Communication and Computing, 14
n°4:239–272, 2003. —
Reprint.
(
doi:10.1007/s0020000301335)
Many questions concerning a zerodimensional polynomial
system can be reduced to linear algebra operations in the quotient
algebra A=k[X1,…,Xn]/I, where I is the ideal generated by the input
system. Assuming that the multiplicative structure of the algebra A is
(partly) known, we address the question of speeding up the linear algebra
phase for the computation of minimal polynomials and rational
parametrizations in A. We present new formulæ for the rational
parametrizations, extending those of Rouillier, and algorithms extending
ideas introduced by Shoup in the univariate case. Our approach is based on
the Amodule structure of the dual space widehat A. An important
feature of our algorithms is that we do not require widehat A to be free
and of rank 1. The complexity of our algorithms for computing the minimal
polynomial and the rational parametrizations are O(2nD5/2)
and O(n2nD5/2) respectively, where D is the dimension of A. For
fixed n, this is better than algorithms based on linear algebra except when
the complexity of the available matrix product has exponent less
than 5/2.

@inproceedings{MeSa03,
author = {Meunier, Ludovic and Salvy, Bruno},
title = {{ESF}: An Automatically Generated Encyclopedia of Special
Functions},
booktitle = {Symbolic and Algebraic Computation},
year = {2003},
editor = {Sendra, J. R.},
publisher = {ACM Press},
pages = {199205},
note = {Proceedings of ISSAC'03, Philadelphia, August 2003.},
doi = {10.1145/860854.860898},
abstract = {We present our ongoing work on the automatic generation of
an encyclopedia of special functions on the web, called The Encyclopedia of
Special Functions (ESF) http://algo.inria.fr/esf. All mathematical
formul{\ae} in the ESF are computed, typeset and displayed without any human
intervention. This is achieved by exploiting a collection of computer algebra
algorithms in a systematic way, on top of a specially designed data structure
for a class of special functions.},
}
Ludovic Meunier and Bruno Salvy
. —
ESF: An automatically generated encyclopedia of special functions. —
In J. R. Sendra, editor,
Symbolic and Algebraic Computation, pages
199–205. ACM Press, 2003. —
Proceedings of ISSAC'03, Philadelphia, August 2003.,
Reprint.
(
doi:10.1145/860854.860898)
We present our ongoing work on the automatic generation of
an encyclopedia of special functions on the web, called The Encyclopedia of
Special Functions (ESF) http://algo.inria.fr/esf. All mathematical
formulæ in the ESF are computed, typeset and displayed without any human
intervention. This is achieved by exploiting a collection of computer algebra
algorithms in a systematic way, on top of a specially designed data structure
for a class of special functions.

@inproceedings{ChMiSa02,
author = {Chyzak, Frédéric and Mishna, Marni and Salvy, Bruno},
title = {Effective Dfinite 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]},
webcomment = {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 Dfinite. We
extend Gessel's work by providing algorithms that compute differential
equations these generating functions satisfy. Examples of applications to
kregular graphs and Young tableaux with repeated entries are given.},
}
Frédéric Chyzak, Marni Mishna, and Bruno
Salvy
. —
Effective Dfinite symmetric functions. —
In
14th Conference of Formal Power Series and Algebraic
Combinatorics, pages 19.1–19.12, Melbourne, Australia, July 2002.
University of Melbourne. —
Extended abstract. Proceedings FPSAC'02. An extended version has appeared
in
[Chyzak et al., 2005a],
Reprint.
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 Dfinite. We
extend Gessel's work by providing algorithms that compute differential
equations these generating functions satisfy. Examples of applications to
kregular graphs and Young tableaux with repeated entries are given.

@article{CoRoSa02,
author = {Cori, Robert and Rossin, Dominique and Salvy, Bruno},
title = {Polynomial Ideals for Sandpiles and their {G}r{\"o}bner
Bases},
journal = {Theoretical Computer Science},
number = {1},
year = {2002},
volume = {276},
pages = {115},
doi = {10.1016/S03043975(00)003972},
abstract = {A polynomial ideal encoding topplings in the abelian
sandpile model on a graph is introduced. A Gr{\"o}bner basis of this ideal is
interpreted combinatorially in terms of wellconnected subgraphs. This gives
rise to algorithms to determine the identity and the operation in the group
of recurrent configurations.},
}
Robert Cori, Dominique Rossin, and Bruno Salvy
. —
Polynomial ideals for sandpiles and their Gröbner bases. —
Theoretical Computer Science, 276 n°1:1–15, 2002. —
Reprint.
(
doi:10.1016/S03043975(00)003972)
A polynomial ideal encoding topplings in the abelian
sandpile model on a graph is introduced. A Gröbner basis of this ideal is
interpreted combinatorially in terms of wellconnected subgraphs. This gives
rise to algorithms to determine the identity and the operation in the group
of recurrent configurations.

@article{NiSaFl02,
author = {Nicod{\`e}me, Pierre and Salvy, Bruno and Flajolet,
Philippe},
title = {Motif Statistics},
journal = {Theoretical Computer Science},
number = {2},
year = {2002},
volume = {287},
pages = {593618},
note = {Extended version of an article published in the proceedings
of 7th Annual European Symposium on Algorithms ESA'99, Prague, July 1999},
doi = {10.1016/S03043975(01)00264X},
abstract = {We present a complete analysis of the statistics of number
of occurrences of a regular expression pattern in a random text. This covers
``motifs'' widely used in computational biology. Our approach is based on:
(i) classical constructive results in automata and formal language theory;
(ii) analytic combinatorics that is used for deriving asymptotic properties
from generating functions; (iii) computer algebra in order to determine
generating functions explicitly, analyse generating functions and extract
coefficients efficiently. We provide constructions for overlapping or
nonoverlapping matches of a regular expression. A companion implementation
produces: multivariate generating functions for the statistics under study; a
fast computation of their Taylor coefficients which yields exact values of
the moments with typical application to random texts of size 30,000; precise
asymptotic formul{\ae} that allow predictions in texts of arbitrarily large
sizes. Our implementation was tested by comparing predictions of the number
of occurrences of motifs against the 7 megabytes amino acid database Procite.
We handled more than 88% of the standard collection of Prodom motifs with our
programs. Such comparisons help detect which motifs are observed in real
biological data more or less frequently than theoretically predicted.},
}
Pierre Nicodème, Bruno Salvy, and Philippe
Flajolet
. —
Motif statistics. —
Theoretical Computer Science, 287 n°2:593–618, 2002. —
Extended version of an article published in the proceedings of 7th Annual
European Symposium on Algorithms ESA'99, Prague, July 1999,
Reprint.
(
doi:10.1016/S03043975(01)00264X)
We present a complete analysis of the statistics of number
of occurrences of a regular expression pattern in a random text. This covers
``motifs'' widely used in computational biology. Our approach is based on:
(i) classical constructive results in automata and formal language theory;
(ii) analytic combinatorics that is used for deriving asymptotic properties
from generating functions; (iii) computer algebra in order to determine
generating functions explicitly, analyse generating functions and extract
coefficients efficiently. We provide constructions for overlapping or
nonoverlapping matches of a regular expression. A companion implementation
produces: multivariate generating functions for the statistics under study; a
fast computation of their Taylor coefficients which yields exact values of
the moments with typical application to random texts of size 30,000; precise
asymptotic formulæ that allow predictions in texts of arbitrarily large
sizes. Our implementation was tested by comparing predictions of the number
of occurrences of motifs against the 7 megabytes amino acid database Procite.
We handled more than 88% of the standard collection of Prodom motifs with our
programs. Such comparisons help detect which motifs are observed in real
biological data more or less frequently than theoretically
predicted.

@techreport{SaSh02,
author = {Salvy, Bruno and Shackell, John},
title = {Asymptotic Expansions with Oscillating Coefficients},
number = {UKC/IMS/02/33},
year = {2002},
month = {October},
institution = {University of Kent, Canterbury},
}
Bruno Salvy and John Shackell
. —
Asymptotic expansions with oscillating coefficients. —
Research Report n°UKC/IMS/02/33, University of Kent, Canterbury, October
2002.

@article{GiLeSa01,
author = {Giusti, Marc and Lecerf, Gr{\'e}goire and Salvy, Bruno},
title = {A {G}r{\"o}bner Free Alternative for Polynomial System
Solving},
journal = {Journal of Complexity},
number = {1},
year = {2001},
month = {March},
volume = {17},
pages = {154211},
doi = {10.1006/jcom.2000.0571},
abstract = {Given a system of polynomial equations and inequations with
coefficients in the field of rational numbers, we show how to compute a
geometric resolution of the set of common roots of the system over the field
of complex numbers. A geometric resolution consists of a primitive element of
the algebraic extension defined by the set of roots, its minimal polynomial,
and the parametrizations of the coordinates. Such a representation of the
solutions has a long history which goes back to Leopold Kronecker and has
been revisited many times in computer algebra. We introduce a new generation
of probabilistic algorithms where all the computations use only univariate or
bivariate polynomials. We give a new codification of the set of solutions of
a positive dimensional algebraic variety relying on a new global version of
Newton's iterator. Roughly speaking the complexity of our algorithm is
polynomial in some kind of degree of the system, in its height, and linear in
the complexity of evaluation of the system. We present our implementation in
the Magma system which is called Kronecker in homage to his method for
solving systems of polynomial equations. We show that the theoretical
complexity of our algorithm is well reflected in practice and we exhibit some
cases for which our program is more efficient than the other available
software.},
}
Marc Giusti, Grégoire Lecerf, and Bruno Salvy
. —
A Gröbner free alternative for polynomial system solving. —
Journal of Complexity, 17 n°1:154–211, March 2001. —
Reprint.
(
doi:10.1006/jcom.2000.0571)
Given a system of polynomial equations and inequations with
coefficients in the field of rational numbers, we show how to compute a
geometric resolution of the set of common roots of the system over the field
of complex numbers. A geometric resolution consists of a primitive element of
the algebraic extension defined by the set of roots, its minimal polynomial,
and the parametrizations of the coordinates. Such a representation of the
solutions has a long history which goes back to Leopold Kronecker and has
been revisited many times in computer algebra. We introduce a new generation
of probabilistic algorithms where all the computations use only univariate or
bivariate polynomials. We give a new codification of the set of solutions of
a positive dimensional algebraic variety relying on a new global version of
Newton's iterator. Roughly speaking the complexity of our algorithm is
polynomial in some kind of degree of the system, in its height, and linear in
the complexity of evaluation of the system. We present our implementation in
the Magma system which is called Kronecker in homage to his method for
solving systems of polynomial equations. We show that the theoretical
complexity of our algorithm is well reflected in practice and we exhibit some
cases for which our program is more efficient than the other available
software.

@inproceedings{MeunierSalvy2001,
author = {Meunier, Ludovic and Salvy, Bruno},
title = {Automatically Generated Encyclopedia of Special
Functions},
booktitle = {Mathematical Knowledge Management},
year = {2001},
note = {Proceedings MKM'01, Linz, September 2001. A more advanced
version has appeared in [Meunier and Salvy, 2003]},
url = {http://www.risc.unilinz.ac.at/about/conferences/MKM2001/Proceedings/printed/meunier.ps},
abstract = {We present our ongoing work on creating an automatically
generated encyclopedia of special functions. The aim is to exploit recent
progress in computer algebra in order to synthesize web pages on special
functions and provide some level of interactivity.},
}
Ludovic Meunier and Bruno Salvy
. —
Automatically generated encyclopedia of special
functions. —
In
Mathematical Knowledge Management, 2001. —
Proceedings MKM'01, Linz, September 2001. A more advanced version has appeared
in
[Meunier and Salvy, 2003].
We present our ongoing work on creating an automatically
generated encyclopedia of special functions. The aim is to exploit recent
progress in computer algebra in order to synthesize web pages on special
functions and provide some level of interactivity.

@techreport{Salvy01,
author = {Salvy, Bruno},
title = {EvenOdd Set Partitions, SaddlePoint Method and Wyman
Admissibility},
number = {4201},
year = {2001},
institution = {Institut National de Recherche en Informatique et en
Automatique},
note = {14 pages},
url = {http://www.inria.fr/rrrt/rr4201.html},
abstract = {The reciprocal of the generating function of the Bell
numbers enumerates the difference between numbers of set partitions with even
and odd number of blocks. The asymptotic behaviour of this oscillatory
sequence is obtained by a saddlepoint analysis involving two conjugate
saddle points. Technical details of the analysis are dealt with by appealing
to Wyman's class of admissible functions.},
}
Bruno Salvy
. —
Evenodd set partitions,
saddlepoint method and Wyman admissibility. —
Research Report n°4201, Institut National de Recherche en Informatique
et en Automatique, 2001. —
14 pages.
The reciprocal of the generating function of the Bell
numbers enumerates the difference between numbers of set partitions with even
and odd number of blocks. The asymptotic behaviour of this oscillatory
sequence is obtained by a saddlepoint analysis involving two conjugate
saddle points. Technical details of the analysis are dealt with by appealing
to Wyman's class of admissible functions.

@inproceedings{NicodemeSalvyFlajolet1999,
author = {Nicodème, Pierre and Salvy, Bruno and Flajolet,
Philippe},
title = {Motif Statistics},
booktitle = {Algorithms – ESA'99},
number = {1643},
year = {1999},
editor = {Nesetril, Jaroslav},
series = {Lecture Notes in Computer Science},
pages = {194–211},
note = {Proceedings 7th Annual European Symposium on Algorithms,
Prague, July 99. An extended version appeared
in [NicodemeSalvyFlajolet02].},
doi = {10.1007/3540484817_18},
url = {http://www.springerlink.com/link.asp?id=kn33ur4g65qcgyhg},
abstract = {We present a complete analysis of the statistics of number
of occurrences of a regular expression pattern in a random text. This covers
``motifs'' widely used in computational biology. Our approach is based on:
(i) a constructive approach to classical results in theoretical
computer science (automata and formal language theory), in particular, the
rationality of generating functions of regular languages; (ii)
analytic combinatorics that is used for deriving asymptotic properties from
generating functions; (iii) computer algebra for determining
generating functions explicitly, analysing generating functions and
extracting coefficients efficiently. We provide constructions for overlapping
or nonoverlapping matches of a regular expression. A companion
implementation produces multivariate generating functions for the statistics
under study. A fast computation of Taylor coefficients of the generating
functions then yields exact values of the moments with typical application to
random texts of size 30,000 while precise symptotic formulæ allow
predictions in texts of arbitrarily large sizes. Our implementation was
tested by comparing predictions of the number of occurrences of motifs
against the 7 megabytes amino acid database sc Prodom. % consensus. We
handled more than 88% of the standard collection of sc Prosite motifs
with our programs. Such comparisons help detect which motifs are observed in
real biological data more or less frequently than theoretically predicted.},
}
Pierre Nicodème, Bruno Salvy, and Philippe
Flajolet
. —
Motif
statistics. —
In Jaroslav Nesetril, editor,
Algorithms – ESA'99,
Lecture
Notes in Computer Science, n°1643 in Lecture Notes in Computer
Science, pages 194–211, 1999. —
Proceedings 7th Annual European Symposium on Algorithms, Prague, July 99. An
extended version appeared in [NicodemeSalvyFlajolet02].,
Reprint.
(
doi:10.1007/3540484817_18)
We present a complete analysis of the statistics of number
of occurrences of a regular expression pattern in a random text. This covers
``motifs'' widely used in computational biology. Our approach is based on:
(i) a constructive approach to classical results in theoretical
computer science (automata and formal language theory), in particular, the
rationality of generating functions of regular languages; (ii)
analytic combinatorics that is used for deriving asymptotic properties from
generating functions; (iii) computer algebra for determining
generating functions explicitly, analysing generating functions and
extracting coefficients efficiently. We provide constructions for overlapping
or nonoverlapping matches of a regular expression. A companion
implementation produces multivariate generating functions for the statistics
under study. A fast computation of Taylor coefficients of the generating
functions then yields exact values of the moments with typical application to
random texts of size 30,000 while precise symptotic formulæ allow
predictions in texts of arbitrarily large sizes. Our implementation was
tested by comparing predictions of the number of occurrences of motifs
against the 7 megabytes amino acid database sc Prodom. % consensus. We
handled more than 88% of the standard collection of sc Prosite motifs
with our programs. Such comparisons help detect which motifs are observed in
real biological data more or less frequently than theoretically
predicted.

@proceedings{Salvy99,
title = {Algorithms Seminar, 1998–1999},
year = {1999},
month = {September},
editor = {Bruno Salvy},
volume = {3830},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr3830.html},
abstract = {These seminar notes represent the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorics, symbolic computation, asymptotic analysis and
averagecase analysis of algorithms and data structures.},
}
Bruno Salvy
, editor. —
Algorithms Seminar,
1998–1999,
Research Report, vol. 3830. Institut
National de Recherche en Informatique et en Automatique, September 1999.
These seminar notes represent the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorics, symbolic computation, asymptotic analysis and
averagecase analysis of algorithms and data structures.

@article{SaSh99,
author = {Salvy, Bruno and Shackell, John},
title = {Symbolic Asymptotics: Multiseries of Inverse Functions},
journal = {Journal of Symbolic Computation},
number = {6},
year = {1999},
month = {June},
volume = {27},
pages = {543563},
doi = {10.1006/jsco.1999.0281},
abstract = {We give an algorithm to compute an asymptotic expansion of
multiseries type for the inverse of any given explog function. An example of
the use of this algorithm to compute asymptotic expansions in combinatorics
via the saddlepoint method is then treated in detail.},
}
Bruno Salvy and John Shackell
. —
Symbolic asymptotics: Multiseries of inverse functions. —
Journal of Symbolic Computation, 27 n°6:543–563, June
1999. —
Reprint.
(
doi:10.1006/jsco.1999.0281)
We give an algorithm to compute an asymptotic expansion of
multiseries type for the inverse of any given explog function. An example of
the use of this algorithm to compute asymptotic expansions in combinatorics
via the saddlepoint method is then treated in detail.

@article{ChSa98,
author = {Chyzak, Frédéric and Salvy, Bruno},
title = {Noncommutative 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},
webcomment = {See the accompanying Maple session and the errata.},
abstract = {Many computations involving special functions,
combinatorial sequences or theirqanalogues 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.},
}
Frédéric Chyzak and Bruno Salvy
. —
Noncommutative elimination in Ore algebras proves multivariate holonomic
identities. —
Journal of Symbolic Computation, 26 n°2:187–227, August
1998. —
Reprint.
(
doi:10.1006/jsco.1998.0207)
Many computations involving special functions,
combinatorial sequences or theirqanalogues 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.

@article{FlSa98,
author = {Flajolet, Philippe and Salvy, Bruno},
title = {Euler Sums and Contour Integral Representations},
journal = {Experimental Mathematics},
number = {1},
year = {1998},
volume = {7},
pages = {15–35},
url = {http://www.math.ethz.ch/EMIS/journals/EM/restricted/7/7.1/flajolet.ps},
abstract = {This paper develops an approach to the evaluation of Euler
sums that involve harmonic numbers, either linearly or nonlinearly. We give
explicit formulæ for several classes of Euler sums in terms of Riemann
zeta values. The approach is based on simple contour integral representations
and residue computations.},
}
Philippe Flajolet and Bruno Salvy
. —
Euler sums and contour integral representations. —
Experimental Mathematics, 7 n°1:15–35, 1998.
This paper develops an approach to the evaluation of Euler
sums that involve harmonic numbers, either linearly or nonlinearly. We give
explicit formulæ for several classes of Euler sums in terms of Riemann
zeta values. The approach is based on simple contour integral representations
and residue computations.

@proceedings{Salvy98,
title = {Algorithms Seminar, 1997–1998},
year = {1998},
month = {September},
editor = {Bruno Salvy},
volume = {3504},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr3504.html},
abstract = {These seminar notes represent the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorics, symbolic computation, asymptotic analysis and
averagecase analysis of algorithms and data structures.},
}
Bruno Salvy
, editor. —
Algorithms Seminar,
1997–1998,
Research Report, vol. 3504. Institut
National de Recherche en Informatique et en Automatique, September 1998.
These seminar notes represent the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorics, symbolic computation, asymptotic analysis and
averagecase analysis of algorithms and data structures.

@article{SaSh98,
author = {Salvy, Bruno and Shackell, John},
title = {Symbolic Asymptotics: Functions of Two Variables, Implicit
Functions},
journal = {Journal of Symbolic Computation},
number = {3},
year = {1998},
month = {March},
volume = {25},
pages = {329349},
doi = {10.1006/jsco.1997.0179},
abstract = {A number of recent papers have been concerned with
algorithms to decide the limiting behaviour of functions of a single
variable. Here we make a corresponding study of a class of functions of two
variables, namely the explog functions. As in the onevariable case, we need
to make certain assumptions regarding the handling of constants. Two of the
main tools in the onevariable case are Hardy fields and nested forms. Here,
we show how to compute some asymptotic estimates for twovariable explog
functions. This method is then used to give an algorithm for computing the
nested forms of real implicit functions.},
}
Bruno Salvy and John Shackell
. —
Symbolic asymptotics: Functions of two variables, implicit functions. —
Journal of Symbolic Computation, 25 n°3:329–349, March
1998. —
Reprint.
(
doi:10.1006/jsco.1997.0179)
A number of recent papers have been concerned with
algorithms to decide the limiting behaviour of functions of a single
variable. Here we make a corresponding study of a class of functions of two
variables, namely the explog functions. As in the onevariable case, we need
to make certain assumptions regarding the handling of constants. Two of the
main tools in the onevariable case are Hardy fields and nested forms. Here,
we show how to compute some asymptotic estimates for twovariable explog
functions. This method is then used to give an algorithm for computing the
nested forms of real implicit functions.

@article{FlSa97,
author = {Flajolet, Philippe and Salvy, Bruno},
title = {The {S}IGSAM Challenges: Symbolic Asymptotics in
Practice},
journal = {SIGSAM Bulletin},
number = {4},
year = {1997},
month = {December},
volume = {31},
pages = {3647},
doi = {10.1145/274888.274890},
abstract = {We present answers to 5 out of 10 of the ``Problems,
Puzzles, Challenges'' proposed by G. J. Fee and M. B. Monagan in the March
1997 issue of the Sigsam Bulletin. In all cases, the answer to a seemingly
numerical problem is obtained via series expansions and asymptotic methods.
This illustrates more generally the crucial role played in the presence of
singular behaviours by symbolic asymptotics as a bridge between symbolic
computation and numerical computations. All our computations have been
performed using MapleV.4 on a Dec Alpha (255/233). The timings indicated
correspond to executions on this machine.},
}
Philippe Flajolet and Bruno Salvy
. —
The Sigsam challenges: Symbolic asymptotics in practice. —
SIGSAM Bulletin, 31 n°4:36–47, December 1997. —
Reprint.
(
doi:10.1145/274888.274890)
We present answers to 5 out of 10 of the ``Problems,
Puzzles, Challenges'' proposed by G. J. Fee and M. B. Monagan in the March
1997 issue of the Sigsam Bulletin. In all cases, the answer to a seemingly
numerical problem is obtained via series expansions and asymptotic methods.
This illustrates more generally the crucial role played in the presence of
singular behaviours by symbolic asymptotics as a bridge between symbolic
computation and numerical computations. All our computations have been
performed using MapleV.4 on a Dec Alpha (255/233). The timings indicated
correspond to executions on this machine.

@article{HaSa97,
author = {Habsieger, Laurent and Salvy, Bruno},
title = {On Integer Chebyshev Polynomials},
journal = {Mathematics of Computation},
number = {218},
year = {1997},
month = {April},
volume = {66},
pages = {763–770},
doi = {10.1090/S0025571897008296},
url = {http://www.ams.org/mcom/199766218/S0025571897008296/S0025571897008296.pdf},
abstract = {We are concerned with the problem of minimizing the
supremum norm on [0,1] of a nonzero polynomial of degree at most n with
integer coefficients. We use the structure of such polynomials to derive an
efficient algorithm for computing them. We give a table of these polynomials
for degree up to 75 and use a value from this table to answer an open
problem and improve a lower bound due to Borwein and Erdelyi (1995).},
}
Laurent Habsieger and Bruno Salvy
. —
On integer Chebyshev polynomials. —
Mathematics of Computation, 66 n°218:763–770, April
1997. —
Reprint.
(
doi:10.1090/S0025571897008296)
We are concerned with the problem of minimizing the
supremum norm on [0,1] of a nonzero polynomial of degree at most n with
integer coefficients. We use the structure of such polynomials to derive an
efficient algorithm for computing them. We give a table of these polynomials
for degree up to 75 and use a value from this table to answer an open
problem and improve a lower bound due to Borwein and Erdelyi
(1995).

@proceedings{Salvy97,
title = {Algorithms Seminar, 1996–1997},
year = {1997},
month = {September},
editor = {Bruno Salvy},
volume = {3267},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr3267.html},
abstract = {These seminar notes represent the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorics, symbolic computation, asymptotic analysis and
averagecase analysis of algorithms and data structures.},
}
Bruno Salvy
, editor. —
Algorithms Seminar,
1996–1997,
Research Report, vol. 3267. Institut
National de Recherche en Informatique et en Automatique, September 1997.
These seminar notes represent the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorics, symbolic computation, asymptotic analysis and
averagecase analysis of algorithms and data structures.

@article{GoSa96,
author = {Gourdon, Xavier and Salvy, Bruno},
title = {Effective asymptotics of linear recurrences with rational
coefficients},
journal = {Discrete Mathematics},
number = {13},
year = {1996},
volume = {153},
pages = {145163},
doi = {10.1016/0012365X(95)00133H},
abstract = {We give algorithms to compute the asymptotic expansion of
solutions of linear recurrences with rational coefficients and rational
initial conditions in polynomial time in the order of the recurrence.},
}
Xavier Gourdon and Bruno Salvy
. —
Effective asymptotics of linear recurrences with rational coefficients. —
Discrete Mathematics, 153 n°1–3:145–163, 1996. —
Reprint.
(
doi:10.1016/0012365X(95)00133H)
We give algorithms to compute the asymptotic expansion of
solutions of linear recurrences with rational coefficients and rational
initial conditions in polynomial time in the order of the
recurrence.

@inproceedings{RiSaShVH96,
author = {Richardson, Dan and Salvy, Bruno and Shackell, John and Van
der Hoeven, Joris},
title = {Asymptotic Expansions of explog Functions},
booktitle = {Symbolic and Algebraic Computation},
year = {1996},
editor = {Lakshman, Y. N.},
publisher = {ACM Press},
address = {New York},
pages = {309313},
note = {Proceedings ISSAC'96, Z{\"u}rich, July 1996},
doi = {10.1145/236869.237089},
abstract = {We give an algorithm to compute asymptotic expansions of
explog functions. This algorithm automatically computes the necessary
asymptotic scale and does not suffer from problems of indefinite
cancellation. In particular, an asymptotic equivalent can always be computed
for a given explog function.},
}
Dan Richardson, Bruno Salvy, John Shackell, and Joris
Van der Hoeven
. —
Asymptotic expansions of explog functions. —
In Y. N. Lakshman, editor,
Symbolic and Algebraic Computation,
pages 309–313, New York, 1996. ACM Press. —
Proceedings ISSAC'96, Zürich, July 1996,
Reprint.
(
doi:10.1145/236869.237089)
We give an algorithm to compute asymptotic expansions of
explog functions. This algorithm automatically computes the necessary
asymptotic scale and does not suffer from problems of indefinite
cancellation. In particular, an asymptotic equivalent can always be computed
for a given explog function.

@proceedings{Salvy96,
title = {Algorithms Seminar, 1995–1996},
year = {1996},
month = {September},
editor = {Bruno Salvy},
volume = {2992},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr2992.html},
}
Bruno Salvy
, editor. —
Algorithms Seminar,
1995–1996,
Research Report, vol. 2992. Institut
National de Recherche en Informatique et en Automatique, September
1996.

@article{DuSa95,
author = {Dumas, Philippe and Salvy, Bruno},
title = {Maple and the {P}utnam Competition},
journal = {Maple Technical Newsletter},
number = {2},
year = {1995},
volume = {2},
pages = {6368},
}
Philippe Dumas and Bruno Salvy
. —
Maple and the Putnam competition. —
Maple Technical Newsletter, 2 n°2:63–68, 1995.

@article{FlSa95,
author = {Flajolet, Philippe and Salvy, Bruno},
title = {Computer Algebra Libraries for Combinatorial Structures},
journal = {Journal of Symbolic Computation},
number = {56},
year = {1995},
volume = {20},
pages = {653671},
doi = {10.1006/jsco.1995.1070},
abstract = {This paper introduces the framework of decomposable
combinatorial structures and their traversal algorithms. A combinatorial type
is decomposable if it admits a specification in terms of unions, products,
sequences, sets, and cycles, either in the labelled or in the unlabelled
context. Many properties of decomposable structures are decidable. Generating
function equations, counting sequences, and random generation algorithms can
be compiled from specifications. Asymptotic properties can be determined
automatically for a reasonably large subclass. Maple libraries that implement
such decision procedures are briefly surveyed (LUO, combstruct, equivalent).
In addition, libraries for manipulating holonomic sequences and functions are
presented (gfun, Mgfun).},
}
Philippe Flajolet and Bruno Salvy
. —
Computer algebra libraries for combinatorial structures. —
Journal of Symbolic Computation, 20 n°56:653–671,
1995. —
Reprint.
(
doi:10.1006/jsco.1995.1070)
This paper introduces the framework of decomposable
combinatorial structures and their traversal algorithms. A combinatorial type
is decomposable if it admits a specification in terms of unions, products,
sequences, sets, and cycles, either in the labelled or in the unlabelled
context. Many properties of decomposable structures are decidable. Generating
function equations, counting sequences, and random generation algorithms can
be compiled from specifications. Asymptotic properties can be determined
automatically for a reasonably large subclass. Maple libraries that implement
such decision procedures are briefly surveyed (LUO, combstruct, equivalent).
In addition, libraries for manipulating holonomic sequences and functions are
presented (gfun, Mgfun).

@article{FlLaLaSa95,
author = {Flajolet, Philippe and Labelle, Gilbert and Laforest,
Louise and Salvy, Bruno},
title = {Hypergeometrics and the cost structure of quadtrees},
journal = {Random Structures \& Algorithms},
number = {2},
year = {1995},
volume = {7},
pages = {117144},
doi = {10.1002/rsa.3240070203},
abstract = {Several characteristic parameters of randomly grown
quadtrees of any dimension are analysed. Additive parameters have
expectations whose generating functions are expressible in terms of
generalized hypergeometric functions. A complex asymptotic process based on
singularity analysis and integral representations akin to Mellin transforms
leads to explicit values for various structure constants related to path
length, retrieval costs, and storage occupation.},
}
Philippe Flajolet, Gilbert Labelle, Louise Laforest, and
Bruno Salvy
. —
Hypergeometrics and the cost structure of quadtrees. —
Random Structures & Algorithms, 7 n°2:117–144, 1995. —
Reprint.
(
doi:10.1002/rsa.3240070203)
Several characteristic parameters of randomly grown
quadtrees of any dimension are analysed. Additive parameters have
expectations whose generating functions are expressible in terms of
generalized hypergeometric functions. A complex asymptotic process based on
singularity analysis and integral representations akin to Mellin transforms
leads to explicit values for various structure constants related to path
length, retrieval costs, and storage occupation.

@book{GoSaZi95,
author = {Gomez, Claude and Salvy, Bruno and Zimmermann, Paul},
title = {Calcul formel : mode d'emploi. {E}xemples en {M}aple},
year = {1995},
publisher = {Masson},
note = {ISBN 2225847800. 328 pages},
}
Claude Gomez, Bruno Salvy, and Paul Zimmermann
. —
Calcul formel : mode d'emploi. Exemples en Maple. —
Masson, 1995. —
ISBN 2225847800. 328 pages.

@article{LipshitzScottSalvy1995,
author = {Lipshitz, Stanley P. and Scott, Tony C. and Salvy, Bruno},
title = {On the Acoustic Impedance of Baffled Strip Radiators},
journal = {Journal of the Audio Engineering Society},
number = {7/8},
year = {1995},
month = {July/August},
volume = {43},
pages = {573580},
abstract = {There appears to be no available expression for the
reactive (mass) term in the acoustic impedance of long baffled strip
radiators, and the literature contains contradictory graphical data on both
the real and the imaginary parts. Reliable data are important for the proper
electroacoustic design of ribbon transducers, and also potentially for other
long, narrow, lowmass planar radiators, both electrostatic and
electrqmagnetic. Analytical expressions and graphical data are presented for
the resistive and reactive parts of the acoustic load on an infinite baffled
strip radiator.},
}
Stanley P. Lipshitz, Tony C. Scott, and Bruno
Salvy
. —
On the acoustic impedance of baffled strip radiators. —
Journal of the Audio Engineering Society, 43
n°7/8:573–580, July/August 1995. —
Reprint.
There appears to be no available expression for the
reactive (mass) term in the acoustic impedance of long baffled strip
radiators, and the literature contains contradictory graphical data on both
the real and the imaginary parts. Reliable data are important for the proper
electroacoustic design of ribbon transducers, and also potentially for other
long, narrow, lowmass planar radiators, both electrostatic and
electrqmagnetic. Analytical expressions and graphical data are presented for
the resistive and reactive parts of the acoustic load on an infinite baffled
strip radiator.

@proceedings{Salvy95,
title = {Algorithms Seminar, 1994–1995},
year = {1995},
month = {October},
editor = {Bruno Salvy},
volume = {2669},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr2669.html},
abstract = {These seminar notes represent the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorial models and random generation, symbolic
computation, asymptotic analysis, averagecase analysis of algorithms and
data structures, and computational number theory.},
}
Bruno Salvy
, editor. —
Algorithms Seminar,
1994–1995,
Research Report, vol. 2669. Institut
National de Recherche en Informatique et en Automatique, October 1995.
These seminar notes represent the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorial models and random generation, symbolic
computation, asymptotic analysis, averagecase analysis of algorithms and
data structures, and computational number theory.

@techreport{SaSl95,
author = {Salvy, Bruno and Slavyanov, Sergey Yu.},
title = {A Combinatorial Problem in the Classification of
SecondOrder Linear ODE's},
number = {2600},
year = {1995},
institution = {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr2600.html},
abstract = {We study a problem of classification of linear homogeneous
secondorder ODE's with polynomial coefficients based on qualitative
properties of singularities. The corresponding combinatorial problem of
counting the number of classes is then solved in terms of the initial number
of singularities.},
}
Bruno Salvy and Sergey Yu. Slavyanov
. —
A combinatorial problem in the
classification of secondorder linear ode's. —
Research Report n°2600, Institut National de Recherche en Informatique
et en Automatique, 1995.
We study a problem of classification of linear homogeneous
secondorder ODE's with polynomial coefficients based on qualitative
properties of singularities. The corresponding combinatorial problem of
counting the number of classes is then solved in terms of the initial number
of singularities.

@article{SaSh95,
author = {Shackell, John and Salvy, Bruno},
title = {Asymptotic Forms and Algebraic Differential Equations},
journal = {Journal of Symbolic Computation},
number = {2},
year = {1995},
volume = {20},
pages = {169177},
doi = {10.1006/jsco.1995.1044},
abstract = {We analyse the complexity of a simple algorithm for
computing asymptotic solutions of algebraic differential equations. This
analysis is based on a computation of the number of possible asymptotic
monomials of a certain order, and on the study of the growth of this number
as the order of the equation grows.},
}
John Shackell and Bruno Salvy
. —
Asymptotic forms and algebraic differential equations. —
Journal of Symbolic Computation, 20 n°2:169–177, 1995. —
Reprint.
(
doi:10.1006/jsco.1995.1044)
We analyse the complexity of a simple algorithm for
computing asymptotic solutions of algebraic differential equations. This
analysis is based on a computation of the number of possible asymptotic
monomials of a certain order, and on the study of the growth of this number
as the order of the equation grows.

@proceedings{Salvy94b,
title = {Algorithms Seminar, 1993–1994},
year = {1994},
month = {October},
editor = {Bruno Salvy},
volume = {2381},
series = {Research Report},
organization= {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr2381.html},
abstract = {These seminar notes represent the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorial models and random generation, symbolic
computation, asymptotic analysis, averagecase analysis of algorithms and
data structures, and computational number theory.},
}
Bruno Salvy
, editor. —
Algorithms Seminar,
1993–1994,
Research Report, vol. 2381. Institut
National de Recherche en Informatique et en Automatique, October 1994.
These seminar notes represent the proceedings of a seminar
devoted to the analysis of algorithms and related topics. The subjects
covered include combinatorial models and random generation, symbolic
computation, asymptotic analysis, averagecase analysis of algorithms and
data structures, and computational number theory.

@article{Salvy94,
author = {Salvy, Bruno},
title = {Fast Computation of Some Asymptotic Functional Inverses},
journal = {Journal of Symbolic Computation},
number = {3},
year = {1994},
volume = {17},
pages = {227236},
doi = {10.1006/jsco.1994.1014},
abstract = {G.~Robin showed that in several naturally occurring
asymptotic expansions of the form \[y(x)\approx\sum_{n\ge0}{P_n(\log\log
x)\over\log^n\!x},\] the polynomials~$P_n$ satisfy a simple relation
\[P'_{n+1}=aP'_n+(bn+c)P_n.\] These results do not give a way to compute
these polynomials, since the constant term remains undetermined by this
equation. In this note, we give a new derivation of some of Robin's results,
and show how the constant terms can be computed with only manipulations of
onevariable formal power series. From there, all the~$P_n$ can be computed
efficiently.},
}
Bruno Salvy
. —
Fast computation of some asymptotic functional inverses. —
Journal of Symbolic Computation, 17 n°3:227–236, 1994. —
Reprint.
(
doi:10.1006/jsco.1994.1014)
G. Robin showed that in several naturally occurring
asymptotic expansions of the form y(x) approx sum _n ge 0P_n( log log
x) over log ^nx, the polynomials Pn satisfy a simple relation
P'_n+1=aP'_n+(bn+c)P_n. These results do not give a way to compute
these polynomials, since the constant term remains undetermined by this
equation. In this note, we give a new derivation of some of Robin's results,
and show how the constant terms can be computed with only manipulations of
onevariable formal power series. From there, all the Pn can be computed
efficiently.

@article{SaZi94,
author = {Salvy, Bruno and Zimmermann, Paul},
title = {Gfun: a {M}aple package for the manipulation of generating
and holonomic functions in one variable},
journal = {ACM Transactions on Mathematical Software},
number = {2},
year = {1994},
volume = {20},
pages = {163177},
doi = {10.1145/178365.178368},
abstract = {We describe the GFUN package which contains functions for
manipulating sequences, linear recurrences, or differential equations and
generating functions of various types. This article is intended both as an
elementary introduction to the subject and as a reference manual for the
package.},
}
Bruno Salvy and Paul Zimmermann
. —
Gfun: a Maple package for the manipulation of generating and holonomic
functions in one variable. —
ACM Transactions on Mathematical Software, 20 n°2:163–177,
1994. —
Reprint.
(
doi:10.1145/178365.178368)
We describe the GFUN package which contains functions for
manipulating sequences, linear recurrences, or differential equations and
generating functions of various types. This article is intended both as an
elementary introduction to the subject and as a reference manual for the
package.

@inproceedings{BrSa93,
author = {Bronstein, Manuel and Salvy, Bruno},
title = {Full Partial Fraction Decomposition of Rational
Functions},
booktitle = {ISSAC'93},
year = {1993},
month = {July},
editor = {Bronstein, Manuel},
publisher = {ACM Press},
address = {New York},
pages = {157160},
doi = {10.1145/164081.164114},
abstract = {We describe a rational algorithm that computes the full
partial fraction expansion of a rational function over the algebraic closure
of its field of definition. The algorithm uses only gcd operations over the
initial field but the resulting decomposition is expressed with linear
denominators. We give examples from its Axiom and Maple implementations.},
}
Manuel Bronstein and Bruno Salvy
. —
Full partial fraction decomposition of rational functions. —
In Manuel Bronstein, editor,
ISSAC'93, pages 157–160, New York,
July 1993. ACM Press. —
Reprint.
(
doi:10.1145/164081.164114)
We describe a rational algorithm that computes the full
partial fraction expansion of a rational function over the algebraic closure
of its field of definition. The algorithm uses only gcd operations over the
initial field but the resulting decomposition is expressed with linear
denominators. We give examples from its Axiom and Maple
implementations.

@techreport{Salvy93b,
author = {(editor), Bruno Salvy},
title = {Algorithms Seminar, 1992–1993},
number = {2130},
year = {1993},
month = {December},
institution = {Institut National de Recherche en Informatique et en
Automatique},
url = {http://www.inria.fr/rrrt/rr2130.html},
abstract = {These seminar notes represent the proceedings (some in
French) of a seminar devoted to the analysis of algorithms and related
topics. The subjects covered include combinatorial models and random
generation, symbolic computati on, asymptotic analysis, averagecase
analysis of algorithms and data structures and some computational number
theory.},
}
Bruno Salvy (editor)
. —
Algorithms seminar,
1992–1993. —
Research Report n°2130, Institut National de Recherche en Informatique
et en Automatique, December 1993.
These seminar notes represent the proceedings (some in
French) of a seminar devoted to the analysis of algorithms and related
topics. The subjects covered include combinatorial models and random
generation, symbolic computati on, asymptotic analysis, averagecase
analysis of algorithms and data structures and some computational number
theory.

@article{FlSa93,
author = {Flajolet, Philippe and Salvy, Bruno},
title = {A Finite Sum of Products of Binomial Coefficients},
journal = {SIAM Review},
number = {4},
year = {1993},
volume = {35},
pages = {645–646},
keywords = {holonomic functions},
note = {Solution to Problem 92–18 by C. C. Grosjean},
doi = {10.1137/1035147},
url = {http://locus.siam.org/fulltext/SIREV/volume35/1035147.pdf},
}
Philippe Flajolet and Bruno Salvy
. —
A finite
sum of products of binomial coefficients. —
SIAM Review, 35 n°4:645–646, 1993. —
Solution to Problem 92–18 by C. C. Grosjean,
Reprint.
(
doi:10.1137/1035147)

@article{FlGoSa93,
author = {Flajolet, Philippe and Gourdon, Xavier and Salvy, Bruno},
title = {Sur une famille de polyn{\^o}mes issus de l'analyse
num{\'e}rique},
journal = {Gazette des Math{\'e}maticiens},
year = {1993},
month = {January},
volume = {55},
pages = {6778},
keywords = {polynomials, special functions, asymptotics, zeros},
}
Philippe Flajolet, Xavier Gourdon, and Bruno
Salvy
. —
Sur une famille de polynômes issus de l'analyse numérique. —
Gazette des Mathématiciens, 55:67–78, January 1993. —
Reprint.

@inproceedings{GourdonSalvy1993,
author = {Gourdon, Xavier and Salvy, Bruno},
title = {Asymptotics of linear recurrences with rational
coefficients},
booktitle = {Formal Power Series and Algebraic Combinatorics},
year = {1993},
editor = {Barlotti, A. and Delest, M. and Pinzani, R.},
pages = {253266},
note = {Proceedings of FPSAC'5, Florence (Italy). An extended
version appeared in Discrete Mathematics, 1996.},
abstract = {We give algorithms to compute the asymptotic expansion of
solutions of linear recurrences with rational coefficients and initial
conditions in polynomial time in the order of the recurrence.},
}
Xavier Gourdon and Bruno Salvy
. —
Asymptotics of linear recurrences with rational coefficients. —
In A. Barlotti, M. Delest, and R. Pinzani, editors,
Formal Power Series
and Algebraic Combinatorics, pages 253–266, 1993. —
Proceedings of FPSAC'5, Florence (Italy). An extended version appeared in
Discrete Mathematics, 1996.
We give algorithms to compute the asymptotic expansion of
solutions of linear recurrences with rational coefficients and initial
conditions in polynomial time in the order of the
recurrence.

@article{GourdonSalvy1993a,
author = {Gourdon, Xavier and Salvy, Bruno},
title = {Computing one million digits of $\sqrt{2}$},
journal = {The Maple Technical Newsletter},
year = {1993},
volume = {10},
pages = {6671},
abstract = {We describe how the knowledge of Maple's internal data
structure can be used to compute the first million digits of $\sqrt{2}$
efficiently.},
}
Xavier Gourdon and Bruno Salvy
. —
Computing one million digits of sqrt 2. —
The Maple Technical Newsletter, 10:66–71, 1993.
We describe how the knowledge of Maple's internal data
structure can be used to compute the first million digits of sqrt 2
efficiently.

@inproceedings{PeSa93,
author = {Petkov{\v s}ek, Marko and Salvy, Bruno},
title = {Finding all hypergeometric solutions of linear differential
equations},
booktitle = {ISSAC'93},
year = {1993},
month = {July},
editor = {Bronstein, Manuel},
publisher = {ACM Press},
address = {New York},
pages = {2733},
doi = {10.1145/164081.164087},
abstract = {Hypergeometric sequences are such that the quotient of two
successive terms is a fixed rational function of the index. We give a
generalization of M.~Petkov{\v s}ek's algorithm to find all hypergeometric
sequence solutions of linear recurrences, and we describe a program to find
all hypergeometric functions that solve a linear differential equation.},
}
Marko Petkov v sek and Bruno Salvy
. —
Finding all hypergeometric solutions of linear differential equations. —
In Manuel Bronstein, editor,
ISSAC'93, pages 27–33, New York,
July 1993. ACM Press. —
Reprint.
(
doi:10.1145/164081.164087)
Hypergeometric sequences are such that the quotient of two
successive terms is a fixed rational function of the index. We give a
generalization of M. Petkov v sek's algorithm to find all hypergeometric
sequence solutions of linear recurrences, and we describe a program to find
all hypergeometric functions that solve a linear differential
equation.

@article{Salvy93,
author = {Salvy, Bruno},
title = {Efficient programming in {M}aple: a case study},
journal = {SIGSAM Bulletin},
number = {2},
year = {1993},
month = {April},
volume = {27},
pages = {112},
doi = {10.1145/165474.165477},
abstract = {Studying the computation of orbits of some given group
acting on a set, we show how successive refinements of a simple program
provide a speedup factor of up to 200. The initial program cannot solve the
problem at all, it is first converted into a program which needs one c.p.u.
week and after all the optimizations have been performed, the computation
takes only four hours. Although the problem is specific, we shall show that
many of the optimizations we use are of interest for other problems as
well.},
}
Bruno Salvy
. —
Efficient programming in Maple: a case study. —
SIGSAM Bulletin, 27 n°2:1–12, April 1993. —
Reprint.
(
doi:10.1145/165474.165477)
Studying the computation of orbits of some given group
acting on a set, we show how successive refinements of a simple program
provide a speedup factor of up to 200. The initial program cannot solve the
problem at all, it is first converted into a program which needs one c.p.u.
week and after all the optimizations have been performed, the computation
takes only four hours. Although the problem is specific, we shall show that
many of the optimizations we use are of interest for other problems as
well.

@inproceedings{BergeronFlajoletSalvy1992,
author = {Bergeron, Fran{\c c}ois and Flajolet, Philippe and Salvy,
Bruno},
title = {Varieties of Increasing Trees},
booktitle = {CAAP'92},
year = {1992},
editor = {Raoult, J.C.},
volume = {581},
series = {Lecture Notes in Computer Science},
pages = {2448},
note = {Proceedings of the 17th Colloquium on Trees in Algebra and
Programming, Rennes, France, February 1992.},
doi = {10.1007/3540552510_2},
abstract = {An increasing tree is a labelled rooted tree in which
labels along any branch from the root go in increasing order. Under various
guises, such trees have surfaced as tree representations of permutations, as
data structures in computer science, and as probabilistic models in diverse
applications. We present a unified generating function approach to the
enumeration of parameters on such trees. The counting generating functions
for several basic parameters are shown to be related to a simple ordinary
differential equation $$ {d\over dz}Y(z)=\phi(Y(z)),$$ which is non linear
and autonomous. Singularity analysis applied to the intervening generating
functions then permits to analyze asymptotically a number of parameters of
the trees, like: root degree, number of leaves, path length, and level of
nodes. In this way it is found that various models share common features:
path length is $O(n\log n)$, the distributions of node levels and number of
leaves are asymptotically normal, etc.},
}
François Bergeron, Philippe Flajolet, and Bruno
Salvy
. —
Varieties of increasing trees. —
In J.C. Raoult, editor,
CAAP'92,
Lecture Notes in Computer
Science, vol. 581, pages 24–48, 1992. —
Proceedings of the 17th Colloquium on Trees in Algebra and Programming, Rennes,
France, February 1992.,
Reprint.
(
doi:10.1007/3540552510_2)
An increasing tree is a labelled rooted tree in which
labels along any branch from the root go in increasing order. Under various
guises, such trees have surfaced as tree representations of permutations, as
data structures in computer science, and as probabilistic models in diverse
applications. We present a unified generating function approach to the
enumeration of parameters on such trees. The counting generating functions
for several basic parameters are shown to be related to a simple ordinary
differential equation $ d over dzY(z)=φ(Y(z)), which is non linear
and autonomous. Singularity analysis applied to the intervening generating
functions then permits to analyze asymptotically a number of parameters of
the trees, like: root degree, number of leaves, path length, and level of
nodes. In this way it is found that various models share common features:
path length is O(n log n)$, the distributions of node levels and number of
leaves are asymptotically normal, etc.

@inproceedings{Salvy1992,
author = {Salvy, Bruno},
title = {General Asymptotic Scales and Computer Algebra},
booktitle = {Asymptotic and Numerical Methods for Partial Differential
Equations, Critical Parameters and Domain Decomposition},
year = {1992},
editor = {Kaper, H. and Garbey, M.},
publisher = {Kluwer Academic Publishers},
note = {Proceedings of a NATO Advanced Research Workshop, Beaune,
France, May 1992.},
abstract = {In many natural applications, one encounters asymptotic
expansions of a form more complicated than mere Puiseux series. Existing
computer algebra systems lack good algorithms for handling such asymptotic
expansions. We present tools that permit the representation and automatic
handling of general explog asymptotic expansions.},
}
Bruno Salvy
. —
General asymptotic scales and computer algebra. —
In H. Kaper and M. Garbey, editors,
Asymptotic and Numerical Methods for
Partial Differential Equations, Critical Parameters and Domain
Decomposition. Kluwer Academic Publishers, 1992. —
Proceedings of a NATO Advanced Research Workshop, Beaune, France, May 1992.
In many natural applications, one encounters asymptotic
expansions of a form more complicated than mere Puiseux series. Existing
computer algebra systems lack good algorithms for handling such asymptotic
expansions. We present tools that permit the representation and automatic
handling of general explog asymptotic expansions.

@inproceedings{SaSh92,
author = {Salvy, Bruno and Shackell, John},
title = {Asymptotic expansions of functional inverses},
booktitle = {Symbolic and Algebraic Computation},
year = {1992},
editor = {Wang, Paul S.},
publisher = {ACM Press},
address = {New York},
pages = {130137},
note = {Proceedings of ISSAC'92, Berkeley, July 1992.},
doi = {10.1145/143242.143292},
abstract = {We study the automatic computation of asymptotic expansions
of functional inverses. Based on previous work on asymptotic expansions, we
give an algorithm which computes Hardyfield solutions of equations~$f(y)=x$,
with~$f$ belonging to a large class of functions.},
}
Bruno Salvy and John Shackell
. —
Asymptotic expansions of functional inverses. —
In Paul S. Wang, editor,
Symbolic and Algebraic Computation, pages
130–137, New York, 1992. ACM Press. —
Proceedings of ISSAC'92, Berkeley, July 1992.,
Reprint.
(
doi:10.1145/143242.143292)
We study the automatic computation of asymptotic expansions
of functional inverses. Based on previous work on asymptotic expansions, we
give an algorithm which computes Hardyfield solutions of equations f(y)=x,
with f belonging to a large class of functions.

@article{FlajoletSalvyZimmermann1991,
author = {Flajolet, Philippe and Salvy, Bruno and Zimmermann, Paul},
title = {Automatic Averagecase Analysis of Algorithms},
journal = {Theoretical Computer Science, Series A},
number = {1},
year = {1991},
month = {February},
volume = {79},
pages = {37109},
doi = {10.1016/03043975(91)90145R},
abstract = {Many probabilistic properties of elementary discrete
combinatorial structures of interest for the averagecase analysis of
algorithms prove to be decidable. This paper presents a general framework in
which such decision procedures can be developed. It is based on a combination
of generating function techniques for counting, and complex analysis
techniques for asymptotic estimations. We expose here the theory of exact
analysis in terms of generating functions for four different domains: the
iterative/recursive and unlabelled/labelled data type domains. We then
present some major components of the associated asymptotic theory and exhibit
a class of naturally arising functions that can be automatically analyzed. A
fair fragment of this theory is also incorporated into a system called
LambdaUpsilonOmega. In this way, using computer algebra, one can produce
automatically nontrivial averagecase analyses of algorithms operating over
a variety of ``decomposable'' combinatorial structures. At a fundamental
level, this paper is part of a global attempt at understanding why so many
elementary combinatorial problems tend to have elementary asymptotic
solutions. In several cases, it proves possible to relate entire classes of
elementary combinatorial problems whose structure is well defined with
classes of elementary ``special'' functions and classes of asymptotic forms
relative to counting, probabilities, or averagecase complexity.},
}
Philippe Flajolet, Bruno Salvy, and Paul
Zimmermann
. —
Automatic averagecase analysis of algorithms. —
Theoretical Computer Science, Series A, 79 n°1:37–109,
February 1991. —
Reprint.
(
doi:10.1016/03043975(91)90145R)
Many probabilistic properties of elementary discrete
combinatorial structures of interest for the averagecase analysis of
algorithms prove to be decidable. This paper presents a general framework in
which such decision procedures can be developed. It is based on a combination
of generating function techniques for counting, and complex analysis
techniques for asymptotic estimations. We expose here the theory of exact
analysis in terms of generating functions for four different domains: the
iterative/recursive and unlabelled/labelled data type domains. We then
present some major components of the associated asymptotic theory and exhibit
a class of naturally arising functions that can be automatically analyzed. A
fair fragment of this theory is also incorporated into a system called
LambdaUpsilonOmega. In this way, using computer algebra, one can produce
automatically nontrivial averagecase analyses of algorithms operating over
a variety of ``decomposable'' combinatorial structures. At a fundamental
level, this paper is part of a global attempt at understanding why so many
elementary combinatorial problems tend to have elementary asymptotic
solutions. In several cases, it proves possible to relate entire classes of
elementary combinatorial problems whose structure is well defined with
classes of elementary ``special'' functions and classes of asymptotic forms
relative to counting, probabilities, or averagecase
complexity.

@article{Salvy91b,
author = {Salvy, B.},
title = {Examples of automatic asymptotic expansions},
journal = {SIGSAM Bulletin},
number = {2},
year = {1991},
month = {April},
volume = {25},
pages = {417},
doi = {10.1145/122520.122521},
abstract = {We describe the current state of a Maple library, gdev,
designed to perform asymptotic expansions for a large class of expressions.
Many examples are provided, along with a short sketch of the underlying
principles. At the time when this report is written, a striking feature of
these examples is that none of them can be computed directly with any of
today's most widespread symbolic computation systems (Macsyma (Sun Release
309.6), Mathematica (Version 1.2, beta test), Maple (Version 4.3) or
Scratchpad~II (Version 4J)).},
}
B. Salvy
. —
Examples of automatic asymptotic expansions. —
SIGSAM Bulletin, 25 n°2:4–17, April 1991. —
Reprint.
(
doi:10.1145/122520.122521)
We describe the current state of a Maple library, gdev,
designed to perform asymptotic expansions for a large class of expressions.
Many examples are provided, along with a short sketch of the underlying
principles. At the time when this report is written, a striking feature of
these examples is that none of them can be computed directly with any of
today's most widespread symbolic computation systems (Macsyma (Sun Release
309.6), Mathematica (Version 1.2, beta test), Maple (Version 4.3) or
Scratchpad II (Version 4J)).

@phdthesis{Salvy1991b,
author = {Salvy, Bruno},
title = {Asymptotique automatique et fonctions
g{\'e}n{\'e}ratrices},
year = {1991},
school = {{\'E}cole polytechnique},
keywords = {asymptotic analysis, automatic asymptotics, computer
algebra},
abstract = {The purpose of this thesis is to partially automate
asymptotic analysis. We first describe the mathematical objects that underlie
asymptotic expansions, and then introduce the data structures and algorithms
that correspond to them. With these tools, the second chapter shows the
automation of the asymptotic expansion of integrals, for a wide class of
integrands. The second part of this thesis is devoted to the analysis of
integral variables. We recall the main properties of generating functions,
and present in detail the automatic extraction of asymptotic information
about their coefficients by purely syntactical operations. This constitutes
the analytical part of the~LUO system. This system, developed with
P.~Zimmermann, is capable of producing nontrivial averagecase analyses of
algorithms and parameters of combinatorial structures. In our last chapter,
we describe its principles and scrutinize a variety of examples to explain
its use and working.},
}
Bruno Salvy
. —
Asymptotique automatique et fonctions génératrices. —
Thèse de doctorat, École polytechnique, 1991.
The purpose of this thesis is to partially automate
asymptotic analysis. We first describe the mathematical objects that underlie
asymptotic expansions, and then introduce the data structures and algorithms
that correspond to them. With these tools, the second chapter shows the
automation of the asymptotic expansion of integrals, for a wide class of
integrands. The second part of this thesis is devoted to the analysis of
integral variables. We recall the main properties of generating functions,
and present in detail the automatic extraction of asymptotic information
about their coefficients by purely syntactical operations. This constitutes
the analytical part of the LUO system. This system, developed with
P. Zimmermann, is capable of producing nontrivial averagecase analyses of
algorithms and parameters of combinatorial structures. In our last chapter,
we describe its principles and scrutinize a variety of examples to explain
its use and working.

@article{Salvy91c,
author = {Salvy, Bruno},
title = {Three ways to get {S}tirling's formula in {M}aple},
journal = {The Maple Technical Newsletter},
year = {1991},
volume = {5},
pages = {3242},
}
Bruno Salvy
. —
Three ways to get Stirling's formula in Maple. —
The Maple Technical Newsletter, 5:32–42, 1991.

@inproceedings{FlajoletSalvyZimmermann1989,
author = {Flajolet, P. and Salvy, B. and Zimmermann, P.},
title = {{L}ambda{U}psilon{O}mega: An Assistant Algorithms
Analyzer},
booktitle = {Applied Algebra, Algebraic Algorithms and ErrorCorrecting
Codes},
year = {1989},
editor = {Mora, T.},
volume = {357},
series = {Lecture Notes in Computer Science},
pages = {201212},
note = {Proceedings AAECC'6, Rome, July 1988},
doi = {10.1007/3540510834_60},
abstract = {LambdaUpsilonOmega, LUO, is a system designed to perform
automatic analysis of welldefined classes of algorithms operating over
decomposable data structures. It consists of an Algebraic Analyzer System
that compiles algorithms specifications into generating functions of average
costs, and an Analytic Analyzer System that extracts asymptotic informations
on coefficients of generating functions. The algebraic part relies on recent
methodologies in combinatorial analysis based on systematic correspondences
between structural type definitions and counting generating functions. The
analytic part makes use of partly classical and partly new correspondences
between singularities of analytic functions and the growth of their Taylor
coefficients. The current version LUO0 of LUO implements as basic data types,
term trees as encountered in symbolic algebra systems. The analytic analyzer
can treat large classes of functions with explicit expressions. In this way,
LUO0 can generate in the current stage about a dozen nontrivial average case
analyses of algorithms like: formal differentiation, some algebraic
simplification and matching algorithms. Its analytic analyzer can determine
asymptotic expansions for large classes of generating functions arising in
the analysis of algorithms. The outline of a design for a full system is also
discussed here. The long term goal is to include a fairly rich set of data
structuring mechanisms including some general recursive type definitions, and
have the analytic analyzer treat wide classes of functional equations as may
be encountered in combinatorial analysis and the analysis of algorithms.},
}
P. Flajolet, B. Salvy, and P. Zimmermann
. —
LambdaUpsilonOmega: An assistant algorithms analyzer. —
In T. Mora, editor,
Applied Algebra, Algebraic Algorithms and
ErrorCorrecting Codes,
Lecture Notes in Computer
Science, vol. 357, pages 201–212, 1989. —
Proceedings AAECC'6, Rome, July 1988.
(
doi:10.1007/3540510834_60)
LambdaUpsilonOmega, LUO, is a system designed to perform
automatic analysis of welldefined classes of algorithms operating over
decomposable data structures. It consists of an Algebraic Analyzer System
that compiles algorithms specifications into generating functions of average
costs, and an Analytic Analyzer System that extracts asymptotic informations
on coefficients of generating functions. The algebraic part relies on recent
methodologies in combinatorial analysis based on systematic correspondences
between structural type definitions and counting generating functions. The
analytic part makes use of partly classical and partly new correspondences
between singularities of analytic functions and the growth of their Taylor
coefficients. The current version LUO0 of LUO implements as basic data types,
term trees as encountered in symbolic algebra systems. The analytic analyzer
can treat large classes of functions with explicit expressions. In this way,
LUO0 can generate in the current stage about a dozen nontrivial average case
analyses of algorithms like: formal differentiation, some algebraic
simplification and matching algorithms. Its analytic analyzer can determine
asymptotic expansions for large classes of generating functions arising in
the analysis of algorithms. The outline of a design for a full system is also
discussed here. The long term goal is to include a fairly rich set of data
structuring mechanisms including some general recursive type definitions, and
have the analytic analyzer treat wide classes of functional equations as may
be encountered in combinatorial analysis and the analysis of
algorithms.

@techreport{FlajoletSalvyZimmermann1989a,
author = {Flajolet, P. and Salvy, B. and Zimmermann, P.},
title = {LambdaUpsilonOmega: The 1989 CookBook},
number = {1073},
year = {1989},
month = {August},
institution = {Institut National de Recherche en Informatique et en
Automatique},
note = {116 pages},
url = {http://www.inria.fr/rrrt/rr1073.html},
abstract = {LambdaUpsilonOmega (LUO) is a research tool designed to
assist the average case analysis of some well defined classes of algorithms
and data structures. This cookbook consists of an informal introduction to
the system together with eighteen examples of programmes that are
automatically analyzed. Amongst the applications treated here, we find:
addition chains, quantitative concurrency analysis of simple systems,
symbolic manipulation algorithms such as formal differentiation,
simplification and rewriting systems, as well as combinatorial models
including various tree and permutation statistics and functional graphs with
applications to integer factorisation.},
}
P. Flajolet, B. Salvy, and P. Zimmermann
. —
LambdaUpsilonOmega:
The 1989 Cookbook. —
Research Report n°1073, Institut National de Recherche en Informatique
et en Automatique, August 1989. —
116 pages.
LambdaUpsilonOmega (LUO) is a research tool designed to
assist the average case analysis of some well defined classes of algorithms
and data structures. This cookbook consists of an informal introduction to
the system together with eighteen examples of programmes that are
automatically analyzed. Amongst the applications treated here, we find:
addition chains, quantitative concurrency analysis of simple systems,
symbolic manipulation algorithms such as formal differentiation,
simplification and rewriting systems, as well as combinatorial models
including various tree and permutation statistics and functional graphs with
applications to integer factorisation.