Complete solution of tropical vector inequalities using matrix sparsification

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференции

Аннотация

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.
Язык оригиналаанглийский
Название основной публикацииMAT TRIAD 2019
Подзаголовок основной публикации International Conference on Matrix Analysis and its Applications: Book of Abstracts
РедакторыJan Bok, David Hartman, Milan Hladík, Miroslav Rozložník
Место публикацииPrague
ИздательCharles University in Prague
Страницы38-38
СостояниеОпубликовано - 2019
СобытиеInternational Conference on Matrix Analysis and its Applications - Liblice, Чехия
Продолжительность: 8 сен 201913 сен 2019
Номер конференции: 8
https://mattriad.math.cas.cz/

Конференция

КонференцияInternational Conference on Matrix Analysis and its Applications
Сокращенный заголовокMAT TRIAD 2019
СтранаЧехия
ГородLiblice
Период8/09/1913/09/19
Адрес в сети Интернет

    Fingerprint

Предметные области Scopus

  • Алгебра и теория чисел

Цитировать

Krivulin, N. (2019). Complete solution of tropical vector inequalities using matrix sparsification. В J. Bok, D. Hartman, M. Hladík, & M. Rozložník (Ред.), MAT TRIAD 2019: International Conference on Matrix Analysis and its Applications: Book of Abstracts (стр. 38-38). Prague: Charles University in Prague.