Activities per year
Abstract
We consider linear vector inequalities defined in the framework of a linearly ordered tropical semifield (a semiring with idempotent addition and invertible multiplication). The problem is to solve twosided inequalities, which have an unknown vector included in both sides, each taking the form of a given matrix multiplied by this unknown vector. Observing that the set of solutions is closed under vector addition and scalar multiplication, we reduce the problem to finding a matrix whose columns generate the entire solution set.
We represent the solution as a family of subsets, each defined by a matrix that is obtained from the given matrices by using a matrix sparsification technique. The technique exploits sparsified matrices to derive a series of new inequalities, which admit a direct solution in the form of matrices that generate their solutions. We describe a
backtracking procedure that reduces the bruteforce search of sparsified matrices by skipping those, which cannot provide solutions, and thus offers an economical way to obtain all subsets in the family. The columns in the generating matrices for subsets are combined together to form a matrix, which is further reduced to have only columns that constitute a minimal generating system of the solution. We use the reduced matrix to represent a complete exact solution of the twosided inequality under consideration in a compact vector form.
We illustrate the results with numerical examples. Extension of the approach to solve twosided equations is also discussed.
We represent the solution as a family of subsets, each defined by a matrix that is obtained from the given matrices by using a matrix sparsification technique. The technique exploits sparsified matrices to derive a series of new inequalities, which admit a direct solution in the form of matrices that generate their solutions. We describe a
backtracking procedure that reduces the bruteforce search of sparsified matrices by skipping those, which cannot provide solutions, and thus offers an economical way to obtain all subsets in the family. The columns in the generating matrices for subsets are combined together to form a matrix, which is further reduced to have only columns that constitute a minimal generating system of the solution. We use the reduced matrix to represent a complete exact solution of the twosided inequality under consideration in a compact vector form.
We illustrate the results with numerical examples. Extension of the approach to solve twosided equations is also discussed.
Original language  English 

Pages  3838 
State  Published  2019 
Event  International Conference on Matrix Analysis and its Applications  Liblice, Czech Republic Duration: 8 Sep 2019 → 13 Sep 2019 Conference number: 8 https://mattriad.math.cas.cz/ 
Conference
Conference  International Conference on Matrix Analysis and its Applications 

Abbreviated title  MAT TRIAD 2019 
Country/Territory  Czech Republic 
City  Liblice 
Period  8/09/19 → 13/09/19 
Internet address 
Scopus subject areas
 Algebra and Number Theory
Keywords
 tropical semifield
 linear inequality
 matrix sparsification
 complete solution
 backtracking
Fingerprint
Dive into the research topics of 'Complete solution of tropical vector inequalities using matrix sparsification'. Together they form a unique fingerprint.
International Conference on Matrix Analysis and its Applications
Николай Кимович Кривулин (Participant)
8 Sep 2019 → 13 Sep 2019Activity: Attendance types › Participating in a conference, workshop, ...

Complete solution of tropical vector inequalities using matrix sparsification
Николай Кимович Кривулин (Speaker)
9 Sep 2019Activity: Talk types › Oral presentation