Complete solution of tropical vector inequalities using matrix sparsification

Standard

Complete solution of tropical vector inequalities using matrix sparsification. / Krivulin, Nikolai .

In: Applications of Mathematics, Vol. 65, No. 6, 12.2020, p. 755-775.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{ea79aeee4d0c47fab931e267f784e78d,

title = "Complete solution of tropical vector inequalities using matrix sparsification",

abstract = "We examine the problem of finding all solutions of two-sided vector inequalities given in the tropical algebra setting, where the unknown vector multiplied by known matrices appears on both sides of the inequality. We offer a solution that uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from one of the given matrices by setting some of its entries to zero. All solutions are then combined to present the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, remark on its computational complexity and illustrate this technique with numerical examples.",

keywords = "tropical semifield, tropical two-sided inequality, matrix sparsification, complete solution, backtracking, 65F50, 15A39, 15A80, OPTIMIZATION PROBLEMS, SYSTEMS, ALGEBRAIC-SOLUTION",

author = "Nikolai Krivulin",

note = "Funding Information: This work was supported in part by the Russian Foundation for Basic Research under the grant 20-010-00145. Acknowledgments; International Conference on Matrix Analysis and its Applications, MAT TRIAD 2019 ; Conference date: 08-09-2019 Through 13-09-2019",

year = "2020",

month = dec,

doi = "10.21136/AM.2020.0376-19",

language = "English",

volume = "65",

pages = "755--775",

journal = "Applications of Mathematics",

issn = "0862-7940",

publisher = "Springer Nature",

number = "6",

url = "https://mattriad.math.cas.cz/",

}

RIS

TY - JOUR

T1 - Complete solution of tropical vector inequalities using matrix sparsification

AU - Krivulin, Nikolai

N1 - Conference code: 8

PY - 2020/12

Y1 - 2020/12

N2 - We examine the problem of finding all solutions of two-sided vector inequalities given in the tropical algebra setting, where the unknown vector multiplied by known matrices appears on both sides of the inequality. We offer a solution that uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from one of the given matrices by setting some of its entries to zero. All solutions are then combined to present the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, remark on its computational complexity and illustrate this technique with numerical examples.

AB - We examine the problem of finding all solutions of two-sided vector inequalities given in the tropical algebra setting, where the unknown vector multiplied by known matrices appears on both sides of the inequality. We offer a solution that uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from one of the given matrices by setting some of its entries to zero. All solutions are then combined to present the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, remark on its computational complexity and illustrate this technique with numerical examples.

KW - tropical semifield

KW - tropical two-sided inequality

KW - matrix sparsification

KW - complete solution

KW - backtracking

KW - 65F50

KW - 15A39

KW - 15A80

KW - OPTIMIZATION PROBLEMS

KW - SYSTEMS

KW - ALGEBRAIC-SOLUTION

UR - http://www.scopus.com/inward/record.url?scp=85092103009&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/f0573213-30e2-3c4c-ab06-fbc37e81e610/

U2 - 10.21136/AM.2020.0376-19

DO - 10.21136/AM.2020.0376-19

M3 - Article

VL - 65

SP - 755

EP - 775

JO - Applications of Mathematics

JF - Applications of Mathematics

SN - 0862-7940

IS - 6

T2 - International Conference on Matrix Analysis and its Applications

Y2 - 8 September 2019 through 13 September 2019

ER -

ID: 62225203