## Research Topics of the Algorithms Project |

Welcome! | Research Topics | People | Publications | Seminars | Software | On-Line Applications | Jobs & Internships |

Analysis of Algorithms | Computer Algebra |

Computer algebra at large aims at making effective large portions of mathematics, paying due attention to complexity issues. For reasons mentioned above, our project specifically investigates the way mathematical objects originating in complex analysis can be dealt with in an algorithmic way by computer algebra systems. Our main contributions in this area concern the automation of asymptotic analysis and the handling of special functions. The mathematical foundations of our algorithms are deeply rooted in differential algebra (Hardy fields for asymptotic expansions and Ore algebras for special functions).

Over the years, in order to automate the average-case analysis of
larger and ever larger classes of algorithms, we have developed
algorithms and implementations for the following problems: the
specification of formally specified combinatorial structures; the
corresponding problems of enumeration and random generation; the
automatic construction of asymptotic scales which is necessary for
extracting the singular behaviour of generating functions; the
automatic computation of asymptotic expansions in such scales; the
automatic computation of asymptotic expansions satisfied by
coefficients of generating series. An *Encyclopedia of
Combinatorial Structures*, available on the web, gathers roughly
one thousand structures for which generating series, recurrences, and
asymptotic behaviour have been determined automatically using our
libraries.

An important principle of computer algebra is that it is often easier
to operate with equations defining a mathematical object implicitly
rather than trying to obtain a ``closed-form'' expression of it. The
class of linear differential and difference equations is particularly
important in view of the large variety of functions and sequences they
capture. In this area, we have developed the highly successful GFUN package (jointly with
P. Zimmermann, from the Spaces project) dealing with the univariate
case. In the multivariate case, we have developed the underlying
theory based on Gröbner bases in Ore algebra, and an implementation in
the MGFUN package. The
algorithmic advances of the past few years have made it possible to
start the implementation of a *Dynamic Dictionary of Mathematical Functions*, providing various information
concerning classical functions (of wide use throughout sciences),
including Bessel functions, Airy functions, ... The corresponding
information is all automatically generated.