حل دستگاه‌های چندجمله‌ای با استفاده از حساب ابرصفحه‌ای و برنامه‌ریزی خطی

Solving polynomial systems of equations is an important problem in many fields such as computer-aided design, manufacturing and robotics. In recent years, subdivision-based solvers, which typically make use of the properties of the Bézier/BB-spline representation, have proven successful in solving such systems of polynomial constraints. A major drawback in using subdivision solvers is their lack of scalability. When the given constraint is represented as a tensor product of its variables, it grows exponentially in size as a function of the number of variables. In this paper, we present a new method for solving systems of polynomial constraints, which scales nicely for systems with a large number of variables and relatively low degree. Such systems appear in many application domains. The method is based on the concept of bounding hyperplane arithmetic, which can be viewed as a generalization of interval arithmetic. We construct bounding hyperplanes, which are then passed to a linear programming solver in order to reduce the root domain. We have implemented our method and present experimental results. The method is compared to previous methods and its advantages are discussed.

Solving polynomial systems of equations is a crucial problem in many fields such as robotics [1], computer aided design and manufacturing [2] and [3], and many others [4]. This problem, namely finding the roots of a set of multivariate polynomial equations, is a difficult one and various approaches have been proposed for it. Symbolical approaches, such as Gröbner bases and similar elimination-based techniques [5], map the original system to a simpler one, which preserves the solution set. Polynomial continuation methods (also known as homotopy methods [4]) start at roots of a simpler system and trace a continuous transformation of the roots to the desired solution. These methods handle the system in a purely algebraic manner, find all complex and real roots, and give general information about the solution set. Such methods are typically not well-suited if only real roots are required.