×

Solving linear systems over idempotent semifields through \(LU\)-factorization. (English) Zbl 1490.65045

Summary: In this paper, we introduce and analyze a new LU-factorization technique for square matrices over idempotent semifields. In particular, more emphasis is put on “max-plus” algebra here but the work is extended to other idempotent semifields as well. We first determine the conditions under which a square matrix has LU factors. Next, using this technique, we propose a method for solving square linear systems of equations whose system matrices are LU-factorizable. We also give conditions for an LU-factorizable system to have solutions. This work is an extension of similar techniques over fields. Maple procedures for this LU-factorization are also included.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
15A06 Linear equations (linear algebraic aspects)
12K10 Semifields

Software:

Maple
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baccelli, F.; Cohen, G.; Olsder, GJ; Quadrat, JP, Synchronization and Linearity: An Algebra for Discrete Event Systems (1992), New York: Wiley, New York · Zbl 0824.93003
[2] Butkoviç, P., Max-algebra: the linear algebra of combinatorics?, Linear Algebra Appl., 367, 313-335 (2003) · Zbl 1022.15017 · doi:10.1016/S0024-3795(02)00655-9
[3] Butkoviç, P., Max-Linear Systems: Theory and Algorithms. Springer Monographs in Mathematics (2010), London: Springer, London · Zbl 1202.15032 · doi:10.1007/978-1-84996-299-5
[4] Cuninghame-Green, RA, Minimax Algebra (1979), Berlin: Springer, Berlin · Zbl 0399.90052 · doi:10.1007/978-3-642-48708-8
[5] Golan, JS, Semirings and Their Applications (1999), Dordrecht: Kluwer Academic, Dordrecht · Zbl 0947.16034 · doi:10.1007/978-94-015-9333-5
[6] Hebish, U.; Weinert, HJ, Semirings: Algebraic Theory and Applications in Computer Science (1998), Singapore: World Scientific, Singapore · Zbl 0934.16046 · doi:10.1142/3903
[7] Hook, J.; Tisseur, F., Incomplete LU preconditioner based on max-plus approximation of LU factorization, SIAM J. Matrix Anal. Appl., 38, 4, 1160-1189 (2017) · Zbl 1386.65102 · doi:10.1137/16M1094579
[8] Izakian, Z.; Niv, A.; Rowen, L., Supertropical SL n, Linear Multilinear Algebra, 66, 7, 1461-1483 (2018) · Zbl 1386.15008 · doi:10.1080/03081087.2017.1363148
[9] Krivulin, N., Solution of generalized linear vector equations in idempotent algebra, Vestnik St. Petersburg Univ. Math., 39, 1, 16-26 (2006)
[10] Krivulin, N., Solution of linear equations and inequalities in idempotent vector spaces, Int. J. Appl. Math. Inform., 7, 1, 14-23 (2013)
[11] Kolokoltsov, V.; Maslov, VP, Idempotent Analysis and Its Applications (1997), Dordrecht: Kluwer Academic, Dordrecht · Zbl 0941.93001 · doi:10.1007/978-94-015-8901-7
[12] Kronewitter, F.D.: Noncommutative computer algebra in linear algebra and control theory. Ph.D. Thesis, University of California, San Diego (2000)
[13] Rutherford, DE, Inverses of Boolean matrices, Glasgow Math. J., 6, 1, 49-53 (1963) · Zbl 0114.01701 · doi:10.1017/S2040618500034705
[14] Tan, YJ, Determinants of matrices over semirings, Linear Multilinear Algebra, 62, 4, 498-517 (2014) · Zbl 1298.15014 · doi:10.1080/03081087.2013.784285
[15] Tan, YJ, On strongly invertible matrices over semirings, Linear Multilinear Algebra, 66, 12, 2501-2511 (2018) · Zbl 1400.15011 · doi:10.1080/03081087.2017.1404553
[16] Vandiver, HS, Note on a simple type of algebra in which the cancellation law of addition does not hold, Bull. Am. Math. Soc., 40, 12, 914-920 (1934) · JFM 60.0901.04 · doi:10.1090/S0002-9904-1934-06003-8
[17] Zumbrägel, J.: Public-key cryptography based on simple semirings. Doctoral dissertation, Verlag nicht ermittelbar (2008)
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.