TY - GEN

T1 - Nonlinear systems solver in floating-point arithmetic using LP reduction

AU - Fünfzig, Christoph

AU - Michelucci, Dominique

AU - Foufou, Sebti

PY - 2009

Y1 - 2009

N2 - This paper presents a new solver for systems of nonlinear equations. Such systems occur in Geometric Constraint Solving, e.g., when dimensioning parts in CAD-CAM, or when computing the topology of sets defined by nonlinear inequalities. The paper does not consider the problem of decomposing the system and assembling solutions of sub-systems. It focuses on the numerical resolution of well-constrained systems. Instead of computing an exponential number of coefficients in the tensorial Bernstein basis, we resort to linear programming for computing range bounds of system equations or domain reductions of system variables. Linear programming is performed on a so called Bernstein polytope: though, it has an exponential number of vertices (each vertex corresponds to a Bernstein polynomial in the tensorial Bernstein basis), its number of hyperplanes is polynomial: O(n2) for a system in n unknowns and equations, and total degree at most two. An advantage of our solver is that it can be extended to non-algebraic equations. In this paper, we present the Bernstein and LP polytope construction, and how to cope with floating point inaccuracy so that a standard LP code can be used. The solver has been implemented with a primal-dual simplex LP code, and some implementation variants have been analyzed. Furthermore, we show geometric-constraint-solving applications, as well as numerical intersection and distance computation examples.

AB - This paper presents a new solver for systems of nonlinear equations. Such systems occur in Geometric Constraint Solving, e.g., when dimensioning parts in CAD-CAM, or when computing the topology of sets defined by nonlinear inequalities. The paper does not consider the problem of decomposing the system and assembling solutions of sub-systems. It focuses on the numerical resolution of well-constrained systems. Instead of computing an exponential number of coefficients in the tensorial Bernstein basis, we resort to linear programming for computing range bounds of system equations or domain reductions of system variables. Linear programming is performed on a so called Bernstein polytope: though, it has an exponential number of vertices (each vertex corresponds to a Bernstein polynomial in the tensorial Bernstein basis), its number of hyperplanes is polynomial: O(n2) for a system in n unknowns and equations, and total degree at most two. An advantage of our solver is that it can be extended to non-algebraic equations. In this paper, we present the Bernstein and LP polytope construction, and how to cope with floating point inaccuracy so that a standard LP code can be used. The solver has been implemented with a primal-dual simplex LP code, and some implementation variants have been analyzed. Furthermore, we show geometric-constraint-solving applications, as well as numerical intersection and distance computation examples.

KW - Distance computation

KW - Geometric constraint solving

KW - Intersection computation

KW - Interval arithmetic

KW - Linear programming

KW - Subdivision solver

UR - http://www.scopus.com/inward/record.url?scp=70350623069&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350623069&partnerID=8YFLogxK

U2 - 10.1145/1629255.1629271

DO - 10.1145/1629255.1629271

M3 - Conference contribution

AN - SCOPUS:70350623069

SN - 9781605587110

T3 - Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling

SP - 123

EP - 134

BT - Proceedings - SPM 2009

T2 - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling

Y2 - 5 October 2009 through 8 October 2009

ER -