Archive of Issues
Russia Nizhni Novgorod
Section  Mathematics 
Title  Double description method over the field of algebraic numbers 
Author(s)  Zolotykh N.Yu.^{a}, Kubarev V.K.^{b}, Lyalin S.S.^{b} 
Affiliations  Nizhni Novgorod State University^{a}, Intel Corporation, Nizhni Novgorod^{b} 
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 wellknown double description method (MotzkinBurger 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 mediumscale problems. 
Keywords  system of linear inequalities, convex hull, cone, polyhedron, double description method, algebraic extensions 
UDC  519.61, 519.852.2 
MSC  9008, 52B55, 9208 
DOI  10.20537/vm180203 
Received  13 April 2018 
Language  Russian 
Citation  Zolotykh N.Yu., Kubarev V.K., Lyalin S.S. Double description method over the field of algebraic numbers, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2018, vol. 28, issue 2, pp. 161175. 
References 

Full text 