Title
Solving multivariate polynomial systems using hyperplane arithmetic and linear programming
Abstract
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 Bezier/B-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.
Year
DOI
Venue
2014
10.1016/j.cad.2013.08.022
Computer-Aided Design
Keywords
Field
DocType
hyperplane arithmetic,linear programming,multivariate polynomial system,present experimental result,large number,previous method,subdivision-based solvers,interval arithmetic,new method,subdivision solvers,polynomial system,polynomial constraint
Tensor product,Mathematical optimization,Polynomial,System of linear equations,Arithmetic,Subdivision,Linear programming,Hyperplane,Solver,Interval arithmetic,Mathematics
Journal
Volume
ISSN
Citations 
46,
0010-4485
2
PageRank 
References 
Authors
0.44
15
1
Name
Order
Citations
PageRank
Iddo Hanniel119712.98