|
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(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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
V. Chvatal. Linear Programming (Series of Books in the Mathematical Sciences). W. H. Freeman, September 1983.
|
| |
3
|
|
| |
4
|
|
 |
5
|
|
| |
6
|
|
| |
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
|
|
| |
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
|
|
| |
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
|
|
| |
17
|
|
| |
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
|
|
| |
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
|
|
| |
22
|
R. Wunderling. Paralleler und objektorientierter Simplex-Algorithmus. PhD thesis, TU Berlin, 1996.
|
|