Все выпуски

Рассматривается задача построения вершинного описания выпуклого полиэдра, заданного как множество решений некоторой системы линейных неравенств, коэффициенты которой являются алгебраическими числами. Обратная задача эквивалентна (двойственна) исходной. Предлагаются программные реализации нескольких модификаций хорошо известного метода двойного описания (метода Моцкина-Бургера), решающего поставленную задачу. Рассматривается два случая: 1) элементы системы неравенств - произвольные алгебраические числа, при этом каждое такое число задается минимальным многочленом и локализующим интервалом; 2) элементы системы неравенств принадлежат заданному конечному расширению ${\mathbb Q} (\alpha)$ поля ${\mathbb Q}$, при этом для $\alpha$ задаются минимальный многочлен и локализующий интервал, а все элементы исходной системы, конечные и промежуточные результаты представлены как многочлены от $\alpha$. Как и ожидалось, программная реализация для второго варианта значительно превосходит реализацию для первого варианта по производительности. Для большего ускорения во втором случае предлагается использовать булевы матрицы вместо матриц невязок. Результаты вычислительного эксперимента показывают, что программные реализации вполне пригодны для решения задач умеренных размеров.

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.