On the maxmin-$\omega$ eigenspaces and their over-approximation by zones

Abstract

Maxmin-$\omega$ dynamical systems were previously introduced as a generalization of dynamical systems expressed by tropical linear algebra. To describe steady states of such systems one has to study an eigenproblem of the form $A{\otimes }_{\omega }x=\lambda +x$ where ${\otimes }_{\omega }$ is the maxmin-$\omega$ matrix-vector multiplication. This eigenproblem can be viewed in more general framework of nonlinear Perron-Frobenius theory. However, instead of studying such eigenspaces directly we develop a different approach: over-approximation by zones. These are traditionally convex sets of special kind which proved to be highly useful in computer science and also relevant in tropical convexity. We first construct a sequence of zones over-approximating a maxmin-$\omega$ eigenspace. Next, the limit of this sequence is refined in a heuristic procedure, which yields a refined zone and also the eigenvalue $\lambda$ with a high success rate. Based on the numerical experiments, in successful cases there is a column of the difference bound matrix (DBM) representation of the refined zone which yields an eigenvector.

21 pages