On solution of two-sided vector equation in tropical algebra
DOI:
https://doi.org/10.21638/spbu01.2023.205Abstract
The problem of solving, in the context of tropical mathematics, 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 unknown vectors on either side of the equal sign, is often called a two-sided equation. A new procedure for solving the two-sided equation is proposed based on minimizing a certain distance function between 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 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. The execution of the procedure consists in constructing a sequence of vectors that are pseudosolutions of the two-sided equation in which the left and right sides are alternately replaced by constant vectors. Unlike the well known alternation 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.Keywords:
idempotent semifield, tropical vector space, heneralized metric, two-sided vector equation, iterative computational procedure, pseudo-solution
Downloads
Download data is not yet available.
References
Литература
1. Kolokoltsov V. N., Maslov V. P. Idempotent Analysis and Its Applications. In: Mathematics and Its Applications, vol. 401. Dordrecht, Springer (1997). https://doi.org/10.1007/978-94-015-8901-7
2. Golan J. S. Semirings and Affine Equations Over Them. In: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94-017-0383-3
3. Heidergott B., Olsder G. J., van der Woude J. Max Plus at Work. In: Princeton Series in Applied Mathematics. Princeton, Princeton University Press (2006).
4. Gondran M., Minoux M. Graphs, Dioids and Semirings. In: Operations Research. Computer Science Interfaces, vol. 41. New York, Springer (2008). https://doi.org/10.1007/978-0-387-75450-5
5. Butkoviˇc P. Max-linear Systems: Theory and Algorithms. In: Springer Monographs in Mathematics. London, Springer (2010). https://doi.org/10.1007/978-1-84996-299-5
6. Maclagan D., Sturmfels B. Introduction to Tropical Geometry. In: Graduate Studies in Mathematics, vol. 161. Providence, AMS (2015). https://doi.org/10.1090/gsm/161
7. Butkoviˇc P. On certain properties of the systems of linear extremal equations. Ekonom.-Mat. Obzor 14 (1), 72-78 (1978).
8. Butkoviˇc P. Solution of systems of linear extremal equations. Ekonom.-Mat. Obzor 17 (4), 402-416 (1981).
9. Butkoviˇc P., Heged¨us G. An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonom.-Mat. Obzor 20 (2), 203-215 (1984).
10. Cuninghame-Green R. A., Butkoviˇc P. The equation A ⊗ x = B ⊗ y over (max, +). Theoret. Comput. Sci. 293 (1), 3-12 (2003). https://doi.org/10.1016/S0304-3975(02)00228-1
11. Butkoviˇc P., Zimmermann K. A strongly polynomial algorithm for solving two-sided linear systems in max-algebra. Discrete Appl. Math. 154 (3), 437-446 (2006). https://doi.org/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 (4), 884-901 (2011). https://doi.org/10.1016/j.laa.2011.02.014
13. Jones D. On two-sided max-linear equations. Discrete Appl. Math. 254 (3), 146-160 (2019). https://doi.org/10.1016/j.dam.2018.06.011
14. Butkoviˇc P. On properties of solution sets of extremal linear programs. Algebraic and Combinatorial Methods in Operations Research. In: North-Holland Mathematics Studies, vol. 95, 41-54. Amsterdam, North-Holland (1984). https://doi.org/10.1016/S0304-0208(08)72952-9
15. Walkup E. A., Borriello G., Taylor J. M., Atiyah M. A. General linear max-plus solution technique. Idempotency. In: Publications of the Newton Institute, 406-415. Cambridge, Cambridge University Press (1998). https://doi.org/10.1017/CBO9780511662508.024
16. Cuninghame-Green R. A., Zimmermann K. Equation with residuated functions. Comment. Math. Univ. Carolin. 42 (4), 729-740 (2001).
17. Кривулин Н. К. Методы идемпотентной алгебры в задачахмоделирования и анализа сложныхсистем. С.-Петербург, Изд-во С.-Петерб. ун-та (2009).
18. Кривулин Н. К. О решении одного класса линейных векторных уравнений в идемпотентной алгебре. Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления 5 (3), 63-76 (2009).
19. Кривулин Н. К. О решении линейных векторных уравнений в идемпотентной алгебре. Математические модели. Теория и приложения 5, 105-113. Санкт-Петербург, Изд-во ВВМ (2004).
References
1. Kolokoltsov V. N., Maslov V. P. Idempotent Analysis and Its Applications. In: Mathematics and Its Applications, vol. 401. Dordrecht, Springer (1997). https://doi.org/10.1007/978-94-015-8901-7
2. Golan J. S. Semirings and Affine Equations Over Them. In: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94-017-0383-3
3. Heidergott B., Olsder G. J., van der Woude J. Max Plus at Work. In: Princeton Series in Applied Mathematics. Princeton, Princeton University Press (2006).
4. Gondran M., Minoux M. Graphs, Dioids and Semirings. In: Operations Research. Computer Science Interfaces, vol. 41. New York, Springer (2008). https://doi.org/10.1007/978-0-387-75450-5
5. Butkoviˇc P. Max-linear Systems: Theory and Algorithms. In: Springer Monographs in Mathematics. London, Springer (2010). https://doi.org/10.1007/978-1-84996-299-5
6. Maclagan D., Sturmfels B. Introduction to Tropical Geometry. In: Graduate Studies in Mathematics, vol. 161. Providence, AMS (2015). https://doi.org/10.1090/gsm/161
7. Butkoviˇc P. On certain properties of the systems of linear extremal equations. Ekonom.-Mat. Obzor 14 (1), 72-78 (1978).
8. Butkoviˇc P. Solution of systems of linear extremal equations. Ekonom.-Mat. Obzor 17 (4), 402-416 (1981).
9. Butkoviˇc P., Heged¨us G. An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonom.-Mat. Obzor 20 (2), 203-215 (1984).
10. Cuninghame-Green R. A., Butkoviˇc P. The equation A ⊗ x = B ⊗ y over (max, +). Theoret. Comput. Sci. 293 (1), 3-12 (2003). https://doi.org/10.1016/S0304-3975(02)00228-1
11. Butkoviˇc P., Zimmermann K. A strongly polynomial algorithm for solving two-sided linear systems in max-algebra. Discrete Appl. Math. 154 (3), 437-446 (2006). https://doi.org/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 (4), 884-901 (2011). https://doi.org/10.1016/j.laa.2011.02.014
13. Jones D. On two-sided max-linear equations. Discrete Appl. Math. 254 (3), 146-160 (2019). https://doi.org/10.1016/j.dam.2018.06.011
14. Butkoviˇc P. On properties of solution sets of extremal linear programs. Algebraic and Combinatorial Methods in Operations Research. In: North-Holland Mathematics Studies, vol. 95, 41-54. Amsterdam, North-Holland (1984). https://doi.org/10.1016/S0304-0208(08)72952-9
15. Walkup E. A., Borriello G., Taylor J. M., Atiyah M. A general linear max-plus solution technique. Idempotency. In: Publications of the Newton Institute, 406-415. Cambridge, Cambridge University Press (1998). https://doi.org/10.1017/CBO9780511662508.024
16. Cuninghame-Green R. A., Zimmermann K. Equation with residuated functions. Comment. Math. Univ. Carolin. 42 (4), 729-740 (2001).
17. Krivulin N. K. Methods of Idempotent Algebra for Problems in Modeling and Analysis of Complex Systems. St Petersburg, St Petersburg University Press (2009). (In Russian)
18. Krivulin N. K. On solution of a class of linear vector equations in idempotent algebra. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes 5 (3), 63-76 (2009). (In Russian)
19. On solution of linear vector equations in idempotent algebra. Mathematical Models. Theory and Applications 5, 105-113. St Petersburg, VVM Publ. (2004). (In Russian)
Downloads
Published
2023-05-10
How to Cite
Krivulin, N. K. (2023). On solution of two-sided vector equation in tropical algebra. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 10(2), 236–248. https://doi.org/10.21638/spbu01.2023.205
Issue
Section
Mathematics
License
Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.
