Numerical Computation of Spectral Elements in Max-Plus Algebra

: We describe the specialization to max-plus algebra of Howard's policy improvement scheme, which yields an algorithm to compute the solutions of spectral problems in the max-plus semiring. Experimentally, the algorithm shows a remarkable (almost linear) average execution time. Resume: Nous specialisons a l'algebre max-plus l'iteration sur les politiques de Howard, qui fournit un algorithme pour calculer valeurs propres et vecteurs propres dans cette algebre. Le temps d'execution de l'algorithme est experimentalement presque lineaire. Keywords: Max-plus semiring, eigenvalue, eigenvector, maximal circuit mean, cycle time, policy iteration 1. INTRODUCTION The max-plus semiring R max is the set R # {-#}, equipped with max, written additively (a # b = max(a, b)), and +, written multiplicatively (a# b = a + b). The zero element will be denoted by 0 (0 = -#), the unit element will be denoted by 1 (1 = 0). We will adopt the usual algebraic conventions, writing for instance ab..