Weak CSR expansions and transience bounds in max-plus algebra

DOI10.1016/J.LAA.2014.07.027zbMATH Open1314.15018arXiv1310.2475OpenAlexW2076004788MaRDI QIDQ406485FDOQ406485

Authors: Glenn Merlet, Thomas Nowak, Sergey M. Sergeev 

Publication date: 8 September 2014

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: 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: A^t=CS^tR + B^t. 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 CS^tR 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.

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

Recommendations

• On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers
• An overview of transience bounds in max-plus algebra
• CSR expansions of matrix powers in max algebra
• New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank
• New transience bounds for max-plus linear systems

zbMATH Keywords

transientdigraphsperiodicitymatrix powersmax-plus

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Factorization of matrices (15A23) Max-plus and related algebras (15A80)

Cites Work

• Title not available (Why is that?)
• Max-linear systems. Theory and algorithms.
• Title not available (Why is that?)
• On visualization scaling, subeigenvectors and Kleene stars in max algebra
• Max-Balancing Weighted Directed Graphs and Matrix Scaling
• Applications of max algebra to diagonal scaling of matrices
• Title not available (Why is that?)
• Unzerlegbare, nicht negative Matrizen
• An extension of the Dulmage-Mendelsohn theorem
• Gaps in the exponent set of primitive matrices
• Powers of matrices over an extremal algebra with applications to periodic graphs
• Transience bounds for long walks
• CSR expansions of matrix powers in max algebra
• Computational Complexity of Nachtigall's Representation
• Diagonally dominant matrices
• On the index of convergence of an irreducible Boolean matrix
• Title not available (Why is that?)
• New transience bounds for max-plus linear systems
• On a sharp estimation in the theory of binary relations on a finite set
• Title not available (Why is that?)
• On the exponent of a primitive digraph
• Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes

Cited In (14)

• A bound for the rank-one transient of inhomogeneous matrix products in special case
• Computation of the transient in max-plus linear systems via SMT-solving
• Title not available (Why is that?)
• New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank
• On the index of convergence of a class of Boolean matrices with structural properties
• On the tropical two-sided discrete logarithm and a key exchange protocol based on the tropical algebra of pairs
• Transience bounds for long walks
• Cryptanalysis of a key exchange protocol based on a modified tropical structure
• Computing transience bounds of emergency call centers: a hierarchical timed Petri net approach
• An overview of transience bounds in max-plus algebra
• Semigroup identities of supertropical matrices
• On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers
• On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product
• Non-surjective linear transformations of tropical matrices preserving the cyclicity index

This page was built for publication: Weak CSR expansions and transience bounds in max-plus algebra

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