Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Using matrix sparsification to solve tropical linear vector equations. / Кривулин, Николай Кимович.
Relational and Algebraic Methods in Computer Science: 21st International Conference, RAMiCS 2024, Prague, Czech Republic, August 19-22, 2024, Proceedings. ed. / Uli Fahrenberg; Wesley Fussner; Roland Glück. Cham : Springer Nature, 2024. p. 193-206 (Lecture Notes in Computer Science; Vol. 14787).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Using matrix sparsification to solve tropical linear vector equations
AU - Кривулин, Николай Кимович
N1 - Conference code: 21
PY - 2024/7/30
Y1 - 2024/7/30
N2 - A linear vector equation in two unknown vectors is examined in the framework of tropical algebra dealing with the theory and applications of semirings and semifields with idempotent addition. We consider a two-sided equation where each side is a tropical product of a given matrix by one of the unknown vectors. We use a matrix sparsification technique to reduce the equation to a set of vector inequalities that involve row-monomial matrices obtained from the given matrices. An existence condition of solutions for the inequalities is established, and a direct representation of the solutions is derived in a compact vector form. To illustrate the proposed approach and to compare the obtained result with that of an existing solution procedure, we apply our solution technique to handle two-sided equations known in the literature. Finally, a computational scheme based on the approach to derive all solutions of the two-sided equation is discussed.
AB - A linear vector equation in two unknown vectors is examined in the framework of tropical algebra dealing with the theory and applications of semirings and semifields with idempotent addition. We consider a two-sided equation where each side is a tropical product of a given matrix by one of the unknown vectors. We use a matrix sparsification technique to reduce the equation to a set of vector inequalities that involve row-monomial matrices obtained from the given matrices. An existence condition of solutions for the inequalities is established, and a direct representation of the solutions is derived in a compact vector form. To illustrate the proposed approach and to compare the obtained result with that of an existing solution procedure, we apply our solution technique to handle two-sided equations known in the literature. Finally, a computational scheme based on the approach to derive all solutions of the two-sided equation is discussed.
KW - idempotent semifield
KW - two-sided linear vector equation
KW - sparsified matrix
KW - row-monomial matrix
KW - complete solution
KW - Idempotent semifield
KW - Two-sided linear vector equation
KW - Sparsified matrix
KW - Complete solution
KW - Row-monomial matrix
UR - https://www.mendeley.com/catalogue/d63a0b28-6755-3553-b37b-496a622a9baa/
U2 - 10.1007/978-3-031-68279-7_12
DO - 10.1007/978-3-031-68279-7_12
M3 - Conference contribution
SN - 978-3-031-68278-0
T3 - Lecture Notes in Computer Science
SP - 193
EP - 206
BT - Relational and Algebraic Methods in Computer Science
A2 - Fahrenberg, Uli
A2 - Fussner, Wesley
A2 - Glück, Roland
PB - Springer Nature
CY - Cham
T2 - Relational and Algebraic Methods in Computer Science
Y2 - 19 August 2024 through 22 August 2024
ER -
ID: 124151391