Nonlinear systems solver in floating-point arithmetic using LP reduction

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: B. Bruderlin and D. Roller, editors. Geometric Constraint Solving and Applications. Springer, 1998.
• 2: V. Chvatal. Linear Programming (Series of Books in the Mathematical Sciences). W. H. Freeman, September 1983.
• 3: I. Duff, A. Erisman, and J. Reid. Direct Methods for Sparse Matrices. Clarendon Press, Oxford, 1986.
• 4: C. B. Durand. Symbolic and Numerical Techniques for Constraint Solving. PhD thesis, Purdue University, 1998.
• 5: G. Elber and M.-S. Kim. Geometric constraint solver using multivariate rational spline functions. In SMA'01: Proc. of the 6th ACM Symp. on Solid Modeling and Applications, pages 1--10, New York, NY, USA, 2001. ACM Press.
• 6: G. Farin. Curves and Surfaces for CAGD: A Practical Guide. Academic Press Professional, San Diego, California, 1988.
• 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: H. Lamure and D. Michelucci. Solving constraints by homotopy. In Proc. of the Symp. on Solid Modeling Foundations and CAD/CAM Applications, pages 263--269, May 1995.
• 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: D. Michelucci and S. Foufou. Using Cayley-Menger determinants for geometric constraint solving. In SM '04: Proceedings of the ninth ACM Symposium on Solid Modeling and Applications, pages 285--290, Aire-la-Ville, Switzerland, Switzerland, 2004. Eurographics Association.
• 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: M. Reuter, T. S. Mikkelsen, E. C. Sherbrooke, T. Maekawa, and N. M. Patrikalakis. Solving nonlinear polynomial systems in the barycentric Bernstein basis. The Visual Computer, 24(3):187--200, 2008.
• 17: E. C. Sherbrooke and N. M. Patrikalakis. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Des., 10(5):379--405, 1993.
• 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: G. Varadhan, S. Krishnan, T. Sriram, and D. Manocha. Topology preserving isosurface extraction for geometry processing. In Second Eurographics Symposium on Geometry Processing, pages 235--244, 2004.
• 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. Wilkinson. The algebraic eigenvalue problem. Oxford University Press, 1965.
• 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