Universal algorithms for solving discrete stationary Bellman equations

G. L. Litvinov ; А. Ya. Rodionov ; S. Sergeev ; A. N. Sobolevski

Vestnik rossijskih universitetov. Matematika, Tome 24 (2019) no. 128, pp. 393-431

Résumé

This paper investigates algorithms for solving discrete stationary (or) matrix Bellman equations over semirings, in particular over tropical and idempotent semirings, Also there are presented some original algorithms, applications and programmed realization.

Détail

Keywords: tropical linear algebra; idempotent semirings; matrix Bellman equations; universal algorithms.

Bibliographie

[1] G. H. Golub and C. van Loan, Matrix Computations, John Hopkins Univ. Press, London, 1989 | MR | Zbl

[2] N. K. Krivulin, Methods of Idempotent Algebra in Problems of Modeling and Analysis of Complex Systems, Publishing House of St. Petersburg university, St. Petersburg, 2009 (In Russian)

[3] G. L. Litvinov, A. N. Sobolevsky, “Exact interval solutions of the discrete Bellman equation and polynomial complexity of idempotent linear algebra problems”, Doklady Mathematics, 374:3 (2000), 304–306, arXiv: (In Russian) math/0101041[math.LA] | MR | Zbl

[4] V. P. Maslov, “A new approach to generalized solutions of nonlinear systems”, Doklady Mathematics, 292:1 (1987), 29–33 (In Russian) | MR | Zbl

[5] V. P. Maslov, “On a new principle of superposition for optimization problems”, Russian Mathematical Surveys, 42:3 (1987), 43–54 | DOI | MR | Zbl

[6] V. P. Maslov, V. N. Kolokoltsov, Idempotent Analysis and Its Applications, Springer Science+Business Media Dordrecht, Dordrecht, 1997 | MR | MR

[7] R. Sedgewick, Algorithms in C++, part 5, Graph Algorithms, 3rd, Addison-Wesley Publishing Company, Inc., California, New York, Amsterdam, 2002 | MR

[8] S. Sergeev, “Universal algorithms for generalized discrete matrix Bellman equations with symmetric Toeplitz matrix”, Tambov University Reports. Series: Natural and Technical Sciences, 16:6–2 (2011), 1751–1758, arXiv: math/0612309

[9] S. N. Sergeev, A. V. Chourkin, “Universal algorithms solving discrete Bellman systems of equations over semirings”, Idempotent and Tropical Mathematics and Problems of Mathematical Physics. II, International Workshop “Idempotent and Tropical Mathematics and Problems of Mathematical Physics” (Independent University of Moscow, French–Russian Laboratory “J.-V. Poncelet”, Russia, August 25–30), Independent University of Moscow, Moscow, 2007, 107–109, arXiv: (In Russian) 0709.4119

[10] A. N. Sobolevsky, “Interval arithmetic and linear algebra over idempotent semirings”, Doklady Mathematics, 369:6 (1999), 747–749 (In Russian) | MR

[11] D. K. Faddeev, V. N. Faddeeva, Computational Methods of Linear Algebra, 3rd ed., Publishing house “Doe”, St. Petersburg, 2002 (In Russian) | MR

[12] G. Alefeld and J. Herzberger, Introduction to interval computations, Academic Press, New York, 1983 | MR | Zbl

[13] F. L. Baccelli, G. Cohen, G. J. Olsder and J. P. Quadrat, Synchronization and Linearity: an Algebra for Discrete Event Systems, Wiley and Sons, 1992 | MR | Zbl

[14] R. C. Backhouse, B. A. Carré, “Regular algebra applied to path-finding problems”, Journal of the Institute of Mathematics and its Applications, 15 (1975), 161–186 | DOI | MR | Zbl

[15] W. Barth, E. Nuding, “Optimale Lösung von Intervalgleichungsystemen”, Computing, 12 (1974), 117–125 | DOI | MR | Zbl

[16] P. Butkovič, Max-linear Systems: Theory and Algorithms, Springer, London, 2010 | MR | Zbl

[17] P. Butkovič, H. Schneider and S. Sergeev, “$Z$-matrix equations in max algebra, nonnegative linear algebra and other semirings”, 2011, arXiv: 1110.4564 | MR | Zbl

[18] B. A. Carré, “An algebra for network routing problems”, Journal of the Institute of Mathematics and its Applications, 7 (1971), 273–294 | DOI | MR | Zbl

[19] B. A. Carré, Graphs and Networks, Oxford Univ. Press, Oxford, 1979 | MR | Zbl

[20] K. Cechlárová and R. A. Cuninghame-Green, “Interval systems of max-separable linear equations”, Linear Algebra and its Applications, 340:1–3 (2002), 215–224 | MR | Zbl

[21] R. A. Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, 166, Springer, Berlin, 1979 | DOI | MR | Zbl

[22] M. Fiedler, J. Nedoma, J. Ramík, J. Rohn and K. Zimmermann, Linear optimization problems with inexact data, Springer, New York, 2006 | MR | Zbl

[23] J. Golan, Semirings and Their Applications, Kluwer Academic Publishers, 2000 | MR

[24] M. Gondran, “Path algebra and algorithms”, Combinatorial Programming: Methods and Applications, Proceedings of the NATO Advanced Study Institute held at the Palais des Congres (Versailles, France, 2–13 September, 1974), Reidel, Dordrecht, 1975, 137–148 | DOI | MR

[25] M. Gondran and M. Minoux, Graphs et Algorithms, Éditions Eylrolles, Paris, 1979 | MR

[26] M. Gondran and M. Minoux, Graphs, Dioids and Semirings, Springer, New York, 2010 | MR

[27] J. Gunawardena, Idempotency, Cambridge Univ. Press, Cambridge, 1998 | MR

[28] L. Hardouin, B. Cottenceau, M. Lhommeau, and E. Le Corronc, “Interval systems over idempotent semiring”, Linear Algebra and its Applications, 431 (2009), 855–862 | DOI | MR | Zbl

[29] V. Kreinovich, A. Lakeev, J. Rohn, and P. Kahl, Computational complexity and feasibility of data processing and interval computations, Applied Optimization, Kluwer Academic Publishers, Dordrecht, 1998 | DOI | MR | Zbl

[30] D. J. Lehmann, “Algebraic structures for transitive closure”, Theoretical Computer Science, 4 (1977), 59–76 | DOI | MR | Zbl

[31] G. L. Litvinov, “The Maslov dequantization, idempotent and tropical mathematics: a brief introduction”, Journal of Mathematical Sciences, 141:4 (2007), 1417–1428, arXiv: math/0507014[math.GM] | DOI | MR

[32] G. L. Litvinov and V. P. Maslov, “Idempotent mathematics: correspondence principle and applications”, Russian Mathematical Surveys, 51 (1996) | DOI | MR | Zbl

[33] G. L. Litvinov and V. P. Maslov, “The correspondence principle for idempotent calculus and some computer applications”, Idempotency, Cambridge Univ. Press, Cambridge, 1998, 420–443, arXiv: math/0101021[math.GM] | DOI | MR | Zbl

[34] G. L. Litvinov and V. P. Maslov, Idempotent mathematics and mathematical physics, AMS Contemporary Mathematics, 307, Providence, 2005 | DOI | MR

[35] G. L. Litvinov, V. P. Maslov, A. Ya. Rodionov, and A. N. Sobolevski{ĭ}, “Universal algorithms, mathematics of semirings and parallel computations”, Lecture Notes in Computational Science and Engineering, 75, 2011, 63–89, arXiv: 1005.1252 | DOI | MR

[36] G. L. Litvinov and E. V. Maslova, “Universal numerical algorithms and their software implementation”, Programming and Computer Software, 26:5 (2000), 275–280, arXiv: math/0102114[math.SC] | DOI | MR | Zbl

[37] G. L. Litvinov, A. Ya. Rodionov and A. V. Chourkin, “Approximate rational arithmetic and arbitrary precision computations for universal algorithms”, International Journal of Pure and Applied Mathematics, 45:2 (2008), 193–204 | MR | Zbl

[38] G. L. Litvinov and S. N. Sergeev, Tropical and Idempotent Mathematics, AMS Contemporary Mathematics, 495, Providence, 2009 | DOI | MR | Zbl

[39] G. L. Litvinov and A. N. Sobolevski{ĭ}, “Idempotent interval analysis and optimization problems”, Reliable Computing, 7:5 (2001), 353–377, arXiv: math/0101080[math.SC] | DOI | MR | Zbl

[40] G. L. Litvinov, V. P. Maslov and A. Ya. Rodionov, “A unifying approach to software and hardware design for scientific calculations and idempotent mathematics”, International Sophus Lie Centre, Moscow, 2000, arXiv: math/0101069[math.SC] | MR | Zbl

[41] M. Lorenz, Object oriented software: a practical guide, Prentice Hall Books, Englewood Cliffs, New Jersey, 1993 | MR

[42] G. Mikhalkin, “Tropical geometry and its applications”, Proceedings of the Madrid ICM, v. 2, 2006, 827–852, arXiv: math/0601041[math.AG] | MR | Zbl

[43] R. E. Moore, Methods and applications of interval analysis, SIAM Studies in Applied Mathematics, SIAM, Philadelphia, 1979 | MR | Zbl

[44] H. Myškova, “Interval systems of max-separable linear equations”, Linear Algebra and its Applications, 403 (2005), 263–272 | DOI | MR

[45] H. Myškova, “Control solvability of interval systems of max-separable linear equations”, Linear Algebra And Its Applications, 416:2–3 (2006), 215–223 | MR

[46] A. Neumaier, Interval methods for systems of equations, Cambridge University Press, Cambridge, 1990 | MR | Zbl

[47] I. Pohl, Object-Oriented Programming Using C++, 2nd ed., Addison-Wesley, Reading, 1997 | Zbl

[48] G. Rote, “A systolic array algorithm for the algebraic path problem”, Computing, 34 (1985), 191–219 | DOI | MR | Zbl

[49] S. Sergeev, “Max-algebraic attraction cones of nonnegative irreducible matrices”, Linear Algebra And Its Applications, 435:7 (2011), 1736–1757 | DOI | MR | Zbl

[50] S. Sergeev and H. Schneider, “CSR expansions of matrix powers in max algebra”, Transactions of Amer. Math. Soc., 364 (2012), 5969–5994 | DOI | MR | Zbl

[51] I. Simon, “Recognizable sets with multiplicities in the tropical semiring”, Lecture Notes in Computer Science, 324 (1988), 107–120 | DOI | MR | Zbl

[52] A. Stepanov and M. Lee, The Standard Template Library, Hewlett-Packard Company, Palo Alto, 1994

[53] O. Viro, “Dequantization of real algebraic geometry on logarithmic paper”, European Congress of Mathematics, European Congress of Mathematics (Barcelona, 2000, July 10–14), Progress in Mathematics, Birkhäuser, Basel, 135–146, arXiv: math/0005163 | MR | Zbl

[54] O. Viro, “From the sixteenth Hilbert problem to tropical geometry”, Japanese Journal of Mathematics, 3:2 (2008), 185–214 | DOI | MR | Zbl

[55] V. V. Voevodin, Mathematical Foundations of Parallel Computings, World Scientific Publ. Co., Singapore, 1992 | MR