Approximation of the set of solutions of systems of nonlinear inequalities using graphic accelerators

Solutions of certain problems can be reduced to the solution of some systems of inequalities. But the computation of the set of exact solutions may not be feasible. Thus, various methods for approximation of the solution set have been developed. The more accurate approximation is required, the bigger number of calculations must be performed and, consequently, the runtime of the algorithms increases. Nowadays, it is common to speed up algorithms by paralleling computations on graphics accelerators. The paper describes the serial method for approximation of the solution of systems of inequalities and proposes the parallel hybrid algorithm that combines iterations on the uniform grid and the branch and bound method. This algorithm is suited for direct implementation on graphics accelerators and does not suffer from the excessive enumeration of possible solution candidates. The sequential algorithm and the two versions of the parallel algorithm are compared through one example: the problem of approximation of the working area of the robot which consists of the set of robot's tool positions and is the key robot's characteristic.