The level set method for the two-sided max-plus eigenproblem

DOI10.1007/S10626-012-0137-ZzbMATH Open1279.15024arXiv1006.5702OpenAlexW2109513024MaRDI QIDQ2393147FDOQ2393147

Authors: Stéphane Gaubert, Sergey M. Sergeev 

Publication date: 7 August 2013

Published in: Discrete Event Dynamic Systems (Search for Journal in Brave)

Abstract: We consider the max-plus analogue of the eigenproblem for matrix pencils Ax=lambda Bx. We show that the spectrum of (A,B) (i.e., the set of possible values of lambda), which is a finite union of intervals, can be computed in pseudo-polynomial number of operations, by a (pseudo-polynomial) number of calls to an oracle that computes the value of a mean payoff game. The proof relies on the introduction of a spectral function, which we interpret in terms of the least Chebyshev distance between Ax and lambda Bx. The spectrum is obtained as the zero level set of this function.

Full work available at URL: https://arxiv.org/abs/1006.5702

Recommendations

• On the problem \(Ax= \lambda Bx\) in max algebra: Every system of intervals is a spectrum
• On special cases of the generalized max-plus eigenproblem
• Eigenproblem for optimal-node matrices in max-plus algebra
• scientific article; zbMATH DE number 2221679
• \(\ell\)-parametric eigenproblem in max-algebra

zbMATH Keywords

spectrummatrix pencilmax-plus algebradiscrete event systemsgeneralized eigenproblemChebyshev distancenonlinear Perron-Frobenius theorymin-max function

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Max-plus and related algebras (15A80) Discrete event control/observation systems (93C65) Matrix pencils (15A22) Combinatorial games (91A46)

Cites Work

• The complexity of mean payoff games on graphs
• Tropical convexity
• Multiorder, Kleene stars and cyclic projectors in the geometry of max cones
• Max-linear systems. Theory and algorithms.
• Title not available (Why is that?)
• The tropical analogue of polar cones
• Tropical polar cones, hypergraph transversals, and mean payoff games
• Minimax algebra
• The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
• Tropical polyhedra are equivalent to mean payoff games
• Title not available (Why is that?)
• Tropical linear-fractional programming and parametric mean payoff games
• Eigenvalues of dynamic max-min systems
• Max-algebra: The linear algebra of combinatorics?
• Perturbation of eigenvalues of matrix pencils and the optimal assignment problem
• Title not available (Why is that?)
• Asymptotics of the Perron eigenvalue and eigenvector using max-algebra
• Title not available (Why is that?)
• Idempotent functional analysis: An algebraic approach
• Convexity and log convexity for the spectral radius
• Min-max functions
• Title not available (Why is that?)
• Scheduling with AND/OR Precedence Constraints
• Stochastic Games with Perfect Information and Time Average Payoff
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• The duality theorem for min-max functions
• A constructive fixed point theorem for min-max functions
• Generalisation of the Perron-Frobenius theory to matrix pencils
• Cyclic projectors and separation theorems in idempotent convex geometry
• Z-Pencils
• Best approximation in max-plus semimodules
• A generalized eigenvalue problem in the max algebra
• An algorithm for exact bounds on the time separation of events in concurrent systems
• A method to find all solutions of a system of multivariate polynomial equalities and inequalities in the max algebra
• On the problem \(Ax= \lambda Bx\) in max algebra: Every system of intervals is a spectrum

Cited In (13)

• On tropical fractional linear programming
• A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Weakly linear systems for matrices over the max-plus quantale
• On max-plus linear dynamical system theory: the regulation problem
• Weak dual residuations applied to tropical linear equations
• Matrix representation of formal polynomials over max-plus algebra
• Eigenvalue methods for sparse tropical polynomial systems
• Analysis and control of max-plus linear discrete-event systems: an introduction
• On the problem \(Ax= \lambda Bx\) in max algebra: Every system of intervals is a spectrum
• On special cases of the generalized max-plus eigenproblem
• A basis theorem for a class of max-plus eigenproblems.
• On the continuity of the generalized spectral radius in max algebra

This page was built for publication: The level set method for the two-sided max-plus eigenproblem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2393147)