Comparative Analysis of Algorithms for Solving Tropical Equations: From the Residuation Method to the Grigoriev Algorithm
DOI:
https://doi.org/10.32603/2071-2340-2025-4-27-48Keywords:
Tropical algebra, min-plus semiring, tropical linear systems, residuation method, Grigoriev algorithm, tropical double description method, message passing algorithm, computational complexityAbstract
Tropical algebra, operating in semirings with idempotent operations, has become a fundamental tool for modeling discrete events, optimization problems, and network analysis. This paper provides a systematic comparative analysis of algorithms for solving tropical linear equations. The residuation method, the Grigoriev algorithm, the tropical double description method, the combinatorial method for finding the principal solution, as well as the message passing algorithm on factor graphs are considered. Their computational complexity, convergence conditions, and areas of applicability are evaluated. Practical recommendations for choosing a method depending on the problem structure and available computing resources are formulated.
References
F. Baccelli, G. Cohen, G. Olsder, and J.-P. Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems, New York, NY, USA: Wiley, 1992.
R. A. Cuninghame-Green, Minimax Algebra, Berlin, Germany: Springer-Verlag, 1979, p. 258.
E. Bortoletto, N. Lindner, and B. Masing, “The tropical and zonotopal geometry of periodic timetables,” Discrete & Computational Geometry, vol. 73, no. 3, pp. 719–763, 2025, doi: 10.1007/s00454-024-00686-2.
M. Akian, S. Gaubert, and A. Guterman, “Tropical polyhedra are equivalent to mean payoff games,” International Journal of Al- gebra and Computation, vol. 22, no. 01, p. 1250001, 2012, doi: 10.1142/S0218196711006674.
P. Maragos, V. Charisopoulos, and E. Theodosis, “Tropical geometry and machine learning,” Proceedings of the IEEE, vol. 109, no. 5, pp. 728–755, 2021, doi: 10.1109/jproc.2021.3065238.
R. Yoshida, L. Zhang, and X. Zhang, “Tropical principal component analysis and its application to phylogenetics,” Bulletin of Mathematical Biology, vol. 81, no. 2, pp. 568–597, 2019, doi: 10.1007/s11538-018- 0493-4.
P. Butkovič, Max-linear Systems: Theory and Algorithms, New York, NY, USA: Springer, 2010, doi: 10.1007/978-1-84996-299-5.
G. Cohen, S. Gaubert, and J.-P. Quadrat, “Duality and separation the- orems in idempotent semimodules,” Linear Algebra and its Applications, vol. 379, pp. 395–422, 2004, doi: 10.1016/j.laa.2003.08.010.
D. Grigoriev, “Complexity of solving tropical linear systems,” Computa- tional Complexity, vol. 22, no. 1, pp. 71–88, 2013, doi: 10.1007/s00037- 012-0053-5.
R. A. Cuninghame-Green and P. Butkovič, “The equation A⊗x = B ⊗y over (max,+),” Theoretical Computer Science, vol. 293, no. 1, pp. 3–12, 2003, doi: 10.1016/s0304-3975(02)00228-1.
U. Zwick and M. Paterson, “The complexity of mean payoff games on graphs,” Theoretical Computer Science, vol. 158, no. 1-2, pp. 343–359, 1996, doi: 10.1016/0304-3975(95)00188-3.
X. Allamigeon, S. Gaubert, and E. Goubault, “The tropical dou- ble description method,” in 27th International Symposium on Theo- retical Aspects of Computer Science (STACS), 2010, pp. 47–58, doi: 10.4230/LIPIcs.STACS.2010.2443.
S. M. Aji and R. J. McEliece, “The generalized distributive law,” IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 325–343, 2000, doi: 10.1109/18.825794.
S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Dis- tributed optimization and statistical learning via the alternating di- rection method of multipliers,” Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1–122, 2011, doi: 10.1561/2200000016.
Y. Weiss, “Correctness of local probability propagation in graphical models with loops,” Neural Computation, vol. 12, no. 1, pp. 1–41, 2000, doi: 10.1162/089976600300015880.
M. J. Wainwright and M. I. Jordan, “Graphical models, exponential families, and variational inference,” Foundations and Trends in Machine Learning, vol. 1, no. 1-2, pp. 1–305, 2008, doi: 10.1561/2200000001.
M. Gondran and M. Minoux, Graphs, Dioids and Semirings, New York, NY, USA: Springer, 2008, doi: 10.1007/978-0-387-75450-5.
G. L. Litvinov, “The maslov dequantization, idempotent and tropical mathematics: a brief introduction,” J. Math. Sci. (N. Y.), vol. 140, pp. 426–444, 2007, doi: 10.1007/s10958-007-0450-5.
F. R. Kschischang, B. J. Frey, and H. A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Transactions on Information The- ory, vol. 47, no. 2, pp. 498–519, 2001, doi: 10.1109/18.910572.
X. Allamigeon, S. Gaubert, and E. Goubault, “Computing the ver- tices of tropical polyhedra using directed hypergraphs,” Discrete & Computational Geometry, vol. 49, no. 2, pp. 247–279, 2013, doi: 10.1007/s00454-012-9469-6.
L. G. Khachiyan, “A polynomial algorithm in linear programming,” Dokl. Akad. Nauk SSSR, vol. 244, no. 5, pp. 1093–1096, 1979.
X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig, “Log-barrier interior point methods are not strongly polynomial,” SIAM Journal on Applied Algebra and Geometry, vol. 2, no. 1, pp. 140–178, 2018, doi: 10.1137/17m1142132.
A. P. Davydow, “Upper and lower bounds for grigoriev’s algorithm for solving integral tropical linear systems,” J. Math. Sci. (N. Y.), vol. 192, no. 3, pp. 295–302, 2012, doi: 10.1007/s10958-013-1395-5.
J. Cochet-Terrasson, S. Gaubert, and J. Gunawardena, “A con- structive fixed point theorem for min-max functions,” Dynamics and Stability of Systems, vol. 14, no. 4, pp. 407–433, 1999, doi: 10.1080/026811199281967.
G. Elidan, I. McGraw, and D. Koller, “Residual belief propagation,” in Proceedings of the 22nd Conference on Uncertainty in Artificial Intel- ligence (UAI), 2006, pp. 165–173.
D. Maclagan and B. Sturmfels, Introduction to Tropical Geometry, Providence, RI, USA: American Mathematical Society, 2015, doi: 10.1090/gsm/161.
T. Bogart, A. N. Jensen, D. Speyer, B. Sturmfels, and R. R. Thomas, “Computing tropical varieties,” Journal of Symbolic Computation, vol. 42, no. 1-2, pp. 54–73, 2007, doi: 10.1016/j.jsc.2006.02.004.
D. Grigoriev and V. Podolskii, “Tropical effective primary and dual nullstellensatz,” in 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), 2015, pp. 379–391, doi: 10.4230/LIPIcs.STACS.2015.379.
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
This work is licensed under a Creative Commons Attribution 4.0 International License.
