Nonlinear systems solver in floating-point arithmetic using LP reduction

Christoph Fünfzig, Dominique Michelucci, Sebti Foufou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - SPM 2009
Subtitle of host publicationSIAM/ACM Joint Conference on Geometric and Physical Modeling
Pages123-134
Number of pages12
DOIs
StatePublished - 2009
EventSPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling - San Francisco, CA, United States
Duration: Oct 5 2009Oct 8 2009

Publication series

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

Other

OtherSPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling
CountryUnited States
CitySan Francisco, CA
Period10/5/0910/8/09

Keywords

  • Distance computation
  • Geometric constraint solving
  • Intersection computation
  • Interval arithmetic
  • Linear programming
  • Subdivision solver

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Computer Vision and Pattern Recognition
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Nonlinear systems solver in floating-point arithmetic using LP reduction'. Together they form a unique fingerprint.

Cite this