Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
max-algebra; Alternating Method; two-sided systems; integer matrices
max-algebra; Alternating Method; two-sided systems; integer matrices
Summary:
The Alternating Method in max-algebra is an efficient approach for solving two-sided max-linear systems of the form $A \otimes x=B \otimes y$, where $A$, $B$ are matrices and $x$, $y$ are vectors of compatible sizes. This iterative procedure typically begins with a randomly chosen initial vector. In the case when matrices $A$ and $B$ are integer matrices and one is finite while the other has at least one finite element in each row and in each column, and provided that the initial vector is also an integer vector, an upper bound on the number of iterations can be determined. This paper proposes starting the Alternating Method with a vector selected based on the matrix elements of $\tilde{A}=(-A^\top) \otimes A$, where $A$ is a finite matrix of the given system, instead of using a randomly selected vector. This choice of initial vector aims to minimize the number of iterations in the Alternating Method. We have proved that, with the proposed choice of initial vector, the number of iterations is bounded above by the expression containing the maximum element of matrix $\tilde{A}$. From this statement, we derive additional conclusions regarding this bound. Finally, we compare the number of iterations in the Alternating Method when it starts from a randomly chosen vector versus when it starts from the vector we propose in this study.
References:
[1] Akian, M., Bapat, R., Gaubert, S.: Max-plus algebra. In: Handbook of linear algebra, Chapter 25 (L. Hogben, R. Brualdi, A. Greenbaum, and R. Mathias, eds.), Chapman and Hall, 2007. DOI
[2] Aminu, A., Olowo, S., Sulaiman, I., Bakar, N. Abu, Mamat, M.: On application of max-plus algebra to synchronized discrete event system. Math. Statist. 9 (2021), 2, 81-92. DOI
[3] Aminu, A., Butkovič, P.: Comparison of methods for solving two-sided systems in max-algebra. University of Birmingham, preprint 2008/8. DOI
[4] Baccelli, F., Cohen, G., Olsder, G., Quadrat, J.: Synchronization and linearity: An algebra for discrete event systems. J. Oper. Res. Soc. 45 (1994), 118-119. DOI
[5] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer Verlag, London 2010. DOI | Zbl 1202.15032
[6] Butkovič, P.: On certain properties of the systems of linear extremal equations. Ekon. Mat. Obzor 14 (1978), 72-78. DOI
[7] Butkovič, P.: Solution of systems of linear extremal equations. Ekon. Mat. Obzor 17 (1981), 402-416. DOI
[8] Butkovič, P., Hegedus, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekon. Mat. Obzor 20 (1984), 203-215. DOI
[9] Butkovič, P.: Max-algebra: the linear algebra of combinatorics?. Linear Algebra Appl. 367 (2003), 313-335. DOI | Zbl 1022.15017
[10] Butkovič, P.: A strongly polynomial algorithm for solving two-sided linear systems in max-algebra. Discrete Appl. Math. 154 (2006), 437-446. DOI
[11] Carre, B A.: An algebra for network routing problems. J. Institute of Mathematics and Its Applications 7 (1971), 273-294. DOI
[12] Cohen, G., Gaubert, S., Mancinelli, E., Quadrat, J. P., Rofman, E.: On traffc light control of regular towns. Math. Notae, Boletin del Instituto de Matematica "Beppo Levi", Ano XLIII, (2005), 51-62. DOI
[13] Cuninghame-Green, R. A., Butkovič, P.: The equation $A\otimes x = B \otimes y$ over $(\max, +)$. Theoret. Comput. Sci. 293 (2003), 3-12. DOI
[14] Cuninghame-Green, R. A.: Projections in minimax algebra. Math. Program. 10 (1976), 1, 111-123. DOI
[15] Cuninghame-Green, R. A.: Minimax Algebra. Lecture Notes Econom. Math. Systems 166, Springer, Berlin 1979. DOI | Zbl 0739.90073
[16] Cuninghame-Green, R. A.: Minimax algebra and applications. Advances Imaging Electron Physics 90 (1994), 1-121. DOI | Zbl 0739.90073
[17] Cuninghame-Green, R. A.: Process synchronisation in a steelworks - a problem of feasibility. In: Proc. 2nd Int. Conf. on Operational Research (Banbury and Maitland, eds.), English University Press (1960), pp. 323-328.
[18] Cuninghame-Green, R. A.: Describing industrial processes with interference and approximating their steady-state behaviour. Oper. Res. Quarterly 13 (1962), 95-100. DOI
[19] Gaubert, S.: Methods and Applications of $(\max,+)$ Linear Algebra. Research Report RR3088, INRIA 1997. DOI
[20] Gaubert, S.: Nonlinear Perron-Frobenius theory and discrete event systems. Actes du colloque Modelisation de Systmes Ractifs (MSR'05) JESA 39 (2005), 175-190. DOI
[21] Giffler, B.: Scheduling general production systems using schedule algebra. Naval Res. Logist. Quarterly 10 (1963), 237-255. DOI
[22] Gondran, M., Minoux, M.: Valeurs propres et vecteur propres dans les dioides et leur interpretation en theorie des graphes. Bulletin de la Direction des Etudes et Recherches Serie C Mathematiques et Informatiques 2 (1977), 25-41.
[23] Heidergott, B., Olsder, G. J., Woude, J. van der: Max-plus at work, Modelling and Analysis of Synchronized Systems: A course on Max-Plus Algebra and Its Applications. Princeton University Press, New Jersey 2006. DOI
[24] Jones, D.: On two-sided Max-Linear equations. Discr. Appl. Math. 254 (2019), 146-160. DOI
[25] Krivulin, N., Sergeev, S.: Minimizing maximum lateness in two-stage projects by tropical optimization. Kybernetika 58 (2022), 5, 816-841. DOI
[26] Li, P.: On sparsity of approximate solutions to max-plus linear systems. Kybernetika 60 (2024), 3, 412-425. DOI
[27] Sergeev, S.: Alternating Method for homogeneous systems of equations over max-algebra. School of Mathematics pre-print, University of Birmingham, 18 (2009). DOI
[28] Stojčetović, B.: Max-algebraic systems of equations - from basic to higher level. In: The Fourth International Conference on Education in Mathematics, Physics and Related Science, Skopje 2023.
[29] Stojčetović, B., Ignjatović, J., Ćirić, M.: Pseudo skew-symmetric matrices over max-plus algebras. Accepted for publication in Filomat.
[30] Vorobyov, N. N.: Extremal algebra of positive matrices. Elektronische Informationsverarbeitung und Kybernetik 3 (1967), 39-71 (in Russian).
[31] Zimmermann, K.: Extremalni algebra. Vyzkumna publikace Ekonomicko-matematicke laboratore pri Ekonomickem ustavu CSAV 46, Praha 1976. (in Czech).
Search
Partner of
