Complete solution of tropical vector inequalities using matrix sparsification

Research output

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 two-sided 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 brute-force 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 two-sided inequality under consideration in a compact vector form.
We illustrate the results with numerical examples. Extension of the approach to solve two-sided equations is also discussed.
Original languageEnglish
Pages38-38
Publication statusPublished - 2019
EventInternational Conference on Matrix Analysis and its Applications - Liblice
Duration: 8 Sep 201913 Sep 2019
Conference number: 8
https://mattriad.math.cas.cz/

Conference

ConferenceInternational Conference on Matrix Analysis and its Applications
Abbreviated titleMAT TRIAD 2019
CountryCzech Republic
CityLiblice
Period8/09/1913/09/19
Internet address

Fingerprint

Matrix Inequality
Subset
Vector addition
Semifield
Unknown
Scalar multiplication
Entire Solution
Semiring
Solution Set
Idempotent
Invertible
Multiplication
Exact Solution
Linearly
Closed
Numerical Examples
Series

Scopus subject areas

  • Algebra and Number Theory

Cite this

Кривулин, Н. К. (2019). Complete solution of tropical vector inequalities using matrix sparsification. 38-38. Abstract from International Conference on Matrix Analysis and its Applications, Liblice, .
Кривулин, Николай Кимович. / Complete solution of tropical vector inequalities using matrix sparsification. Abstract from International Conference on Matrix Analysis and its Applications, Liblice, .
@conference{66c65e10b6184195b7f6c6dd7602f00b,
title = "Complete solution of tropical vector inequalities using matrix sparsification",
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 two-sided 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 abacktracking procedure that reduces the brute-force 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 two-sided inequality under consideration in a compact vector form.We illustrate the results with numerical examples. Extension of the approach to solve two-sided equations is also discussed.",
keywords = "tropical semifield, linear inequality, matrix sparsification, complete solution, backtracking",
author = "Кривулин, {Николай Кимович}",
note = "Krivulin N. Complete solution of tropical vector inequalities using matrix sparsification // MAT TRIAD 2019: Book of Abstracts / Jan Bok, David Hartman, Milan Hlad{\'i}k, Miroslav Rozložn{\'i}k eds. MATFYZPRESS: Prague, 2019. P. 38. (IUUK-ITI Series, vol. 2019-676); International Conference on Matrix Analysis and its Applications, MAT TRIAD 2019 ; Conference date: 08-09-2019 Through 13-09-2019",
year = "2019",
language = "English",
pages = "38--38",
url = "https://mattriad.math.cas.cz/",

}

Complete solution of tropical vector inequalities using matrix sparsification. / Кривулин, Николай Кимович.

2019. 38-38 Abstract from International Conference on Matrix Analysis and its Applications, Liblice, .

Research output

TY - CONF

T1 - Complete solution of tropical vector inequalities using matrix sparsification

AU - Кривулин, Николай Кимович

N1 - Krivulin N. Complete solution of tropical vector inequalities using matrix sparsification // MAT TRIAD 2019: Book of Abstracts / Jan Bok, David Hartman, Milan Hladík, Miroslav Rozložník eds. MATFYZPRESS: Prague, 2019. P. 38. (IUUK-ITI Series, vol. 2019-676)

PY - 2019

Y1 - 2019

N2 - 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 two-sided 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 abacktracking procedure that reduces the brute-force 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 two-sided inequality under consideration in a compact vector form.We illustrate the results with numerical examples. Extension of the approach to solve two-sided equations is also discussed.

AB - 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 two-sided 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 abacktracking procedure that reduces the brute-force 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 two-sided inequality under consideration in a compact vector form.We illustrate the results with numerical examples. Extension of the approach to solve two-sided equations is also discussed.

KW - tropical semifield

KW - linear inequality

KW - matrix sparsification

KW - complete solution

KW - backtracking

UR - https://iti.mff.cuni.cz/series/2019/676.pdf

M3 - Abstract

SP - 38

EP - 38

ER -

Кривулин НК. Complete solution of tropical vector inequalities using matrix sparsification. 2019. Abstract from International Conference on Matrix Analysis and its Applications, Liblice, .