Double description method over the field of algebraic numbers

N. Yu. Zolotykh   ; V. K. Kubarev   ; S. S. Lyalin

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 28 (2018) no. 2, pp. 161-175

Résumé

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.

Détail

Keywords: system of linear inequalities, convex hull, cone, polyhedron, double description method, algebraic extensions.

Bibliographie

[1] Bastrakov S. I., Zolotykh N.Yu., “Fast method for verifying Chernikov rules in Fourier–Motzkin elimination”, Computational Mathematics and Mathematical Physics, 55:1 (2015), 160–167 | DOI | DOI | MR | Zbl

[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”, System and applied software, v. 2, Gor'kii State University, Gor'kii, 1984, 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, 52:1 (2012), 146–156 | DOI | MR | Zbl

[4] Mnev N. E., “On realizability of combinatorial types of convex polytopes over number fields”, Zap. Nauchn. Sem. LOMI, 123 (1983), 203–207 (in Russian) | Zbl

[5] Motzkin T. S., Raiffa H., Thompson G. L., Thrall R. M., “The double description method”, Contributions to theory of games, v. 2, Princeton University Press, Princeton, New Jersey, 1953, 51–73 | MR

[6] Schrijver A., Theory of linear and integer programming, John Wiley Sons, 1998 | MR

[7] Ziegler G. M., Lectures on polytopes, Springer, New York, 1995, 370 pp. | DOI | MR | Zbl

[8] Chernikov S. N., Linear inequalities, Nauka, M., 1968, 488 pp.

[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, 5:2 (1965), 228–233 | DOI | MR

[10] Avis D., “A revised implementation of the reverse search vertex enumeration algorithm”, Polytopes — combinatorics and computation, Birkhäuser, Basel, 2000, 177–198 | DOI | MR | Zbl

[11] Avis D., Bremner D., Seidel R., How good are convex hull algorithms?, Computational Geometry, 7:5–6 (1997), 265–301 | DOI | MR | Zbl

[12] Avis D., Fukuda K., “A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra”, Discrete and Computational Geometry, 8:3 (1992), 295–313 | DOI | MR | Zbl

[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, 72:1–2 (2008), 3–21 | DOI | MR

[14] Barber C. B., Dobkin D. P., Huhdanpaa H., “The quickhull algorithm for convex hulls”, ACM Transactions on Mathematical Software (TOMS), 22:4 (1996), 469–483 | DOI | MR | Zbl

[15] Bremner D., Fukuda K., Marzetta A., “Primal-dual methods for vertex and facet enumeration”, Discrete and Computational Geometry, 20:3 (1998), 333–357 | DOI | MR | Zbl

[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

[17] Fukuda K., Prodon A., “Double description method revisited”, Combinatorics and Computer Science, CCS 1995, Lecture Notes in Computer Science, 1120, Springer, Berlin–Heidelberg, 1996, 91–111 | DOI | MR

[18] Horst R., Pardalos P. M., Van Thoai N., Introduction to global optimization, Springer US, 2000 | MR

[19] Loos R., “Computing in algebraic extensions”, Computer Algebra, Computing Supplementa, 4, Springer, Vienna, 1983, 173–187 | DOI | MR

[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, 365–372 | DOI | MR

[21] Rump S., “On the sign of a real algebraic number”, Proceedings of the third ACM symposium on Symbolic and algebraic computation, ACM, 1976, 238–241 | DOI

[22] Schrijver A., Combinatorial optimization. Polyhedra and efficiency, Springer-Verlag, Berlin–Heidelberg, 2003 | MR | Zbl

[23] Terzer M., Stelling J., “Large-scale computation of elementary flux modes with bit pattern trees”, Bioinformatics, 24:19 (2008), 2229–2235 | DOI