RealRootClassification - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


RegularChains[ParametricSystemTools]

  

RealRootClassification

  

compute a real root classification of a parametric semi-algebraic system

 

Calling Sequence

Parameters

Description

Options

Examples

References

Calling Sequence

RealRootClassification(F, N, P, H, d, n, R)

RealRootClassification(F, N, P, H, d, r, R)

RealRootClassification(F, N, P, H, d, n, R, 'output'='formula')

RealRootClassification(F, N, P, H, d, n, R, 'output'='samples')

Parameters

R

-

polynomial ring

F

-

list of polynomials of R

N

-

list of polynomials of R

P

-

list of polynomials of R

H

-

list of polynomials of R

d

-

positive integer

n

-

non-negative integer

r

-

non-negative integer range or an integer range

Description

• 

For a semi-algebraic system with parametric variables (parameters), RealRootClassification computes conditions on the parameters for the system to have a given number of real solutions.

• 

More precisely, consider a semi-algebraic system S with polynomial equations, non-negative polynomial inequalities, (strictly) positive polynomial inequalities, and polynomial inequations given respectively by F, N, P, and H, and with the last d variables of R as parameters.

  

This command returns a pair C,BP, such that, provided BP does not vanish, the semi-algebraic system S has exactly n distinct real solutions (or, the number of distinct real solutions of S falls into the range r) if and only if the parameters are taking values in C.

• 

In the returned pair, C,BP, C is of type semi_algebraic_set (a list of regular_semi_algebraic_sets) representing the conditions, and BP is of type border_polynomial excluding some exceptional parameter values. Note that all the polynomials in C and BP involve only parameters.

• 

Note that, in special circumstances, the returned pair C,BP is not well defined. See BorderPolynomial or the related explanation below.

• 

r is an integer range of the form a..k where a is a non-negative integer and k is either a non-negative integer satisfying ak or a name without value standing for infinity.

• 

There are two special cases where the computed condition C,BP is not well defined or does not return the expected answer. One is when the system S is positive dimensional for almost all parameter values. In this case some variables will be treated as parameters, and the command returns conditions for the system to have real solutions w.r.t. the new parameters set. The second case is when the input system is inconsistent.

• 

There are 2 representations of regular_semi_algebraic_sets in the current implementation according to the different nature of the input systems. The related representations are quantifier-free formula, quantifier-free formula with n-th root indices, and isolating box. For the latter one, see RealRootIsolate.

• 

One can get a more detailed description on the result of the command RealRootClassification by setting the infolevel variable to be greater than 0 (see the examples below).

• 

Because of the inner representation of data in Maple and the strategy of formula simplification in RealRootClassification, the output conditions C for mathematically equivalent input (e.g. all are same but different variable order in ring R) may be different in their form but are equivalent to each other, of course.

• 

The algorithm is described in the paper by Yang, L., Hou, X., Xia, B. "A complete algorithm for automated discovering of a class of inequality-type theorems." Sci. China Ser. F, Vol. 44 (2001): 33--49.

• 

The algorithm is complete in theory, however, the command RealRootClassification may quit and output a necessary condition for some examples due to too heavy computation.

Options

• 

The option 'output'='samples' modifies the algorithm as follows: instead of returning a pair, C,BP, where C is of type semi_algebraic_set (a list of regular_semi_algebraic_sets) the command returns sample points in the parameter space. All these sample points belong to the complement of the hypersurface defined by BP in the parameter space. Moreover there is at least sample point per connected component satisfying the following property: the input parametric semi-algebraic system S has n distinct real solutions (or, the number of distinct real solutions of S falls into the range r) above this component. In addition, there is no sample points belonging to the connected components not satisfying the previous property.

• 

The option 'output'='samples' also modifies the output format as follows. It is a record with five fields. DecomposedSystems is a list of basic semi-algebraic systems  (each of them consisting of a list of equational constraints and a list positive inequality constraints) such that the union of their solution sets equals the solution set of the input semi-algebraic system S outside of the hypersurface defined by its border polynomial. BorderPolynomial is the border polynomial of S as computed by this command. Parameters lists the parameters in the projection order used by the underlying OPENCAD sampling algorithm. ProjectionPolynomials is a list of lists of polynomials, where each inner list consists of the polynomials used in each OPENCAD projection. SamplePoints is the list of the sample points described above.

• 

The option 'output'='formula' is the default option of this command.

  

The computations performed for the option 'output'='samples' are a first step in the computations  performed for option 'output'='formula'. This latter option is often more computationally intensive than the former one while the information provided by this former may often be sufficient in practice.

Examples

withRegularChains:

withParametricSystemTools:

withSemiAlgebraicSetTools:

RPolynomialRingx,a,b,c

Rpolynomial_ring

(1)

Fax2+bx+c;N;P;H

Fax2+bx+c

N

P

H

(2)

We compute the condition on a,b,c for the system to have no real solutions.

rrcRealRootClassificationF,N,P,H,3,0,R

rrcregular_semi_algebraic_set,border_polynomial

(3)

We first inspect the border polynomial.

Inforrc2,R

a,4ac+b2

(4)

We then inspect the regular semi-algebraic set.

rcRepresentingChainrrc11,R

rcregular_chain

(5)

Inforc,R

(6)

rsasrrc11

rsasregular_semi_algebraic_set

(7)

pbxRepresentingBoxrsas,R

pbxparametric_box

(8)

qffRepresentingQuantifierFreeFormulapbx

qffquantifier_free_formula

(9)

Infoqff,R

4acb2,1

(10)

We now pretty print the quantifier-free formula.

DisplayQuantifierFreeFormulaqff:

4acb2>0

(11)

We compute the condition on a,b,c for the system to have real solutions.

rrcRealRootClassificationF,N,P,H,3,1..k,R

rrcregular_semi_algebraic_set,border_polynomial

(12)

We first inspect the border polynomial.

Inforrc2,R

a,4ac+b2

(13)

We then inspect the regular semi-algebraic set.

rcRepresentingChainrrc11,R

rcregular_chain

(14)

Inforc,R

(15)

rsasrrc11

rsasregular_semi_algebraic_set

(16)

pbxRepresentingBoxrsas,R

pbxparametric_box

(17)

qffRepresentingQuantifierFreeFormulapbx

qffquantifier_free_formula

(18)

We now pretty print the quantifier-free formula.

DisplayQuantifierFreeFormulaqff:

4acb2<0

(19)

Below we make use of the option 'output'='samples' for the cases where the input system has exactly one positive solution when a is positive.

rrcRealRootClassificationF&comma;N&comma;a&comma;x&comma;H&comma;3&comma;1&comma;R&comma;output=samples

rrcParameters&colon;c&comma;b&comma;aBorderPolynomial&colon;a&comma;c&comma;4ac+b2ProjectionPolynomials&colon;c&comma;b&comma;a&comma;4ac+b2SamplePoints&colon;c=12&comma;b=12&comma;a=12&comma;c=12&comma;b=12&comma;a=12DecomposedSystems&colon;x2a+xb+c&comma;a&comma;x

(20)

Using the info printing an alternative and more verbose output is illustrated hereafter.

infolevelRegularChains1&colon;

We consider another parametric semi-algebraic system.

RPolynomialRingz&comma;y&comma;x&comma;b&comma;a

Rpolynomial_ring

(21)

Fx2+y2xy1&comma;y2+z2yza2&comma;z2+x2zxb2

Fx2xy+y21&comma;a2+y2yz+z2&comma;b2+x2zx+z2

(22)

Na1&comma;ba&semi;Px&comma;y&comma;z&comma;a&comma;b&comma;a+1b&semi;H

Na1&comma;ba

Px&comma;y&comma;z&comma;a&comma;b&comma;a+1b

H

(23)

We compute the conditions on b&comma;a for the system to have exactly two distinct real solutions.

rrcRealRootClassificationF&comma;N&comma;P&comma;H&comma;2&comma;2&comma;R

RealRootClassification:   FINAL RESULT:
RealRootClassification:   The system has given number of real solution(s) IF AND ONLY IF
RealRootClassification:   [R[1] < 0, 0 < R[2], 0 < R[3]]
RealRootClassification:   where                                                  
RealRootClassification:   R[1] = a^2-b^2+b-1
RealRootClassification:   R[2] = a^2-b^2+a+1
RealRootClassification:   R[3] = 81*a^12-216*a^10*b^2+144*a^8*b^4-18*a^6*b^6+144*a^4*b^8-216*a^2*b^10+81*b^12-216*a^10+414*a^8*b^2-204*a^6*b^4-204*a^4*b^6+414*a^2*b^8-216*b^10+144*a^8-204*a^6*b^2+241*a^4*b^4-204*a^2*b^6+144*b^8-18*a^6-204*a^4*b^2-204*a^2*b^4-18*b^6+144*a^4+414*a^2*b^2+144*b^4-216*a^2-216*b^2+81
RealRootClassification:   PROVIDED THAT                                                 
RealRootClassification:   a-1 <> 0
RealRootClassification:   a-b <> 0
RealRootClassification:   b-1 <> 0
RealRootClassification:   b+1 <> 0
RealRootClassification:   a+1 <> 0
RealRootClassification:   a+b <> 0
RealRootClassification:   a^2-b^2-b-1 <> 0
RealRootClassification:   a^2-b^2+b-1 <> 0
RealRootClassification:   a^2-b^2-a+1 <> 0
RealRootClassification:   a^2-b^2+a+1 <> 0
RealRootClassification:   a^2-a*b+b^2-1 <> 0
RealRootClassification:   a^2+a*b+b^2-1 <> 0
RealRootClassification:   81*a^12-216*a^10*b^2+144*a^8*b^4-18*a^6*b^6+144*a^4*b^8-216*a^2*b^10+81*b^12-216*a^10+414*a^8*b^2-204*a^6*b^4-204*a^4*b^6+414*a^2*b^8-216*b^10+144*a^8-204*a^6*b^2+241*a^4*b^4-204*a^2*b^6+144*b^8-18*a^6-204*a^4*b^2-204*a^2*b^4-18*b^6+144*a^4+414*a^2*b^2+144*b^4-216*a^2-216*b^2+81 <> 0
RealRootClassification:   1.861*seconds

rrcregular_semi_algebraic_set&comma;border_polynomial

(24)

We first inspect the border polynomial.

Inforrc2&comma;R

a1&comma;a+1&comma;a+b&comma;ab&comma;b1&comma;b+1&comma;129b6+169b4+169b8+169a46827a6b2+24181a4b46827a2b66827a4b26827a2b4+469a2b283a2+a12+b1283a1083b1083b229a66827a4b6+469a2b883a10b2+169a8b429a6b6+169a4b883a2b10+469a8b26827a6b4+169a8&comma;a2b2b1&comma;a2b2+b1&comma;a2b2a+1&comma;a2b2+a+1&comma;a2ab+b21&comma;a2+ab+b21

(25)

We then inspect the regular semi-algebraic set.

rcRepresentingChainrrc11&comma;R

rcregular_chain

(26)

Inforc&comma;R

(27)

pbxRepresentingBoxrrc11&comma;R

pbxparametric_box

(28)

qffRepresentingQuantifierFreeFormulapbx

qffquantifier_free_formula

(29)

DisplayQuantifierFreeFormulaqff&colon;

a2b2+b<1anda2b2+a+1>0and81a12216a10b2+144a8b418a6b6+144a4b8216a2b10+81b12216a10+414a8b2204a6b4204a4b6+414a2b8216b10+144a8204a6b2+241a4b4204a2b6+144b818a6204a4b2204a2b418b6+144a4+414a2b2+144b4216a2216b2+81>0

(30)

We discuss the situation when the parameter satisfies a^2+a+1=0.

RealRootClassificationa2+a+1&comma;opF&comma;N&comma;P&comma;H&comma;2&comma;2&comma;R

RealRootClassification:   The system does NOT have the given number of real solution(s)!
RealRootClassification:   .72e-1*seconds

&comma;border_polynomial

(31)

In the printed information below, (1)S[1] means that if b is specified and satisfies the output inequality, a should be the least real root of S[1].

RPolynomialRingx&comma;a&comma;b&comma;c

Rpolynomial_ring

(32)

In the following example, we compute the real root classification of x4+x2a+xb+c=0 when the parameters satisfy b=0 and 2a3+8ac9b2=0.

Fb&comma;2a3+8ac9b2&comma;x4+ax2+bx+c&semi;N&semi;P&semi;H

Fb&comma;2a3+8ac9b2&comma;x4+x2a+xb+c

N

P

H

(33)

RealRootClassificationF&comma;N&comma;P&comma;H&comma;3&comma;1..4&comma;R

RealRootClassification:   The system has given number of real solution(s) IF AND ONLY IF
RealRootClassification:   [R[1] < 0, `(1)S`[1], `(1)S`[2]]
RealRootClassification:   where                                                      
RealRootClassification:   R[1] = a
RealRootClassification:   and                                                        
RealRootClassification:   S[1] = b
RealRootClassification:   S[2] = a^2-4*c
RealRootClassification:   PROVIDED THAT                     
RealRootClassification:   a <> 0
RealRootClassification:   .12e-1*seconds

regular_semi_algebraic_set&comma;border_polynomial

(34)

References

  

Yang, L.; Hou, X.; and Xia, B. "A complete algorithm for automated discovering of a class of inequality-type theorems." Science in China Ser F. Vol. 44, (2001): 33-49.

See Also

BorderPolynomial

ComplexRootClassification

DiscriminantSequence

RealRootCounting

RealRootIsolate

RegularChains