Next: 4.6 Robustness issues Up: 4. Nonlinear Polynomial Solvers Previous: 4.4 Projected Polyhedron algorithm Contents Index

4.5 Auxiliary variable method for nonlinear systems with square roots of polynomials

In this section we will focus on how to compute the real roots of systems of irrational equations involving nonlinear polynomials and square roots of nonlinear polynomials within a finite box. Square roots of nonlinear polynomials in the context of shape interrogation arise from normalization of the normal vector and analytical expressions of the principal curvatures of the surface (see (2.24), (3.3), (3.49), (3.50)). They often appear in the form of

$\displaystyle f({\bf x}) + g({\bf x})\sqrt{h({\bf x})}=0\;,$

(4.24)

where ${\bf x}$ is the unknown vector of variables, and $f({\bf x})$ , $g({\bf x})$ and $h({\bf x})$ are multivariate polynomials over the box ${\bf x} \in [0,1]^{l}$ .

These polynomials can be expressed in the Bernstein basis as

$\displaystyle f({\bf x}) = \sum_{I}^{M_f} f_{I}B_{I,M_f}({\bf x})\;,$			(4.25)
$\displaystyle g({\bf x}) = \sum_{I}^{M_g} g_{I}B_{I,M_g}({\bf x})\;,$			(4.26)
$\displaystyle h({\bf x}) = \sum_{I}^{M_h} h_{I}B_{I,M_h}({\bf x})\;.$			(4.27)

Since the square root is involved we cannot use the convex hull property of the Bernstein polynomial directly.

One might consider a squaring method to square out the square root, so that the equation becomes

$\displaystyle f^2({\bf x}) - g^2({\bf x})h({\bf x}) = 0\;.$

(4.28)

This leads to a higher degree equation, also providing extraneous roots which are not typically necessary. The disadvantages of this squaring method are discussed in [255]. The alternative is the auxiliary variable method which will transform the problem into a problem of higher dimensionality. The higher dimensional formulation has been studied by Hoffmann [169] for surface interrogation problems. First we will introduce the auxiliary variable $\tau$ such that

$\displaystyle \tau^2= h({\bf x})\;.$

(4.29)

Bounds $a \leq \tau \leq b$ can be obtained by

$\displaystyle a = \sqrt{min_Ih_I}\;,$			(4.30)
$\displaystyle b = \sqrt{max_Ih_I}\;.$			(4.31)

When is negative, we just set =0. For convenience, we also scale $\tau$ such that $\sigma \equiv \frac{\tau - a}{b - a}$ , so that $0 \leq \sigma \leq 1$ . Consequently, the system of irrational equations involving nonlinear polynomials and square roots of nonlinear polynomials (4.24), which consists of one equation with unknowns, has been transformed to a system of nonlinear polynomial equations which consists of two equations with unknowns as follows:

$\displaystyle f({\bf x}) + g({\bf x})\left[a + \sigma(b - a)\right] = 0\;,$			(4.32)
$\displaystyle \left[a + \sigma(b - a)\right]^2 - h({\bf x}) = 0\;,$			(4.33)

where $0 \leq \sigma \leq 1$ and ${\bf x} \in [0,1]^l$ . Note that even though we transformed the problem into a problem of higher dimensionality, the degree of the new variable $\sigma$ is only two. System (4.32) (4.33) of two polynomial equations can be solved using the PP algorithm. A similar procedure can be used when (4.24) involves not only one but scalar equations of the form (4.24). If the $h({\bf x})$ term is different in each of the equations, then system (4.32) (4.33) will be transformed into nonlinear polynomial equations in unknowns.

Next: 4.6 Robustness issues Up: 4. Nonlinear Polynomial Solvers Previous: 4.4 Projected Polyhedron algorithm Contents Index

December 2009