+7 (3412) 91 60 92

## Archive of Issues

Russia Nizhni Novgorod
Year
2018
Volume
28
Issue
2
Pages
161-175
 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 Universitya, Intel Corporation, Nizhni Novgorodb 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 UDC 519.61, 519.852.2 MSC 90-08, 52B55, 92-08 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. 161-175. References Bastrakov S.I., Zolotykh N.Yu. Fast method for verifying Chernikov rules in Fourier-Motzkin elimination, Computational Mathematics and Mathematical Physics, 2015, vol. 55, no. 1, pp. 160-167. DOI: 10.1134/S0965542515010042 Veselov S.I., Parubochii I.E., Shevchenko V.N. A program for finding the skeleton of the cone of nonnegative solutions of a system of linear inequalities, Sistemnoe i prikladnoe programmnoe obespechenie. Chast' 2 (System and applied software. Part 2), Gor'kii: Gor'kii State University, 1984, pp. 83-92 (in Russian). Zolotykh N.Yu. New modification of the double description method for constructing the skeleton of a polyhedral cone, Computational Mathematics and Mathematical Physics, 2012, vol. 52, no. 1, pp. 146-156. DOI: 10.1134/S0965542512010162 Mnev N.E. On realizability of combinatorial types of convex polytopes over number fields, Zap. Nauchn. Sem. LOMI, 1983, vol. 123, pp. 203-207 (in Russian). Motzkin T.S., Raiffa H., Thompson G.L., Thrall R.M. The double description method, Contributions to theory of games, vol. 2, Princeton, New Jersey: Princeton University Press, 1953, pp. 51-73. Schrijver A. Theory of linear and integer programming, John Wiley & Sons, 1998. Ziegler G.M. Lectures on polytopes, Springer New York, 1995, 370 p. DOI: 10.1007/978-1-4613-8431-1 Chernikov S.N. Lineinye neravenstva (Linear inequalities), Moscow: Nauka, 1968, 488 p. Chernikova N.V. Algorithm for finding a general formula for the non-negative solutions of a system of linear inequalities, USSR Computational Mathematics and Mathematical Physics, 1965, vol. 5, issue 2, pp. 228-233. DOI: 10.1016/0041-5553(65)90045-5 Avis D. A revised implementation of the reverse search vertex enumeration algorithm, Polytopes - combinatorics and computation, Basel: Birkhäuser, 2000, pp. 177-198. DOI: 10.1007/978-3-0348-8438-9_9 Avis D., Bremner D., Seidel R. How good are convex hull algorithms? Computational Geometry, 1997, vol. 7, no. 5-6, pp. 265-301. DOI: 10.1016/S0925-7721(96)00023-5 Avis D., Fukuda K. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete and Computational Geometry, 1992, vol. 8, no. 3, pp. 295-313. DOI: 10.1007/BF02293050 Bagnara R., Hill P.M., Zaffanella E. The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems, Science of Computer Programming, 2008, vol. 72, no. 1-2, pp. 3-21. DOI: 10.1016/j.scico.2007.08.001 Barber C.B., Dobkin D.P., Huhdanpaa H. The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), 1996, vol. 22, no. 4, pp. 469-483. DOI: 10.1145/235815.235821 Bremner D., Fukuda K., Marzetta A. Primal-dual methods for vertex and facet enumeration, Discrete and Computational Geometry, 1998, vol. 20, no. 3, pp. 333-357. DOI: 10.1007/PL00009389 Demenkov M., Filimonov N. Polyhedral barrier regulator design using non-monotonic Lyapunov function, 2016 International Conference Stability and Oscillations of Nonlinear Control Systems (Pyatnitskiy's Conference), IEEE, 2016. DOI: 10.1109/STAB.2016.7541176 Fukuda K., Prodon A. Double description method revisited, Combinatorics and Computer Science. CCS 1995. Lecture Notes in Computer Science, vol. 1120, Springer, Berlin, Heidelberg, 1996, pp. 91-111. DOI: 10.1007/3-540-61576-8_77 Horst R., Pardalos P.M., Van Thoai N. Introduction to global optimization, Springer US, 2000. Loos R. Computing in algebraic extensions, Computer Algebra. Computing Supplementa, vol 4, Springer, Vienna, 1983, pp. 173-187. DOI: 10.1007/978-3-7091-7551-4_12 Perry J. Exploring the dynamic Buchberger algorithm, Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation - ISSAC'17, ACM, 2017, pp. 365-372. DOI: 10.1145/3087604.3087643 Rump S. On the sign of a real algebraic number, Proceedings of the third ACM symposium on Symbolic and algebraic computation, ACM, 1976, pp. 238-241. Schrijver A. Combinatorial optimization: polyhedra and efficiency, Springer-Verlag Berlin Heidelberg, 2003. Terzer M., Stelling J. Large-scale computation of elementary flux modes with bit pattern trees, Bioinformatics, 2008, vol. 24, no. 19, pp. 2229-2235. DOI: 10.1093/bioinformatics/btn401 Full text