Brigitte Vallée: The Concept of "Dynamical Analysis"

This is a joint work with Jerémie Bourdon and Benoît Daireaux.

It is a quite natural idea to consider an algorithm together with its possible inputs as a dynamical system. The (discrete) time is related to the number of iterations. The main tools of dynamical system theory (for instance the transfer operator) encapsulate all the important informations relative to the "dynamics" of the algorithm, and they are quite useful to describe the evolution of the system. Most of the algorithms have a quite correlated history, in the sense that the future evolution of the algorithm depends on the whole previous history. In this case, the "generating function methodology" is no longer useful, and we propose to replace it by a "generating operator methodology". In fact, the transfer operators can be diverted from their classical use and viewed as "generating" operators, in the sense that they can easily generate the main parameters of interest, and generating functions themselves. Whereas classical singularity analysis relates (complex) singularities of generating functions to asymptotics of their coefficients, we here relate asymptotics of main parameters to dominant spectral properties of the transfer operators. More precisely, their main analytical property (in a convenient functional space) that is useful in dynamical analysis is the existence of a "spectral gap" that separates the unique dominant eigenvalue from the remainder of the spectrum.

Brigitte Vallée: Instances of Dynamical Analyses Using More Complex Dynamical Systems

This is a joint work with Jerémie Bourdon and Benoît Daireaux.

All the previous instances of dynamical systems deal with "complete" dynamical systems, i.e., dynamical systems whose branches are surjective. More recently, we are led to study dynamical systems that are no longer complete. First, some natural algorithms (of the Euclidean type) lead to this kind of dynamical systems. Second, this kind of dynamical systems is quite useful when studying very correlated dynamical sources. In this case, we have to work in more complex functional spaces, where we cannot expect the transfer operator to be compact. The convenient space is the space of functions with bounded variation.

As an instance of the method, we study a generic Euclidean algorithm, called the $\alpha$-Euclidean algorithm, where the remainder has to belong to some interval $[\alpha-1, \alpha]$ with $\alpha \in [0, 1]$. When the parameter varies in $[0, 1]$, this gives rise to a whole class of algorithms. We can answer some natural questions, for instance: How does the number of iterations and the bit complexity evolve with respect to $\alpha$? What is the best algorithm of the whole class?

Back to the Index