Institut de Mathématiques de Marseille, UMR 7373

Aller au menu
Aller à la recherche
Aller au contenu
Aller à la navigation

Le CNRS
Autres sites CNRS

L’Institut
Annuaire
Équipes de recherche
Séminaires
Colloques
Publications
Contrats de recherche / Projets
Relations internationales
Enseignement-Formation
Bibliothèques
Ressources / Procédures
Offres d’emploi
Appels à projets
- AAP 2017
- AAP 2018
Liens
Trombinoscope
Intranet (AIGLe)
--Revue de Presse CNRS
---Nouveaux Personnels

Rechercher

Accueil >

MERLET Glenn

Organisme : Aix Marseille Université
Maître de Conférences

Equipe: Groupes, Dynamique, Arithmétique, Combinatoire (GDAC)

glenn.merlet _AT_

univ-amu.fr

04 91 26 96 69

Bureau: 213, Etg: 2, Bât: TPR2 - Site : Luminy

Page Web perso

Domaines de Recherche:

Productions scientifiques :

The ultimate rank of tropical matrices

Auteur(s): Guillon P., Izhakian Zur, Mairesse Jean, Merlet G.

(Article) Publié: Journal Of Algebra, vol. 437 p.222-248 (2015)

Ref HAL: hal-01194760_v1
DOI: 10.1016/j.jalgebra.2015.02.026
Exporter : BibTex | endNote
Résumé:

A tropical matrix is a matrix defined over the max-plus semiring. For such matrices, there exist several non-coinciding notions of rank: the row rank, the column rank, the Schein/Barvinok rank, the Kapranov rank, or the tropical rank, among others. In the present paper, we show that there exists a natural notion of ultimate rank for the powers of a tropical matrix, which does not depend on the underlying notion of rank. Furthermore, we provide a simple formula for the ultimate rank of a matrix, which can therefore be computed in polynomial time. Then we turn our attention to finitely generated semigroups of matrices, for which our notion of ultimate rank is generalized naturally. We provide both combinatorial and geometric characterizations of semigroups having maximal ultimate rank. As a consequence, we obtain a polynomial algorithm to decide if the ultimate rank of a finitely generated semigroup is maximal.

Weak CSR expansions and transience bounds in max-plus algebra

Auteur(s): Merlet G., Nowak Thomas, Sergeev Sergei

(Article) Publié: Linear Algebra And Its Applications, vol. 461 p.163-199 (2014)

Ref HAL: hal-01058031_v2
DOI: 10.1016/j.laa.2014.07.027
Exporter : BibTex | endNote
Résumé:

This paper aims to unify and extend existing techniques for deriving upper bounds on the transient of max-plus matrix powers. To this aim, we introduce the concept of weak CSR expansions: At=CStR⊕Bt. We observe that most of the known bounds (implicitly) take the maximum of (i) a bound for the weak CSR expansion to hold, which does not depend on the values of the entries of the matrix but only on its pattern, and (ii) a bound for the CStR term to dominate. To improve and analyze (i), we consider various cycle replacement techniques and show that some of the known bounds for indices and exponents of digraphs apply here. We also show how to make use of various parameters of digraphs. To improve and analyze (ii), we introduce three different kinds of weak CSR expansions (named after Nachtigall, Hartman-Arguelles, and Cycle Threshold). As a result, we obtain a collection of bounds, in general incomparable to one another, but better than the bounds found in the literature.

Commentaires: 37 pages

A coupling approach to estimating the Lyapunov exponent of stochastic max-plus linear systems

Auteur(s): Goverde Rob, Heidergott Bernd, Merlet G.

(Article) Publié: European Journal Of Operational Research, vol. p. (2011)

Ref HAL: hal-01263221_v1
DOI: 10.1016/j.ejor.2010.09.035
Exporter : BibTex | endNote
Résumé:

This paper addresses the problem of approximately computing the Lyapunov exponent of stochastic max-plus linear systems. Our approach allows for an efficient simulation of bounds for the Lyapunov expo-nent. We provide sufficient conditions for the convergence of the bounds. In particular, a perfect samplingscheme for the Lyapunov exponent is established. We illustrate the effectiveness of our bounds with anapplication to (real-life) railway systems.

Memory loss property for products of random matrices in the $(\max,+)$ algebra

Auteur(s): Merlet G.

(Article) Publié: Mathematics Of Operations Research, vol. p. (2010)

Ref HAL: hal-00001607_v3
Ref Arxiv: math.PR/0405452
DOI: 10.1287/moor.1090.0434
Ref. & Cit.: NASA ADS
Exporter : BibTex | endNote
Résumé:

Products of random matrices in the $(\max,+)$ algebra are used as a model for a class of discrete event dynamical systems. J. Mairesse proved that such a system couples in finite times with a unique stationary regime if and only if it has a memory loss property. We prove that the memory loss property is generic in the following sense : if it is not fulfilled, the support of the measure is included in a finite union of affine hyperplanes and in the discrete case the atoms of the measure are linearly related.

Commentaires: The article has been completely rewritten, in order to state more explicit results and allow the matrices' entries to be infinite. Moreover the results are illustrated on a simple production system.

Menu

Rechercher