Сравнительный анализ алгоритмов решения тропических уравнений: от метода резольвенты до алгоритма Григорьева
DOI:
https://doi.org/10.32603/2071-2340-2025-4-27-48Ключевые слова:
Тропическая алгебра, мин-плюс полукольцо, тропические линейные системы, метод резольвенты, алгоритм Григорьева, тропическое двойственное описание, алгоритм передачи сообщений, вычислительная сложностьАннотация
Тропическая алгебра, оперирующая в полукольцах с идемпотентными операциями, стала фундаментальным инструмент для моделирования дискретных событий, задач оптимизации и анализа сетей. В данной статье проводится систематический сравнительный анализ алгоритмов решения тропических линейных уравнений. Рассмотрены метод резольвенты, алгоритм Григорьева, метод тропического двойственного описания, комбинаторный метод поиска главного решения, а также алгоритм передачи сообщений на фактор-графах. Оценены их вычислительная сложность, условия сходимости и области применимости. Сформулированы практические рекомендации по выбору метода в зависимости от структуры задачи и доступных вычислительных ресурсов.
Библиографические ссылки
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.
Опубликован
Выпуск
Раздел
Лицензия
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
