Orbits and critical components of matrices in max-min algebra

DOI10.1016/J.LAA.2007.05.017MaRDI QIDQ996299zbMATH OpenOpenAlexFDO

Authors Blanka Semančíková

Publication date 14 September 2007

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

Full work available at URL https://doi.org/10.1016/j.laa.2007.05.017

zbMATH Keywords

algorithmcomputational complexitymax-min algebraorbit of matrixperiodic orbitpowers of matrices

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Algebraic systems of matrices (15A30) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Periodic orbits of vector fields and flows (37C27) Complexity and performance of numerical algorithms (65Y20)

Review text

The paper deals with a speed-up of a known \(O(n^3)\) algorithm computing the period of a periodic orbit in max-min algebra. An orbit in the max-min algebra is a sequence of the state vectors \(x(r)\), \(r\in \mathbb{N}\) of a max-min system \(x(r+1)=A\otimes x(r)\), where the matrix multiplication is defined with respect to the operations \(\oplus=\max\) and \(\otimes=\min\). In 2006, the author gave an \(O(n^3)\) algorithm computing the period of a periodic orbit [ibid. 414, No.~1, 38--63 (2006; Zbl 1125.15020)]. In this paper, the computational complexity of this algorithm is decreased by using only those coordinate-orbits, which correspond to the minimal non-trivial threshold components, called the critical components, of the transition matrix. All parts of the new algorithm except the computing of the critical components have complexity \(O(n^2)\). The formula for the orbit period presented in this paper is optimal in the following sense: the number of coordinate-orbits in the formula cannot be reduced. The formula is also helpful in solving the converse problem: generating an orbit with a prescribed period. This is demonstrated by examples. Furthermore, the paper shows that the non-critical coordinates of the state vector after \(n-1\) steps can be ignored, how to generate a known periodic regime by using a small number of coordinates of the state vector and that the difference between the defect of an orbit and the quasidefect of its critical coordinates is small. The final part deals with the situation when the matrix is reduced after the orbit has reached its periodic regime.

Recommendations

• Orbits in max--min algebra
• scientific article; zbMATH DE number 1508985
• Computing orbit period in max-min algebra
• Computing matrix period in max--min algebra
• Matrix period in max-algebra

Cites work

• Combinatorial matrix theory
• Computing a graph's period quadratically by node condensation
• Computing matrix period in max--min algebra
• Computing orbit period in max-min algebra
• Eigenvectors in Bottleneck algebra
• scientific article; zbMATH DE number 3779513 (Why is no real title available?)
• scientific article; zbMATH DE number 1516306 (Why is no real title available?)
• scientific article; zbMATH DE number 908181 (Why is no real title available?)
• On the powers of matrices in bottleneck/fuzzy algebra
• Orbits in max--min algebra
• Powers of matrices over distributive lattices -- a review
• Residuation in fuzzy algebra and some applications

Cited in

(8)

• Computing orbit period in max-min algebra
• CSR expansions of matrix powers in max algebra
• scientific article; zbMATH DE number 434963 (Why is no real title available?)
• Critical graph of max-plus matrices and applications in period optimization for traffic systems
• Max-algebraic attraction cones of nonnegative irreducible matrices
• On the \(\lambda \)-robustness of matrices over fuzzy algebra
• Orbits in max--min algebra
• Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes

This page was built for publication: Orbits and critical components of matrices in max-min algebra

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