On the solution of a two-sided vector equation in tropical algebra. (English. Russian original) Zbl 1518.15020
Vestn. St. Petersbg. Univ., Math. 56, No. 2, 172-181 (2023); translation from Vestn. St-Peterbg. Univ., Ser. I, Mat. Mekh. Astron. 10(68), No. 2, 236-248 (2023).
Summary: In the context of tropical mathematics, the problem of solving a vector equation with two given matrices and unknown vectors, each part of which has the form of a product of one of the matrices and an unknown vector, is considered. Such an equation, which has an unknown vector on either side of the equal sign, is often called a two-sided equation. A new procedure for solving two-sided equations is proposed based on minimizing some distance function between the vectors of tropical vector spaces that are generated by the columns of each of the matrices. As a result of the procedure, a pair of vectors is obtained, which provides a minimum distance between the spaces and the value of the distance itself. If the equation has solutions, then the resulting vectors are the solution to the equation. Otherwise, these vectors define a pseudo-solution that minimizes the deviation of one side of the equation from the other. Execution of the procedure consists in constructing a sequence of vectors that are pseudo-solutions of the two-sided equation in which the left and right sides are alternately replaced by constant vectors. Unlike the well-known alternating algorithm, in which the corresponding inequalities are solved one by one instead of equations, the proposed procedure uses a different argument, looks simpler, and allows one to establish natural criteria for completing calculations. If the equation has no solutions, the procedure also finds a pseudo-solution and determines the value of the error associated with it, which can be useful in solving approximation problems.
MSC:
| 15A24 | Matrix equations and identities |
| 15A06 | Linear equations (linear algebraic aspects) |
| 14T10 | Foundations of tropical geometry and relations with algebra |
Keywords:
idempotent semifield; tropical vector space; generalized metric; two-sided vector equation; iterative computational procedure; pseudo-solutionReferences:
| [1] | V. N. Kolokoltsov and V. P. Maslov, Idempotent Analysis and Its Applications (Springer-Verlag, Dordrecht, 1997), in Ser.: Mathematics and Its Applications, Vol. 401. doi:10.1007/978-94-015-8901-7 · Zbl 0941.93001 |
| [2] | J. S. Golan, Semirings and Affine Equations over Them (Springer-Verlag, New York, 2003), in Ser.: Mathematics and Its Applications, Vol. 556. doi:10.1007/978-94-017-0383-3 · Zbl 1042.16038 |
| [3] | B. Heidergott, G. J. Olsder, and J. van der Woude, Max Plus at Work (Princeton Univ. Press, Princeton, 2006), in Ser.: Princeton Series in Applied Mathematics. · Zbl 1130.93003 |
| [4] | M. Gondran and M. Minoux, Graphs, Dioids and Semirings: New Models and Algorithms (Springer-Verlag, New York, 2008), in Ser.: Operations Research/Computer Science Interfaces Series, Vol. 41. doi:10.1007/978-0-387-75450-5 · Zbl 1201.16038 |
| [5] | P. Butkovič, Max-Linear Systems: Theory and Algorithms (Springer-Verlag, London, 2010), in Ser.: Springer Monographs in Mathematics. doi:10.1007/978-1-84996-299-5 · Zbl 1202.15032 |
| [6] | D. Maclagan and B. Sturmfels, Introduction to Tropical Geometry (American Mathematical Society, Providence, R.I., 2015), in Ser.: Graduate Studies in Mathematics, Vol. 161. doi:10.1090/gsm/161 · Zbl 1321.14048 |
| [7] | Butkovič, P., “On certain properties of the systems of linear extremal equations,” Ekon.-, Mat. Obz., 14, 72-78 (1978) · Zbl 0381.15008 |
| [8] | Butkovič, P., “Solution of systems of linear extremal equations,” Ekon.-, Mat. Obz., 17, 402-416 (1981) · Zbl 0533.90057 |
| [9] | Butkovič, P.; Hegedüs, G., “An elimination method for finding all solutions of the system of linear equations over an extremal algebra,” Ekon.-, Mat. Obz., 20, 203-215 (1984) · Zbl 0545.90101 |
| [10] | Cuninghame-Green, R. A.; Butkovič, P., The equation A⊗x = B⊗y over (max,+), Theor. Comput. Sci., 293, 3-12 (2003) · Zbl 1021.65022 · doi:10.1016/S0304-3975(02)00228-1 |
| [11] | Butkovič, P.; Zimmermann, K., A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Discrete Appl. Math., 154, 437-446 (2006) · Zbl 1090.68119 · doi:10.1016/j.dam.2005.09.008 |
| [12] | Lorenzo, E.; de la Puente, M. J., An algorithm to describe the solution set of any tropical linear system A☉x = B☉x, Linear Algebra Appl., 435, 884-901 (2011) · Zbl 1217.65076 · doi:10.1016/j.laa.2011.02.014 |
| [13] | Jones, D., On two-sided max-linear equations, Discrete Appl. Math., 254, 146-160 (2019) · Zbl 1407.15017 · doi:10.1016/j.dam.2018.06.011 |
| [14] | P. Butkovič, “On properties of solution sets of extremal linear programs,” in Algebraic and Combinatorial Methods in Operations Research (North-Holland, Amsterdam, 1984), in Ser.: North-Holland Mathematics Studies, vol. 95, pp. 41-54. doi:10.1016/S0304-0208(08)72952-9 · Zbl 0567.90066 |
| [15] | E. A. Walkup, G. Borriello, J. M. Taylor, and M. A. Atiyah, “A general linear max-plus solution technique,” in Idempotency (Cambridge Univ. Press, Cambridge, 1998), in Ser.: Publications of the Newton Institute, pp. 406-415. doi:10.1017/CBO9780511662508.024 · Zbl 0898.68035 |
| [16] | Cuninghame-Green, R. A.; Zimmermann, K., Equation with residuated functions, Comment. Math. Univ. Carol., 42, 729-740 (2001) · Zbl 1068.93039 |
| [17] | Krivulin, N. K., Methods of Idempotent Algebra for Problems in Modeling and Analysis of Complex Systems (2009), St. Petersburg: S.-Peterb. Gos. Univ., St. Petersburg |
| [18] | Krivulin, N. K., “On solution of a class of linear vector equations in idempotent algebra,” Vestn. S.-, Peterb. Univ.: Prikl. Mat. Inf. Protsessy Upr., 5, 63-76 (2009) |
| [19] | N. K. Krivulin, “On solution of linear vector equations in idempotent algebra,” in Mathematical Models: Theory and Applications (VVM, St. Petersburg, 2004), Vol. 5, pp. 105-113 [in Russian]. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
