Polynomial System Solving

All Products Maple MapleSim

Home : Support : Online Help : System : Information : Updates : Maple 16 : Polynomial System Solving

Polynomial System Solving in Maple 16

Computing and manipulating the real solutions of a polynomial system is a requirement for many application areas, such as biological modeling, robotics, program verification, control design, to name just a few. For example, an important problem in computational biology is to study the stability of the equilibria (or steady states) of biological systems. This question can often be reduced to solving a parametric system of polynomial equations and inequalities.

The RegularChains package in Maple 16 provides a collection of tools for studying systems of polynomial equations, inequations and inequalities. It is particularly useful for solving and working with the real solutions of polynomial systems, such as the steady-state problem, amongst many others. The new RegularChains features in Maple 16 include:

•	set theoretical operations for semi-algebraic sets (Complement, Difference , Intersection, IsContained, IsEmpty, Projection),

•	new solvers for popular types of systems (LinearSolve, RealComprehensiveTriangularize),

•	a new command, SuggestVariableOrder, for heuristically selecting a good variable order for computing a triangular decomposition of a polynomial system

•	significant enhancements and performance improvements for the Triangularize, RealTriangularize, and CylindricalAlgebraicDecompose commands

The two following applications highlighting these new features.

$restart$

$with (RegularChains) &colon;$

$with (SemiAlgebraicSetTools) &colon;$

$with (ParametricSystemTools) &colon;$

Application 1: Stability analysis of a parametric dynamical system

Application 2: Verifying mathematical identities by branch cut analysis

Application 1: Stability analysis of a parametric dynamical system

Consider a biological system described by the nonlinear multiple switch model

$S ≔ Vector ([\overset{&period;}{x} (t) = - x (t) + \frac{s}{1 + y {(t)}^{2}}, \overset{&period;}{y} (t) = - y (t) + \frac{s}{1 + x {(t)}^{2}}])$

where the unknowns $x, y$ represent two protein concentrations and $s$ represents the strength of unrepressed protein expression. This latter quantity is regarded as a time-constant parameter.

The equilibria of $S$ correspond to $\overset{&period;}{x} = \overset{&period;}{y} = 0$ , or equivalently, $F = 0$ , where

$f ≔ \binom{rhs ~ (S)}{} | \binom{}{[x (t) = x, y (t) = y]}$

The following two Hurwitz determinants determine the stability of the hyperbolic equilibria of $S$ :

$d_{1} ≔ - (\frac{\partial}{\partial x} f_{1} + \frac{\partial}{\partial y} f_{2})$

$2$

(1.1)

$d_{2} ≔ (\frac{\partial}{\partial x} f_{1}) \cdot (\frac{\partial}{\partial y} f_{2}) - (\frac{\partial}{\partial y} f_{1}) \cdot (\frac{\partial}{\partial x} f_{2})$

$1 - \frac{4 s^{2} y x}{{(1 + y^{2})}^{2} {(1 + x^{2})}^{2}}$

(1.2)

The semi-algebraic system below encodes the asymptotically stable hyperbolic equilibria:

$P ≔ [numer (f_{1}) = 0, numer (f_{2}) = 0, x > 0, y > 0, s > 0, numer (d_{2}) > 0] &colon; print ~ (P) &colon;$

$0 < 1 + 2 x^{2} + x^{4} + 2 y^{2} + 4 y^{2} x^{2} + 2 y^{2} x^{4} + y^{4} + 2 y^{4} x^{2} + y^{4} x^{4} - 4 s^{2} y x$

(1.3)

We solve this problem by first computing a real comprehensive triangular decomposition of $P$ with respect to the parameter $s$ , using the new command RealComprehensiveTriangularize:

$R ≔ PolynomialRing ([y, x, s]) &colon;$

$C ≔ RealComprehensiveTriangularize (P, 1, R)$

$[[[1, squarefree_semi_algebraic_system], [2, squarefree_semi_algebraic_system]], [[semi_algebraic_set, []], [semi_algebraic_set, [1]], [semi_algebraic_set, [2]]]]$

(1.4)

This is a decomposition of the original system into several simpler triangular systems and some additional conditions on the parameter $s$ :

$Display (C_{1}, R)$

(1.5)

$Display (C_{2}, R)$

$[[[s < - 2, s = - 2, And (- 2 < s, s < 0), s = 0, s = 2], []], [[And (0 < s, s < 2)], [1]], [[2 < s], [2]]]$

(1.6)

Suppose we are interested in those values of $s$ for which the biological system is bistable (that is, there are at least two stable equilibria). This means that we are looking for values of $s$ such that $P$ has at least 2 positive real solutions. We use the RealComprehensiveTriangularize command again and apply it to our previous result $C$ :

$result ≔ RealComprehensiveTriangularize (C, R, 2)$

$[[[1, squarefree_semi_algebraic_system]], [[semi_algebraic_set, [1]]]]$

(1.7)

The condition on $s$ that we are looking for is given by the second entry:

$Display ({result}_{2}, R)$

$[[[2 < s], [1]]]$

(1.8)

The locations of the stable equilibria are described by the following triangular system from the first entry:

$Display ({result}_{1}, R)$

(1.9)

We now illustrate the result by discussing the special case $s = 3$ . From the equations above, there are $2$ stable equilibria given by:

$equilibria ≔ [allvalues (solve (\binom{[x y - 1 = 0, x^{2} - 3 x + 1 = 0]}{} | \binom{}{s = 3}))]$

$[\{x = \frac{3}{2} - \frac{1}{2} \sqrt{5}, y = \frac{3}{2} + \frac{1}{2} \sqrt{5}\}, \{x = \frac{3}{2} + \frac{1}{2} \sqrt{5}, y = \frac{3}{2} - \frac{1}{2} \sqrt{5}\}]$

(1.10)

$evalf (equilibria)$

$[\{x = 0.381966012, y = 2.618033988\}, \{x = 2.618033988, y = 0.381966012\}]$

(1.11)

We verify that the last inequality is satisfied:

$condition ≔ \binom{8 x s^{3} - 6 x s^{5} - 4 s^{2} + 5 s^{4} - s^{6} + x s^{7} > 0}{} | \binom{}{s = 3}$

$0 < 945 x - 360$

(1.12)

$evalf (\binom{condition}{} | \binom{}{{equilibria}_{1}})$

$0. < 0.957881$

(1.13)

$evalf (\binom{condition}{} | \binom{}{{equilibria}_{2}})$

$0. < 2114.042119$

(1.14)

Below, we graphically display trajectories of the dynamical system in the special case. The first plot is a 2D animation, and the second one is a 3D static plot with time as the z-axis. We can see the two stable equilibria well in both plots, but there is also a third, unstable, equilibrium that can be seen best in the 3D plot.

$special ≔ \binom{convert (S, list)}{} | \binom{}{s = 3}$

$[\frac{&DifferentialD;}{&DifferentialD; t} x (t) = - x (t) + \frac{3}{1 + {y (t)}^{2}}, \frac{&DifferentialD;}{&DifferentialD; t} y (t) = - y (t) + \frac{3}{1 + {x (t)}^{2}}]$

(1.15)

$with (DEtools) &colon;$

${IC}_{2} ≔ [[x (0) = 0.5, y (0) = 0], seq ([x (0) = i, y (0) = 0], i = 1 .. 5), [x (0) = 0, y (0) = 0.5], seq ([x (0) = 0, y (0) = i], i = 1 .. 5), [x (0) = 4.5, y (0) = 5], seq ([x (0) = i, y (0) = 5], i = 1 .. 4), [x (0) = 5, y (0) = 4.5], seq ([x (0) = 5, y (0) = i], i = 1 .. 4), seq ([x (0) = i, y (0) = i], i = 0 .. 5)] &colon;$

$DEplot (special, [x (t), y (t)], t = 0 .. 20, x = 0 .. 5, y = 0 .. 5, {IC}_{2}, arrows = none, animate = true, numframes = 40, linecolor = \sqrt{t})$

${IC}_{3} ≔ [seq ([x (0) = 0.1, y (0) = 0.04 j], j = 0 .. 25), seq ([x (0) = 0.1, y (0) = 1 + 0.04 j], j = 0 .. 25), seq ([x (0) = 0.1, y (0) = 4 + 0.1 j], j = 0 .. 10), seq ([x (0) = 0.1, y (0) = 3 + 0.05 j], j = 0 .. 20), seq ([x (0) = 0.1, y (0) = 2 + 0.05 j], j = 0 .. 20), seq ([y (0) = 0.1, x (0) = 0.04 j], j = 0 .. 25), seq ([y (0) = 0.1, x (0) = 1 + 0.04 j], j = 0 .. 25), seq ([y (0) = 0.1, x (0) = 4 + 0.1 j], j = 0 .. 10), seq ([y (0) = 0.1, x (0) = 3 + 0.05 j], j = 0 .. 20), seq ([y (0) = 0.1, x (0) = 2 + 0.05 j], j = 0 .. 20), seq ([x (0) = 0.2 j, y (0) = 0.2 j], j = 0 .. 25)] &colon;$

$DEplot3d (special, \{x (t), y (t)\}, t = 0 .. 50, x = 0 .. 5, y = 0 .. 5, {IC}_{3}, scene = [x (t), y (t), t], thickness = 1, linecolor = \sqrt{t}, axes = frame)$

Application 2: Verifying mathematical identities by branch cut analysis

Let $z$ be a complex variable. Which of the following two identities holds for all $z \in &complexes;$ ?

$\sqrt{z^{2} - 1} = \sqrt{z - 1} \cdot \sqrt{z + 1}$

$\sqrt{z^{2} - 1} = \sqrt{z - 1} \sqrt{z + 1}$

(2.1)

$\sqrt{1 - z^{2}} = \sqrt{1 - z} \cdot \sqrt{1 + z}$

$\sqrt{1 - z^{2}} = \sqrt{1 - z} \sqrt{z + 1}$

(2.2)

In Maple, the branch cut for the square root function $\sqrt{z}$ is the negative real axis $z < 0$ . If we rewrite $z = x + ⅈ y$ in Cartesian coordinates, we can express that condition by the simple semi-algebraic system $&Im; (z) = y = 0, &real; (z) = x < 0$ . For example (2.1) above, the branch cuts of the three square root functions are, from left to right:

$assume (x, real)$

$assume (y, real)$

$[&Im; ({(x + ⅈ y)}^{2} - 1) = 0, &real; ({(x + ⅈ y)}^{2} - 1) < 0]$

$[2 x~ y~ = 0, {x~}^{2} - {y~}^{2} < 1]$

(2.3)

$[&Im; (x + ⅈ y - 1) = 0, &real; (x + ⅈ y - 1) < 0]$

$[y~ = 0, x~ < 1]$

(2.4)

$[&Im; (x + ⅈ y + 1) = 0, &real; (x + ⅈ y + 1) < 0]$

$[y~ = 0, x~ < - 1]$

(2.5)

The following plot depicts these three branch cuts.

$with (plottools) &colon;$

$with (plots) &colon;$

$branchcuts ≔ display (line ([0, - 10], [0, 10], color = red), line ([- 1, - 0.12], [1, - 0.12], color = red), line ([- 10, 0.05], [1, 0.05], color = green), line ([- 10, - 0.12], [- 1, - 0.12], color = blue), thickness = 4, view = [- 5 .. 5, - 5 .. 5]) &colon;$

$branchcuts$

By continuity arguments, it is now sufficient to check the proposed identity (2.1) at finitely many points covering all possible combinations of branch cuts. Such a set of points can be computed using the command CylindricalAlgebraicDecompose:

$b_{1} ≔ [,,]$

$[[2 x~ y~ = 0, {x~}^{2} - {y~}^{2} < 1], [y~ = 0, x~ < 1], [y~ = 0, x~ < - 1]]$

(2.6)

$R ≔ PolynomialRing ([y, x]) &colon;$

$S ≔ CylindricalAlgebraicDecompose (b_{1}, R, output = rootof)$

$[[x~ < - 1, y~ = 0], [x~ = - 1, y~ = 0], [- 1 < x~, x~ < 0, y~ = 0], [x~ = 0, y~ < 0], [x~ = 0, y~ = 0], [x~ = 0, 0 < y~], [0 < x~, x~ < 1, y~ = 0]]$

(2.7)

The union of all branch cuts was decomposed into the 7 disjoint intervals above. We pick one sample point for each interval:

$S ≔ [[x = - 2, y = 0], S_{2}, [x = - \frac{1}{2}, y = 0], [x = 0, y = - 1], S_{5}, [x = 0, y = 1], [x = \frac{1}{2}, y = 0]]$

$[[x~ = - 2, y~ = 0], [x~ = - 1, y~ = 0], [x~ = - \frac{1}{2}, y~ = 0], [x~ = 0, y~ = - 1], [x~ = 0, y~ = 0], [x~ = 0, y~ = 1], [x~ = \frac{1}{2}, y~ = 0]]$

(2.8)

We also add one sample point $(1, 1)$ not contained on any branch cut:

$S ≔ [S [], [x = 1, y = 1]]$

$[[x~ = - 2, y~ = 0], [x~ = - 1, y~ = 0], [x~ = - \frac{1}{2}, y~ = 0], [x~ = 0, y~ = - 1], [x~ = 0, y~ = 0], [x~ = 0, y~ = 1], [x~ = \frac{1}{2}, y~ = 0], [x~ = 1, y~ = 1]]$

(2.9)

The following graph displays the sample points in relation to the branch cuts.

$display (branchcuts, seq (point (rhs ~ (P)), P \in S), symbol = solidcircle, symbolsize = 20)$

Now we check whether the identity (2.1) holds for all of these sample points:

$f_{1} ≔ \binom{(lhs - rhs) ()}{} | \binom{}{z = x + ⅈ y}$

$\sqrt{{(x~ + I y~)}^{2} - 1} - \sqrt{x~ + I y~ - 1} \sqrt{x~ + I y~ + 1}$

(2.10)

$seq (radnormal (eval (f_{1}, P)), P \in S)$

$2 \sqrt{3}, 0, 0, 2 I \sqrt{2}, 0, 0, 0, 0$

(2.11)

We conclude that (2.1) is not an identity, and we can even say precisely when it fails: on the first interval $x < - 1 and y = 0$ , and on the fourth interval $x = 0 and y < 0$ .

Now we proceed in the same way for the second proposed identity (2.2). The branch cuts are:

$[&Im; (1 - {(x + ⅈ y)}^{2}) = 0, &real; (1 - {(x + ⅈ y)}^{2}) < 0]$

$[- 2 x~ y~ = 0, - {x~}^{2} + {y~}^{2} < - 1]$

(2.12)

$[&Im; (1 - (x + ⅈ y)) = 0, &real; (1 - (x + ⅈ y)) < 0]$

$[- y~ = 0, - x~ < - 1]$

(2.13)

$[&Im; (1 + x + ⅈ y) = 0, &real; (1 + x + ⅈ y) < 0]$

$[y~ = 0, x~ < - 1]$

(2.14)

$branchcuts ≔ display (line ([- 10, 0], [- 1, 0], color = red), line ([1, 0], [10, 0], color = red), line ([1, 0.12], [10, 0.12], color = green), line ([- 10, - 0.12], [- 1, - 0.12], color = blue), thickness = 4, view = [- 5 .. 5, - 5 .. 5]) &colon;$

$branchcuts$

$b_{2} ≔ [,,]$

$[[- 2 x~ y~ = 0, - {x~}^{2} + {y~}^{2} < - 1], [- y~ = 0, - x~ < - 1], [y~ = 0, x~ < - 1]]$

(2.15)

$S ≔ CylindricalAlgebraicDecompose (b_{2}, R, output = rootof)$

$[[x~ < - 1, y~ = 0], [1 < x~, y~ = 0]]$

(2.16)

We need only 2+1 sample points in this case:

$S ≔ [[x = - 2, y = 0], [x = 0, y = 0], [x = 2, y = 0]]$

$[[x~ = - 2, y~ = 0], [x~ = 0, y~ = 0], [x~ = 2, y~ = 0]]$

(2.17)

$display (branchcuts, seq (point (rhs ~ (P)), P \in S), symbol = solidcircle, symbolsize = 20)$

$f_{2} ≔ \binom{(lhs - rhs) ()}{} | \binom{}{z = x + ⅈ y}$

$\sqrt{1 - {(x~ + I y~)}^{2}} - \sqrt{1 - x~ - I y~} \sqrt{x~ + I y~ + 1}$

(2.18)

$seq (radnormal (eval (f_{2}, P)), P \in S)$

$0, 0, 0$

(2.19)

Thus we have proved that (2.2) is indeed an identity.

Download Help Document

Maple

Maple Add-Ons

MapleSim

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim

Maple

Powerful math software that is easy to use

Maple Add-Ons

MapleSim

Advanced System Level Modeling

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim