Аппроксимация множества решений систем нелинейных неравенств с использованием графических ускорителей

Существует множество задач, сводящихся к решению системы неравенств. Точное получение множества решений в подобных задачах не всегда возможно, из-за чего прибегают к различным методам аппроксимации данного множества. При повышении точности аппроксимации искомого множества увеличивается объем необходимых вычислений и, соответственно, время работы алгоритмов. В работе для увеличения быстродействия алгоритмов поиска аппроксимируемого множества применяются параллельные вычисления на графических ускорителях. Приводится описание и реализация последовательного метода аппроксимации системы неравенств и предлагается параллельный гибридный алгоритм, сочетающий перебор на равномерной сетке и идеи метода ветвей и границ. Этот алгоритм хорошо подходит для реализации на графических ускорителях и не приводит к избыточному перебору. Приведено сравнение эффективности работы последовательного и двух вариантов параллельного алгоритмов на примере прикладной задачи аппроксимации рабочей области робота. Рабочая область состоит из множества возможных положений инструмента и служит одной из ключевых характеристик робота.