Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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 subsystems. 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(n²) 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.

REFERENCES

• 1: Beat Bruderlin , D. Roller, Geometric Constraint Solving and Applications, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 2: V. Chvatal. Linear Programming (Series of Books in the Mathematical Sciences). W. H. Freeman, September 1983.
• 3: I. S. Duff , A. M. Erisman , J. K. Reid, Direct methods for sparse matrices27100, Oxford University Press, Inc., New York, NY, 1986
• 4: Cassiano Berenguer Durand , Christoph M. Hoffmann, Symbolic and numerical techniques for constraint solving, Purdue University, West Lafayette, IN, 1998
• 5: Gershon Elber , Myung-Soo Kim, Geometric constraint solver using multivariate rational spline functions, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.1-10, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376958]
• 6: Gerald Farin, Curves and surfaces for CAGD: a practical guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 7: J. J. H. Forrest and J. A. Tomlin. Updating triangular factors of the basis to maintain sparsity in the product form simplex method. Mathematical Programming, (2):263--278, 1972.
• 8: T. Grandine. Geometry processing (chapter 24). In Handbook of CAGD (Farin, Hoschek, Kim eds.), pages 603--623. Elsevier, 2002.
• 9: C. Hoffmann and B. Yuan. There are 12 common tangents to four spheres. 2000. http://www.cs.purdue.edu/homes/cmh/distribution/SphereTangents.htm.
• 10: R. Kearfott. Rigorous Global Search: Continuous Problems. Kluwer, Dordrecht, Netherlands, 1996.
• 11: Hervé Lamure , Dominique Michelucci, Solving geometric constraints by homotopy, Proceedings of the third ACM symposium on Solid modeling and applications, p.263-269, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218071]
• 12: D. Michelucci. Linear Programming for Interval Newton Solvers - Extended abstract on a work in progress. In Automatic Deduction in Geometry, ADG 2008, Shanghai, 2008.
• 13: Dominique Michelucci , Sebti Foufou, Using Cayley-Menger determinants for geometric constraint solving, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
• 14: D. Michelucci and S. Foufou. Bernstein basis for interval analysis: application to geometric constraints systems solving. 8th Conference on Real Numbers and Computers (Bruguera and Daumas, eds.), pages 37--46, July 2008.
• 15: B. Mourrain and J.-P. Pavone. Subdivision methods for solving polynomial equations. Technical Report RR-5658, INRIA, August 2005.
• 16: Martin Reuter , Tarjei S. Mikkelsen , Evan C. Sherbrooke , Takashi Maekawa , Nicholas M. Patrikalakis, Solving nonlinear polynomial systems in the barycentric Bernstein basis, The Visual Computer: International Journal of Computer Graphics, v.24 n.3, p.187-200, January 2008 [doi>10.1007/s00371-007-0184-x]
• 17: Evan C. Sherbrooke , Nicholas M. Patrikalakis, Computation of the solutions of nonlinear polynomial systems, Computer Aided Geometric Design, v.10 n.5, p.379-405, Oct. 1993 [doi>10.1016/0167-8396(93)90019-Y]
• 18: D. Stewart. A Platform with Six Degrees of Freedom. UK Institution of Mechanical Engineers Proceedings, 180 Part 1(15):371--386, 1965--66.
• 19: Gokul Varadhan , Shankar Krishnan , TVN Sriram , Dinesh Manocha, Topology preserving surface extraction using adaptive subdivision, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057464]
• 20: C. Wampler, A. Morgan, and A. Sommese. Numerical continuation methods for solving polynomial systems arising in kinematics. ASME J. on Design, (112):59--68, 1990.
• 21: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 22: R. Wunderling. Paralleler und objektorientierter Simplex-Algorithmus. PhD thesis, TU Berlin, 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

Keywords:
CAD, distance computation, geometric constraint solving, geometric constraints, intersection computation, interval arithmetic, linear programming, subdivision solver