RegularChains[SemiAlgebraicSetTools] - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Factorization and Solving Equations : RegularChains : SemiAlgebraicSetTools Subpackage : RegularChains/SemiAlgebraicSetTools/RealRootIsolate

RegularChains[SemiAlgebraicSetTools]

  

RealRootIsolate

  

isolate real roots

  

BoxValues

  

extract values from a box

 

Calling Sequence

Parameters

Description

Examples

References

Calling Sequence

RealRootIsolate(F, N, P, H, R, opts)

RealRootIsolate(rc, R, opts)

BoxValues(box, R)

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

rc

-

regular chain of R

opts

-

(optional) equation(s) of the form keyword=value where keyword is one of 'abserr', 'rerr', 'constraints', or 'method'.

box

-

box isolating a root

Description

• 

The RealRootIsolate command returns a list of boxes. Each box isolates exactly one real root of the regular chain rc or semi-algebraic system S whose polynomial equations, non-negative polynomial inequalities, (strictly) positive polynomial inequalities and polynomial inequations are given respectively by F, N, P, and H. Moreover, it is guaranteed that all real solutions are found. The regular chain rc or semi-algebraic system S has to be zero-dimensional (see IsZeroDimensional). Furthermore, rc must be square-free (see Squarefree and the radical option of Triangularize).

• 

Each box returned by the RealRootIsolate command is a Cartesian product of open intervals or singletons. The BoxValues command retrieves a detailed description of the box parameter and returns a list of elements of the form v&equals;a&comma;b (with a<b) or v&equals;a. In the former case, it means that a<v<b . In the latter case, it means that the value of v is a.

• 

The options 'abserr'=avalue and 'rerr'=rvalue can be used to specify the maximal size of the returned boxes. When one of these options is provided, avalue or rvalue should be a positive rational number. In the first case, all boxes returned by the RealRootIsolate will have a width smaller than or equal to avalue; in the second case, the ratio of the width and the absolute value of the encoded non-zero real algebraic number is smaller than or equal to rvalue, where the width of a box is defined as the maximum of the widths of the intervals of box.

• 

The option 'constraints'=value can be used to constrain the range of the variables.  This option can be used in the calling sequence with a regular chain rc. value should be a list of equations of the form v=cons_v, where v is a variable name. Not all variables need to be constrained, and each variable should appear at most once in the list value. The RealRootIsolate will only return solutions which satisfy all constraints. The cons_v can have one of the following forms, depending on the desired constraint: a (meaning v&equals;a), a&comma;b (meaning a<v<b ), closeda&comma;b (meaning a<=v<b ), a&comma;closedb (meaning a<v<=b ), closeda&comma;closedb (meaning a<=v<=b ).

• 

You can specify the algorithm using the option 'method' = 'VincentCollinsAkritas' or 'Discoverer'. The first one is a generalization of the Vincent-Collins-Akritas algorithm which isolates real roots for univariate polynomials. The techniques are very close to the ones used by Renaud Rioboo in his ISSAC 1992 paper (see reference below). The other one implements the algorithm of the paper "Real Solution Isolation Using Interval Arithmetic" by B. Xia and T. Zhang. By default, the first one is used. However, the second one can often do better on large input data.

Examples

withRegularChains&colon;

withChainTools&colon;

withSemiAlgebraicSetTools&colon;

RPolynomialRingy&comma;x

R:=polynomial_ring

(1)

Fx320x&comma;y22x&colon;Ny&colon;Px&colon;Hx&plus;y&colon;

LRealRootIsolateF&comma;N&comma;P&comma;H&comma;R

L:=box

(2)

Note that the constraints option is not supported in this calling sequence with four polynomial sets F, N, P and H. Other examples hereafter illustrate the use of the constraints option.

mapBoxValues&comma;L&comma;R

y&equals;2&comma;4&comma;x&equals;154&comma;5

(3)

LRealRootIsolateF&comma;N&comma;P&comma;H&comma;R&comma;&apos;abserr&apos;&equals;125

L:=box

(4)

mapBoxValues&comma;L&comma;R

y&equals;381128&comma;3&comma;x&equals;28564&comma;1145256

(5)

LRealRootIsolateF&comma;N&comma;P&comma;H&comma;R&comma;&apos;rerr&apos;&equals;125

L:=box

(6)

mapBoxValues&comma;L&comma;R

y&equals;4716&comma;3&comma;x&equals;28564&comma;575128

(7)

LRealRootIsolateF&comma;N&comma;P&comma;H&comma;R&comma;method&equals;&apos;Discoverer&apos;

L:=box

(8)

mapBoxValues&comma;L&comma;R

y&equals;238&comma;3&comma;x&equals;14332&comma;573128

(9)

LRealRootIsolateF&comma;N&comma;P&comma;H&comma;R&comma;&apos;rerr&apos;&equals;1210&comma;method&equals;&apos;Discoverer&apos;

L:=box

(10)

mapBoxValues&comma;L&comma;R

y&equals;4899916384&comma;61252048&comma;x&equals;366358192&comma;91592048

(11)

Build a simple regular chain:

CChain2x21&comma;3y3x&comma;EmptyR&comma;R

C:=regular_chain

(12)

LRealRootIsolateC&comma;R

L:=box&comma;box

(13)

Retrieve the box values:

mapBoxValues&comma;L&comma;R

y&equals;0&comma;1&comma;x&equals;12&comma;1&comma;y&equals;1&comma;0&comma;x&equals;1&comma;12

(14)

Using the 'abserr' option:

LRealRootIsolateC&comma;R&comma;&apos;abserr&apos;&equals;11010

L:=box&comma;box

(15)

mapBoxValues&comma;L&comma;R

y&equals;1061225723317179869184&comma;6632660771073741824&comma;x&equals;194368031999274877906944&comma;97184015999137438953472&comma;y&equals;6632660771073741824&comma;1061225723317179869184&comma;x&equals;97184015999137438953472&comma;194368031999274877906944

(16)

Using the 'constraints' option:

CChainx22&comma;y1yx&comma;EmptyR&comma;R

C:=regular_chain

(17)

LRealRootIsolateC&comma;R&comma;&apos;constraints&apos;&equals;

L:=box&comma;box&comma;box&comma;box

(18)

mapBoxValues&comma;L&comma;R

y&equals;1&comma;x&equals;0&comma;2&comma;y&equals;1&comma;x&equals;2&comma;0&comma;y&equals;1&comma;3&comma;x&equals;0&comma;2&comma;y&equals;3&comma;1&comma;x&equals;2&comma;0

(19)

LRealRootIsolateC&comma;R&comma;&apos;constraints&apos;&equals;x&equals;4

L:=

(20)

LRealRootIsolateC&comma;R&comma;&apos;constraints&apos;&equals;x&equals;1&comma;2

L:=box&comma;box

(21)

mapBoxValues&comma;L&comma;R

y&equals;12&comma;118&comma;x&equals;4532&comma;2316&comma;y&equals;118&comma;94&comma;x&equals;4532&comma;2316

(22)

LRealRootIsolateC&comma;R&comma;&apos;constraints&apos;&equals;y&equals;1

L:=box&comma;box

(23)

mapBoxValues&comma;L&comma;R

y&equals;1&comma;x&equals;0&comma;2&comma;y&equals;1&comma;x&equals;2&comma;0

(24)

LRealRootIsolateC&comma;R&comma;&apos;constraints&apos;&equals;y&equals;closed1&comma;2

L:=box&comma;box&comma;box

(25)

mapBoxValues&comma;L&comma;R

y&equals;1&comma;x&equals;0&comma;2&comma;y&equals;1&comma;x&equals;2&comma;0&comma;y&equals;1&comma;2&comma;x&equals;54&comma;32

(26)

LRealRootIsolateC&comma;R&comma;&apos;constraints&apos;&equals;y&equals;closed1&comma;1110

L:=box&comma;box

(27)

mapBoxValues&comma;L&comma;R

y&equals;1&comma;x&equals;0&comma;2&comma;y&equals;1&comma;x&equals;2&comma;0

(28)

LRealRootIsolateC&comma;R&comma;&apos;constraints&apos;&equals;y&equals;1&comma;2

L:=box

(29)

mapBoxValues&comma;L&comma;R

y&equals;1&comma;2&comma;x&equals;54&comma;32

(30)

References

  

F. Boulier, C. Chen, F. Lemaire, M. Moreno Maza "Real root isolation of regular chains." ASCM'2009, Math-for-Industry, Lecture Note Series Vol. 22.

  

R. Rioboo "Computation of the real closure of an ordered field." ISSAC'92, Academic Press, San Francisco.

  

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

  

B. Xia, L. Yang "An Algorithm for Isolating the Real Solutions of Semi-algebraic Systems." J. Symb. Comput. , Vol. 34, Num. 5 (2002): 461-477.

  

B. Xia, T. Zhang "Real Solution Isolation Using Interval Arithmetic." Computers and Mathematics with Applications, Vol. 52, (2006): 853-860.

See Also

RealTriangularize

RefineBox

RefineListBox

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam