phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2018 - 2 issue » pp. 161-175

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
  1. 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
  2. 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).
  3. 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
  4. 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).
  5. 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.
  6. Schrijver A. Theory of linear and integer programming, John Wiley & Sons, 1998.
  7. Ziegler G.M. Lectures on polytopes, Springer New York, 1995, 370 p. DOI: 10.1007/978-1-4613-8431-1
  8. Chernikov S.N. Lineinye neravenstva (Linear inequalities), Moscow: Nauka, 1968, 488 p.
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. Horst R., Pardalos P.M., Van Thoai N. Introduction to global optimization, Springer US, 2000.
  19. 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
  20. 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
  21. 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.
  22. Schrijver A. Combinatorial optimization: polyhedra and efficiency, Springer-Verlag Berlin Heidelberg, 2003.
  23. 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
/doc/issues-2018/18-02-03.pdf
<< Previous article
Next article >>