|
This article is cited in 3 scientific papers (total in 3 papers)
MATHEMATICS
Double description method over the field of algebraic numbers
N. Yu. Zolotykha, V. K. Kubarevb, S. S. Lyalinb a Department of Algebra, Geometry and Discrete Mathematics,
Nizhni Novgorod State University, pr. Gagarina, 23, Nizhni Novgorod, 603950, Russia
b Intel Corp.,
ul. Turgeneva, 30, Nizhni Novgorod, 603024, Russia
Abstract:
We consider the problem of constructing the dual representation of a convex polyhedron defined as a set of solutions to a system of linear inequalities with coefficients which are algebraic numbers. The inverse problem is equivalent (dual) to the initial problem. We propose program implementations of several variations of the well-known double description method (Motzkin–Burger method) solving this problem. The following two cases are considered: 1) the elements of the system of inequalities are arbitrary algebraic numbers, and each such number is represented by its minimal polynomial and a localizing interval; 2) the elements of the system belong to a given extension ${\mathbb Q} (\alpha)$ of ${\mathbb Q}$, and the minimal polynomial and the localizing interval are given only for $\alpha$, all elements of the system, intermediate and final results are represented as polynomials of $\alpha$. As expected, the program implementation for the second case significantly outperforms the implementation for the first one in terms of speed. In the second case, for greater acceleration, we suggest using a Boolean matrix instead of the discrepancy matrix. The results of a computational experiment show that the program is quite suitable for solving medium-scale problems.
Keywords:
system of linear inequalities, convex hull, cone, polyhedron, double description method, algebraic extensions.
Received: 13.04.2018
Citation:
N. Yu. Zolotykh, V. K. Kubarev, S. S. Lyalin, “Double description method over the field of algebraic numbers”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 28:2 (2018), 161–175
Linking options:
https://www.mathnet.ru/eng/vuu628 https://www.mathnet.ru/eng/vuu/v28/i2/p161
|
Statistics & downloads: |
Abstract page: | 415 | Full-text PDF : | 198 | References: | 42 |
|