Weak CSR expansions and transience bounds in max-plus algebra
From MaRDI portal
Publication:406485
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.
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
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 627763 (Why is no real title available?)
- scientific article; zbMATH DE number 1542661 (Why is no real title available?)
- scientific article; zbMATH DE number 2221679 (Why is no real title available?)
- scientific article; zbMATH DE number 2221696 (Why is no real title available?)
- An extension of the Dulmage-Mendelsohn theorem
- Applications of max algebra to diagonal scaling of matrices
- CSR expansions of matrix powers in max algebra
- Computational Complexity of Nachtigall's Representation
- Diagonally dominant matrices
- Gaps in the exponent set of primitive matrices
- Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
- Max-Balancing Weighted Directed Graphs and Matrix Scaling
- Max-linear systems. Theory and algorithms.
- New transience bounds for max-plus linear systems
- On a sharp estimation in the theory of binary relations on a finite set
- On the exponent of a primitive digraph
- On the index of convergence of an irreducible Boolean matrix
- On visualization scaling, subeigenvectors and Kleene stars in max algebra
- Powers of matrices over an extremal algebra with applications to periodic graphs
- Transience bounds for long walks
- Unzerlegbare, nicht negative Matrizen
Cited in
(16)- Non-surjective linear transformations of tropical matrices preserving the cyclicity index
- New transience bounds for max-plus linear systems
- Computation of the transient in max-plus linear systems via SMT-solving
- scientific article; zbMATH DE number 7670358 (Why is no real title available?)
- 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
- A bound for the rank-one transient of inhomogeneous matrix products in special case.
- Transience bounds for long walks
- CSR expansions of matrix powers in max algebra
- 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
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)
