TY - GEN
T1 - Solution isolation strategies for the Bernstein polytopes-based solver
AU - Djedaini, Mahfoud
AU - Barki, Hichem
AU - Foufou, Sebti
AU - Michelucci, Dominique
PY - 2013
Y1 - 2013
N2 - The Bernstein polytopes-based solver is a new method developed to solve systems of nonlinear equations, which often occur in Geometric Constraint Solving Problems. The principle of this solver is to linearize nonlinear monomials and then to solve the resulting linear programming problems, through linear programming. However, without any strategy for the isolation of the many solutions of multiple-solution systems, this solver is slow in practice. To overcome this problem, we propose in this work, a study of several strategies for solution isolation, through the split of solution boxes into several subboxes, according to three main steps answering the questions: when, where, and how to perform a split? We provide a detailed benchmark evaluating both time and space complexities for the proposed splitting strategies, applied to several Geometric Constraint Solving Problems widely encountered in geometric modeling. We also compare several linear programming solvers within our Bernstein solver.
AB - The Bernstein polytopes-based solver is a new method developed to solve systems of nonlinear equations, which often occur in Geometric Constraint Solving Problems. The principle of this solver is to linearize nonlinear monomials and then to solve the resulting linear programming problems, through linear programming. However, without any strategy for the isolation of the many solutions of multiple-solution systems, this solver is slow in practice. To overcome this problem, we propose in this work, a study of several strategies for solution isolation, through the split of solution boxes into several subboxes, according to three main steps answering the questions: when, where, and how to perform a split? We provide a detailed benchmark evaluating both time and space complexities for the proposed splitting strategies, applied to several Geometric Constraint Solving Problems widely encountered in geometric modeling. We also compare several linear programming solvers within our Bernstein solver.
UR - http://www.scopus.com/inward/record.url?scp=84893621553&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893621553&partnerID=8YFLogxK
U2 - 10.1109/IEEEGCC.2013.6705782
DO - 10.1109/IEEEGCC.2013.6705782
M3 - Conference contribution
AN - SCOPUS:84893621553
SN - 9781479907243
T3 - 2013 7th IEEE GCC Conference and Exhibition, GCC 2013
SP - 234
EP - 239
BT - 2013 7th IEEE GCC Conference and Exhibition, GCC 2013
T2 - 2013 7th IEEE GCC Conference and Exhibition, GCC 2013
Y2 - 17 November 2013 through 20 November 2013
ER -