login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

Edit detail for Cylindrical Algebraic Decomposition revision 2 of 4

1 2 3 4
Editor: Bill page
Time: 2014/04/11 18:34:46 GMT+0
Note: formatting and projectionSet fix

added:
CylindricalAlgebraicDecompositionUtilities

added:
SimpleCell

changed:
---  VARS ==> VariationsPackage(TheField,ThePols)
  --  VARS ==> VariationsPackage(TheField,ThePols)

added:
Cell

removed:
-     
-

added:
CylindricalAlgebraicDecompositionPackage

changed:
-       f : ((RUP,RUP) -> Boolean) := (degree(#1) <= degree(#2))
       f : ((RUP,RUP) -> Boolean) := (x,y)+->(degree(x) <= degree(y))

added:
Test Input

removed:
-)lib )dir .

On Wednesday, October 12, 2005 5:29 PM Renaud Rioboo wrote:

Dear Axiom fans,

In the last few years there have been a regain of interest in some Computer Algebra users circles about Cylindrical Algebraic Decomposition (aka CAD). As some of you may know my thesis was about CAD and I am regularly receiving queries about CAD and the Axiom implementation I wrote.

I already privately gave sources or ran particular problems for some people but I have never officially released my sources because I do not think they are at production level and many work has still to be done on them.

Recently Martin Rubey thought it could be a good idea to release them and I have of course no objection on that point nor on sharing these sources with the community. If there is some interest on it you may include it into the Axiom distribution with the same permissions than the rest of the software.

While I wait for my lab to give me the necessary permissions to be able to use Axiom and export this software you may find it's sources at the unlisted url

http://rioboo.free.fr/CadPub/

I would like to add just a few words about that work which is a straightforward implementation of the standard papers by Arnon, Collins and McCallum? which are more than 20 years old now.

My work on Cad is 15 years old and was developped for the defense of my thesis where CAD was an sample application for real algebraic numbers manipulations. By the time I wrote it I also needed some subresultant calculations which were not in Axiom (Scratchpad by that time) and the required machinery to work with real algebraic numbers.

Along the times, real algebraic numbers were included into Axiom and subresultant calculations which are used in several places of the Axiom Library were modified to all use Lionel Ducos's package which enables a performance gain. While making these modifications to Axiom I tried to keep my CAD package up-to-date with the Axiom Library and have used it as a test for other packages. It thus should compile under recent Axiom versions and should compute something that resembles a CAD.

Don't expect this package to be the absolute CAD program, I never found time to further work on it in order to include many enhancements which are present in other CAD packages. While Axiom versions evolved I had to remove what I thought were enhancements and remove some support for generalization. As of today it only includes one projection method which is the McCallum? projection and no reconstruction nor adjacency's are taken into account.

However it did reasonabily compare with more recent techniques such as Rational Univariate Representation (aka RUR) for simple cases though it could not produce results for some more complicated cases. By the time this comparison was made Axiom had some severe memory restrictions which seem to have disappear now. I thus think that many objections to using CAD could now be revised.

For hard problems this package should thus not be worse than any other CAD package except that you cannot fall into an optimzation drawback :-) There is no optimization !

I will of course try to maintain the package to the best of my ability. One thing I should do is include comments describing the different functions, but even that requires going into the code and the algorithms which are quite old for me now.

Let me know if there is some interest on it.

Best regards,

Renaud


CylindricalAlgebraicDecompositionUtilities?

spad
)ab pack CADU CylindricalAlgebraicDecompositionUtilities
CylindricalAlgebraicDecompositionUtilities(R,P) : PUB == PRIV where
-- Tese are some standard tools which are needed to compute with univariate -- polynomials. -- -- A gcd basis for a set of polynomials is a set of pairwise relatively prime -- polynomials which all divide the original set and whose product is the -- same than the product of the original set. -- -- A square free basis for a list of polynomials is just a list -- of square free polynomials which are pairwise relatively primes and have -- the same roots than the original polynomials.
R : GcdDomain P : UnivariatePolynomialCategory(R)
PUB == with squareFreeBasis : List(P) -> List(P) ++ gcdBasis : List(P) -> List(P) ++ decompose a list of polynomials into pairwise relatively ++ prime polynomials gcdBasisAdd : (P,List(P)) -> List(P) ++ add one polynomial to list of pairwise relatively prime polynomials
PRIV == add
squareFreeBasis(lpols) == lpols = [] => [] pol := first(lpols) sqpol := unitCanonical(squareFreePart(pol)) gcdBasis(cons(sqpol,squareFreeBasis(rest(lpols))))
gcdBasisAdd(p,lpols) == (degree(p) = 0) => lpols null lpols => [unitCanonical p] p1 := first(lpols) g := gcd(p,p1) (degree(g) = 0) => cons(p1,gcdBasisAdd(p,rest lpols)) p := (p exquo g)::P p1 := (p1 exquo g)::P basis := gcdBasisAdd(p,rest(lpols)) if degree(p1) > 0 then basis := cons(p1,basis) gcdBasisAdd(g,basis)
gcdBasis(lpols) == (#lpols <= 1) => lpols basis := gcdBasis(rest lpols) gcdBasisAdd(first(lpols),basis)
spad
   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/4986109030324487666-25px001.spad
      using old system compiler.
   CADU abbreviates package CylindricalAlgebraicDecompositionUtilities 
------------------------------------------------------------------------
   initializing NRLIB CADU for CylindricalAlgebraicDecompositionUtilities 
   compiling into NRLIB CADU 
   compiling exported squareFreeBasis : List P -> List P
Time: 0.04 SEC.
compiling exported gcdBasisAdd : (P,List P) -> List P Time: 0.01 SEC.
compiling exported gcdBasis : List P -> List P Time: 0 SEC.
(time taken in buildFunctor: 0)
;;; *** |CylindricalAlgebraicDecompositionUtilities| REDEFINED
;;; *** |CylindricalAlgebraicDecompositionUtilities| REDEFINED Time: 0 SEC.
Cumulative Statistics for Constructor CylindricalAlgebraicDecompositionUtilities Time: 0.05 seconds
finalizing NRLIB CADU Processing CylindricalAlgebraicDecompositionUtilities for Browser database: --->-->CylindricalAlgebraicDecompositionUtilities(constructor): Not documented!!!! --------(squareFreeBasis ((List P) (List P)))--------- --------(gcdBasis ((List P) (List P)))--------- --->-->CylindricalAlgebraicDecompositionUtilities((gcdBasis ((List P) (List P)))): Improper first word in comments: decompose "decompose a list of polynomials into pairwise relatively prime polynomials" --------(gcdBasisAdd ((List P) P (List P)))--------- --->-->CylindricalAlgebraicDecompositionUtilities((gcdBasisAdd ((List P) P (List P)))): Improper first word in comments: add "add one polynomial to list of pairwise relatively prime polynomials" --->-->CylindricalAlgebraicDecompositionUtilities(): Missing Description ; compiling file "/var/aw/var/LatexWiki/CADU.NRLIB/CADU.lsp" (written 11 APR 2014 06:34:38 PM):
; /var/aw/var/LatexWiki/CADU.NRLIB/CADU.fasl written ; compilation finished in 0:00:00.026 ------------------------------------------------------------------------ CylindricalAlgebraicDecompositionUtilities is now explicitly exposed in frame initial CylindricalAlgebraicDecompositionUtilities will be automatically loaded when needed from /var/aw/var/LatexWiki/CADU.NRLIB/CADU

SimpleCell?

spad
)ab domain SCELL SimpleCell
-- This domain is made to work with one-dimensional semi-algebraic cells -- ie either an algebraic point, either an interval. The point is specified as -- specification of an algebraic value.
SimpleCell(TheField,ThePols) : PUB == PRIV where TheField : RealClosedField ThePols : UnivariatePolynomialCategory(TheField) O ==> OutputForm B ==> Boolean Z ==> Integer N ==> NonNegativeInteger
-- VARS ==> VariationsPackage(TheField,ThePols) VARS ==> RealPolynomialUtilitiesPackage(TheField,ThePols) LF ==> List(TheField)
PUB == CoercibleTo(O) with
allSimpleCells : (ThePols,Symbol) -> List % allSimpleCells : (List(ThePols),Symbol) -> List % hasDimension? : % -> B samplePoint : % -> TheField stablePol : % -> ThePols variableOf : % -> Symbol separe : (LF,TheField,TheField) -> LF pointToCell : (TheField,B,Symbol) -> %
PRIV == add
Rep := Record(samplePoint:TheField, hasDim:B, varOf:Symbol)
samplePoint(c) == c.samplePoint
stablePol(c) == error "Prout"
hasDimension?(c) == c.hasDim
variableOf(c) == c.varOf
coerce(c:%):O == o : O := ((c.varOf)::O) = ((c.samplePoint)::O) brace [o,(c.hasDim)::O]
separe(liste,gauche,droite) == milieu : TheField := (gauche + droite) / (2::TheField) liste = [] => [milieu] #liste = 1 => [gauche,first(liste),droite] nbe := first(liste) lg :List(TheField) := [] ld :List(TheField) := rest(liste) sg := sign(milieu-nbe) while sg > 0 repeat lg := cons(nbe,lg) ld = [] => return(separe(reverse(lg),gauche,milieu)) nbe := first(ld) sg := sign(milieu-nbe) ld := rest(ld) sg < 0 => append(separe(reverse(lg),gauche,milieu), rest(separe(cons(nbe,ld),milieu,droite))) newDroite := (gauche+milieu)/(2::TheField) null lg => newGauche := (milieu+droite)/(2::TheField) while newGauche >= first(ld) repeat newGauche := (milieu+newGauche)/(2::TheField) append([gauche,milieu],separe(ld,newGauche,droite)) while newDroite <= first(lg) repeat newDroite := (newDroite+milieu)/(2::TheField) newGauche := (milieu+droite)/(2::TheField) null ld => append(separe(reverse(lg),gauche,newDroite),[milieu,droite]) while newGauche >= first(ld) repeat newGauche := (milieu+newGauche)/(2::TheField) append(separe(reverse(lg),gauche,newDroite), cons(milieu,separe(ld,newGauche,droite)))
pointToCell(sp,hasDim?,varName) == [sp,hasDim?,varName]$Rep
allSimpleCells(p:ThePols,var:Symbol) == allSimpleCells([p],var)
PACK ==> CylindricalAlgebraicDecompositionUtilities(TheField,ThePols) allSimpleCells(lp:List(ThePols),var:Symbol) == lp1 := gcdBasis(lp)$PACK null(lp1) => [pointToCell(0,true,var)] b := ("max" / [ boundOfCauchy(p)$VARS for p in lp1 ])::TheField l := "append" / [allRootsOf(makeSUP(unitCanonical(p))) for p in lp1] l := sort(l) l1 := separe(l,-b,b) res : List(%) := [pointToCell(first(l1),true,var)] l1 := rest(l1) while not(null(l1)) repeat res := cons(pointToCell(first(l1),false,var),res) l1 := rest(l1) l1 = [] => return(error "Liste vide") res := cons(pointToCell(first(l1),true,var),res) l1 := rest(l1) reverse! res
spad
   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/2449457199855673372-25px002.spad
      using old system compiler.
   SCELL abbreviates domain SimpleCell 
------------------------------------------------------------------------
   initializing NRLIB SCELL for SimpleCell 
   compiling into NRLIB SCELL 
   compiling exported samplePoint : $ -> TheField
      SCELL;samplePoint;$TheField;1 is replaced by QVELTc0 
Time: 0.01 SEC.
compiling exported stablePol : $ -> ThePols SCELL;stablePol;$ThePols;2 is replaced by errorProut Time: 0 SEC.
compiling exported hasDimension? : $ -> Boolean SCELL;hasDimension?;$B;3 is replaced by QVELTc1 Time: 0 SEC.
compiling exported variableOf : $ -> Symbol SCELL;variableOf;$S;4 is replaced by QVELTc2 Time: 0 SEC.
compiling exported coerce : $ -> OutputForm Time: 0 SEC.
compiling exported separe : (List TheField,TheField,TheField) -> List TheField Time: 0.01 SEC.
compiling exported pointToCell : (TheField,Boolean,Symbol) -> $ SCELL;pointToCell;TheFieldBS$;7 is replaced by VECTOR Time: 0 SEC.
compiling exported allSimpleCells : (ThePols,Symbol) -> List $ Time: 0 SEC.
processing macro definition PACK ==> CylindricalAlgebraicDecompositionUtilities(TheField,ThePols) compiling exported allSimpleCells : (List ThePols,Symbol) -> List $ Time: 0.02 SEC.
(time taken in buildFunctor: 0)
;;; *** |SimpleCell| REDEFINED
;;; *** |SimpleCell| REDEFINED Time: 0 SEC.
Cumulative Statistics for Constructor SimpleCell Time: 0.04 seconds
finalizing NRLIB SCELL Processing SimpleCell for Browser database: --->-->SimpleCell(constructor): Not documented!!!! --->-->SimpleCell((allSimpleCells ((List %) ThePols (Symbol)))): Not documented!!!! --->-->SimpleCell((allSimpleCells ((List %) (List ThePols) (Symbol)))): Not documented!!!! --->-->SimpleCell((hasDimension? ((Boolean) %))): Not documented!!!! --->-->SimpleCell((samplePoint (TheField %))): Not documented!!!! --->-->SimpleCell((stablePol (ThePols %))): Not documented!!!! --->-->SimpleCell((variableOf ((Symbol) %))): Not documented!!!! --->-->SimpleCell((separe ((List TheField) (List TheField) TheField TheField))): Not documented!!!! --->-->SimpleCell((pointToCell (% TheField (Boolean) (Symbol)))): Not documented!!!! --->-->SimpleCell(): Missing Description ; compiling file "/var/aw/var/LatexWiki/SCELL.NRLIB/SCELL.lsp" (written 11 APR 2014 06:34:40 PM):
; /var/aw/var/LatexWiki/SCELL.NRLIB/SCELL.fasl written ; compilation finished in 0:00:00.071 ------------------------------------------------------------------------ SimpleCell is now explicitly exposed in frame initial SimpleCell will be automatically loaded when needed from /var/aw/var/LatexWiki/SCELL.NRLIB/SCELL

Cell

spad
)ab domain CELL Cell
Cell(TheField) : PUB == PRIV where TheField : RealClosedField
ThePols ==> Polynomial(TheField)
O ==> OutputForm B ==> Boolean Z ==> Integer N ==> NonNegativeInteger BUP ==> SparseUnivariatePolynomial(TheField) SCELL ==> SimpleCell(TheField,BUP)
PUB == CoercibleTo(O) with
samplePoint : % -> List(TheField) dimension : % -> N hasDimension? : (%,Symbol) -> B makeCell : List(SCELL) -> % makeCell : (SCELL,%) -> % mainVariableOf : % -> Symbol variablesOf : % -> List Symbol projection : % -> Union(%,"failed")
PRIV == add
Rep := List(SCELL)
coerce(c:%):O == paren [sc::O for sc in c]
projection(cell) == null cell => error "projection: should not appear" r := rest(cell) null r => "failed" r
makeCell(l:List(SCELL)) == l
makeCell(scell,toAdd) == cons(scell,toAdd)
mainVariableOf(cell) == null(cell) => error "Should not appear" variableOf(first(cell))
variablesOf(cell) == null(cell) => [] cons(mainVariableOf(cell),variablesOf(rest(cell)::%))
dimension(cell) == null(cell) => 0 hasDimension?(first(cell)) => 1+dimension(rest(cell)) dimension(rest(cell))
hasDimension?(cell,var) == null(cell) => error "Should not appear" sc : SCELL := first(cell) v := variableOf(sc) v = var => hasDimension?(sc) v < var => false v > var => true error "Caca Prout"
samplePoint(cell) == null(cell) => [] cons(samplePoint(first(cell)),samplePoint(rest(cell)))
spad
   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/1601075696811996402-25px003.spad
      using old system compiler.
   CELL abbreviates domain Cell 
------------------------------------------------------------------------
   initializing NRLIB CELL for Cell 
   compiling into NRLIB CELL 
Local variable Rep type redefined: (Join (ListAggregate (SimpleCell TheField (SparseUnivariatePolynomial TheField))) (CATEGORY domain (SIGNATURE nil ($)) (SIGNATURE null ((Boolean) $)) (SIGNATURE cons ($ (SimpleCell TheField (SparseUnivariatePolynomial TheField)) $)) (SIGNATURE append ($ $ $)) (IF (has (SimpleCell TheField (SparseUnivariatePolynomial TheField)) (BasicType)) (PROGN (SIGNATURE setUnion ($ $ $)) (SIGNATURE setIntersection ($ $ $)) (SIGNATURE setDifference ($ $ $))) noBranch) (IF (has (SimpleCell TheField (SparseUnivariatePolynomial TheField)) (OpenMath)) (ATTRIBUTE (OpenMath)) noBranch))) to (Join (SetCategory) (CATEGORY domain (SIGNATURE construct ((Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))) TheField (Boolean) (Symbol))) (SIGNATURE ~= ((Boolean) (Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))) (Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))))) (SIGNATURE coerce ((OutputForm) (Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))))) (SIGNATURE elt (TheField (Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))) samplePoint)) (SIGNATURE elt ((Boolean) (Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))) hasDim)) (SIGNATURE elt ((Symbol) (Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))) varOf)) (SIGNATURE setelt (TheField (Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))) samplePoint TheField)) (SIGNATURE setelt ((Boolean) (Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))) hasDim (Boolean))) (SIGNATURE setelt ((Symbol) (Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))) varOf (Symbol))) (SIGNATURE copy ((Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol))) (Record (: samplePoint TheField) (: hasDim (Boolean)) (: varOf (Symbol)))))))
   compiling exported coerce : $ -> OutputForm
Time: 0.01 SEC.
compiling exported projection : $ -> Union($,failed) Time: 0 SEC.
compiling exported makeCell : List SimpleCell(TheField,SparseUnivariatePolynomial TheField) -> $ CELL;makeCell;L$;3 is replaced by l Time: 0 SEC.
compiling exported makeCell : (SimpleCell(TheField,SparseUnivariatePolynomial TheField),$) -> $ CELL;makeCell;Sc2$;4 is replaced by CONS Time: 0 SEC.
compiling exported mainVariableOf : $ -> Symbol Time: 0 SEC.
compiling exported variablesOf : $ -> List Symbol Time: 0 SEC.
compiling exported dimension : $ -> NonNegativeInteger Time: 0 SEC.
compiling exported hasDimension? : ($,Symbol) -> Boolean Time: 0 SEC.
compiling exported samplePoint : $ -> List TheField Time: 0 SEC.
(time taken in buildFunctor: 0)
;;; *** |Cell| REDEFINED
;;; *** |Cell| REDEFINED Time: 0 SEC.
Cumulative Statistics for Constructor Cell Time: 0.01 seconds
finalizing NRLIB CELL Processing Cell for Browser database: --->-->Cell(constructor): Not documented!!!! --->-->Cell((samplePoint ((List TheField) %))): Not documented!!!! --->-->Cell((dimension ((NonNegativeInteger) %))): Not documented!!!! --->-->Cell((hasDimension? ((Boolean) % (Symbol)))): Not documented!!!! --->-->Cell((makeCell (% (List (SimpleCell TheField (SparseUnivariatePolynomial TheField)))))): Not documented!!!! --->-->Cell((makeCell (% (SimpleCell TheField (SparseUnivariatePolynomial TheField)) %))): Not documented!!!! --->-->Cell((mainVariableOf ((Symbol) %))): Not documented!!!! --->-->Cell((variablesOf ((List (Symbol)) %))): Not documented!!!! --->-->Cell((projection ((Union % failed) %))): Not documented!!!! --->-->Cell(): Missing Description ; compiling file "/var/aw/var/LatexWiki/CELL.NRLIB/CELL.lsp" (written 11 APR 2014 06:34:41 PM):
; /var/aw/var/LatexWiki/CELL.NRLIB/CELL.fasl written ; compilation finished in 0:00:00.029 ------------------------------------------------------------------------ Cell is now explicitly exposed in frame initial Cell will be automatically loaded when needed from /var/aw/var/LatexWiki/CELL.NRLIB/CELL

CylindricalAlgebraicDecompositionPackage?

spad
)ab pack CAD CylindricalAlgebraicDecompositionPackage
CylindricalAlgebraicDecompositionPackage(TheField) : PUB == PRIV where
TheField : RealClosedField
ThePols ==> Polynomial(TheField) P ==> ThePols BUP ==> SparseUnivariatePolynomial(TheField) RUP ==> SparseUnivariatePolynomial(ThePols)
Z ==> Integer N ==> NonNegativeInteger
CELL ==> Cell(TheField) SCELL ==> SimpleCell(TheField,BUP)
PUB == with
cylindricalDecomposition: List P -> List CELL cylindricalDecomposition: (List(P),List(Symbol)) -> List CELL projectionSet: (List RUP) -> List P coefficientSet: RUP -> List P discriminantSet : List RUP -> List(P) resultantSet : List RUP -> List P principalSubResultantSet : (RUP,RUP) -> List P specialise : (List(ThePols),CELL) -> List(BUP)
PRIV == add
cylindricalDecomposition(lpols) == lv : List(Symbol) := [] for pol in lpols repeat ground?(pol) => "next pol" lv := removeDuplicates(append(variables(pol),lv)) lv := reverse(sort(lv)) cylindricalDecomposition(lpols,lv)
cylindricalDecomposition(lpols,lvars) == lvars = [] => error("CAD: cylindricalDecomposition: empty list of vars") mv := first(lvars) lv := rest(lvars) lv = [] => lp1 := [ univariate(pol) for pol in lpols ] scells := allSimpleCells(lp1,mv)$SCELL [ makeCell([scell]) for scell in scells ] lpols1 := projectionSet [univariate(pol,mv) for pol in lpols] previousCad := cylindricalDecomposition(lpols1,lv) res : List(CELL) := [] for cell in previousCad repeat lspec := specialise(lpols,cell) scells := allSimpleCells(lspec,mv) res := append(res,[makeCell(scell,cell) for scell in scells]) res
PACK1 ==> CylindricalAlgebraicDecompositionUtilities(ThePols,RUP) PACK2 ==> CylindricalAlgebraicDecompositionUtilities(TheField,BUP)
specialise(lpols,cell) == lpols = [] => error("CAD: specialise: empty list of pols") sp := samplePoint(cell) vl := variablesOf(cell) res : List(BUP) := [] for pol in lpols repeat p1 := univariate(eval(pol,vl,sp)) -- zero?(p1) => return(error "Bad sepcialise") degree(p1) = 0 => "next pol" res := cons(p1,res) res
coefficientSet(pol) == res : List(ThePols) := [] for c in coefficients(pol) repeat ground?(c) => return(res) res := cons(c,res) res
SUBRES ==> SubResultantPackage(ThePols,RUP) discriminantSet(lpols) == res : List(ThePols) := [] for p in lpols repeat v := subresultantVector(p,differentiate(p))$SUBRES not(zero?(degree(v.0))) => return(error "Bad discriminant") d : ThePols := leadingCoefficient(v.0) -- d := discriminant p zero?(d) => return(error "Non Square Free polynomial") if not(ground? d) then res := cons(d,res) res
principalSubResultantSet(p,q) == if degree(p) < degree(q) then (p,q) := (q,p) if degree(p) = degree(q) then (p,q) := (q,pseudoRemainder(p, q)) v := subresultantVector(p,q)$SUBRES [coefficient(v.i,i) for i in 0..(((#v)-2)::N)]
resultantSet(lpols) == res : List(ThePols) := [] laux := lpols for p in lpols repeat laux := rest(laux) for q in laux repeat r : ThePols := first(principalSubResultantSet(p,q)) -- r := resultant(p,q) zero?(r) => return(error "Non relatively prime polynomials") if not(ground? r) then res := cons(r,res) res
projectionSet(lpols) == res : List(ThePols) := [] for p in lpols repeat c := content(p) ground?(c) => "next p" res := cons(c,res) lp1 := [primitivePart p for p in lpols] f : ((RUP,RUP) -> Boolean) := (x,y)+->(degree(x) <= degree(y)) lp1 := sort(f,lp1) lsqfrb := squareFreeBasis(lp1)$PACK1 lsqfrb := sort(f,lsqfrb) for p in lp1 repeat res := append(res,coefficientSet(p)) res := append(res,discriminantSet(lsqfrb)) append(res,resultantSet(lsqfrb))
spad
   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/4314612298553742433-25px004.spad
      using old system compiler.
   CAD abbreviates package CylindricalAlgebraicDecompositionPackage 
------------------------------------------------------------------------
   initializing NRLIB CAD for CylindricalAlgebraicDecompositionPackage 
   compiling into NRLIB CAD 
   compiling exported cylindricalDecomposition : List Polynomial TheField -> List Cell TheField
Time: 0.01 SEC.
compiling exported cylindricalDecomposition : (List Polynomial TheField,List Symbol) -> List Cell TheField Time: 0.02 SEC.
processing macro definition PACK1 ==> CylindricalAlgebraicDecompositionUtilities(Polynomial TheField,SparseUnivariatePolynomial Polynomial TheField) processing macro definition PACK2 ==> CylindricalAlgebraicDecompositionUtilities(TheField,SparseUnivariatePolynomial TheField) compiling exported specialise : (List Polynomial TheField,Cell TheField) -> List SparseUnivariatePolynomial TheField Time: 0.01 SEC.
compiling exported coefficientSet : SparseUnivariatePolynomial Polynomial TheField -> List Polynomial TheField Time: 0 SEC.
processing macro definition SUBRES ==> SubResultantPackage(Polynomial TheField,SparseUnivariatePolynomial Polynomial TheField) compiling exported discriminantSet : List SparseUnivariatePolynomial Polynomial TheField -> List Polynomial TheField Time: 0.02 SEC.
compiling exported principalSubResultantSet : (SparseUnivariatePolynomial Polynomial TheField,SparseUnivariatePolynomial Polynomial TheField) -> List Polynomial TheField Time: 0.01 SEC.
compiling exported resultantSet : List SparseUnivariatePolynomial Polynomial TheField -> List Polynomial TheField Time: 0.01 SEC.
compiling exported projectionSet : List SparseUnivariatePolynomial Polynomial TheField -> List Polynomial TheField Time: 0.01 SEC.
(time taken in buildFunctor: 0)
;;; *** |CylindricalAlgebraicDecompositionPackage| REDEFINED
;;; *** |CylindricalAlgebraicDecompositionPackage| REDEFINED Time: 0 SEC.
Warnings: [1] cylindricalDecomposition: lv has no value [2] specialise: res has no value [3] discriminantSet: res has no value [4] resultantSet: res has no value [5] projectionSet: res has no value
Cumulative Statistics for Constructor CylindricalAlgebraicDecompositionPackage Time: 0.09 seconds
finalizing NRLIB CAD Processing CylindricalAlgebraicDecompositionPackage for Browser database: --->-->CylindricalAlgebraicDecompositionPackage(constructor): Not documented!!!! --->-->CylindricalAlgebraicDecompositionPackage((cylindricalDecomposition ((List (Cell TheField)) (List (Polynomial TheField))))): Not documented!!!! --->-->CylindricalAlgebraicDecompositionPackage((cylindricalDecomposition ((List (Cell TheField)) (List (Polynomial TheField)) (List (Symbol))))): Not documented!!!! --->-->CylindricalAlgebraicDecompositionPackage((projectionSet ((List (Polynomial TheField)) (List (SparseUnivariatePolynomial (Polynomial TheField)))))): Not documented!!!! --->-->CylindricalAlgebraicDecompositionPackage((coefficientSet ((List (Polynomial TheField)) (SparseUnivariatePolynomial (Polynomial TheField))))): Not documented!!!! --->-->CylindricalAlgebraicDecompositionPackage((discriminantSet ((List (Polynomial TheField)) (List (SparseUnivariatePolynomial (Polynomial TheField)))))): Not documented!!!! --->-->CylindricalAlgebraicDecompositionPackage((resultantSet ((List (Polynomial TheField)) (List (SparseUnivariatePolynomial (Polynomial TheField)))))): Not documented!!!! --->-->CylindricalAlgebraicDecompositionPackage((principalSubResultantSet ((List (Polynomial TheField)) (SparseUnivariatePolynomial (Polynomial TheField)) (SparseUnivariatePolynomial (Polynomial TheField))))): Not documented!!!! --->-->CylindricalAlgebraicDecompositionPackage((specialise ((List (SparseUnivariatePolynomial TheField)) (List (Polynomial TheField)) (Cell TheField)))): Not documented!!!! --->-->CylindricalAlgebraicDecompositionPackage(): Missing Description ; compiling file "/var/aw/var/LatexWiki/CAD.NRLIB/CAD.lsp" (written 11 APR 2014 06:34:42 PM):
; /var/aw/var/LatexWiki/CAD.NRLIB/CAD.fasl written ; compilation finished in 0:00:00.059 ------------------------------------------------------------------------ CylindricalAlgebraicDecompositionPackage is now explicitly exposed in frame initial CylindricalAlgebraicDecompositionPackage will be automatically loaded when needed from /var/aw/var/LatexWiki/CAD.NRLIB/CAD

Test Input

fricas
)lib SCELL CELL CAD
SimpleCell is already explicitly exposed in frame initial SimpleCell will be automatically loaded when needed from /var/aw/var/LatexWiki/SCELL.NRLIB/SCELL Cell is already explicitly exposed in frame initial Cell will be automatically loaded when needed from /var/aw/var/LatexWiki/CELL.NRLIB/CELL CylindricalAlgebraicDecompositionPackage is already explicitly exposed in frame initial CylindricalAlgebraicDecompositionPackage will be automatically loaded when needed from /var/aw/var/LatexWiki/CAD.NRLIB/CAD Ran := RECLOS(FRAC INT)

\label{eq1}\hbox{\axiomType{RealClosure}\ } (\hbox{\axiomType{Fraction}\ } (\hbox{\axiomType{Integer}\ }))(1)
Type: Type
fricas
Cad := CAD(Ran)

\label{eq2}\hbox{\axiomType{CylindricalAlgebraicDecompositionPackage}\ } (\hbox{\axiomType{RealClosure}\ } (\hbox{\axiomType{Fraction}\ } (\hbox{\axiomType{Integer}\ })))(2)
Type: Type
fricas
p1 : POLY(Ran) := x^2+y^2-1

\label{eq3}{{y}^{2}}+{{x}^{2}}- 1(3)
Type: Polynomial(RealClosure?(Fraction(Integer)))
fricas
p2 : POLY(Ran) := y-x^2

\label{eq4}y -{{x}^{2}}(4)
Type: Polynomial(RealClosure?(Fraction(Integer)))
fricas
lpols : List(POLY(Ran)) := [p1,p2]

\label{eq5}\left[{{{y}^{2}}+{{x}^{2}}- 1}, \:{y -{{x}^{2}}}\right](5)
Type: List(Polynomial(RealClosure?(Fraction(Integer))))
fricas
cad := cylindricalDecomposition(lpols)$Cad

\label{eq6}\begin{array}{@{}l}
\displaystyle
\left[{\left({\left\{{y = - 5}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = - 2}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 4}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = - 2}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 5}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = - 2}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = - 2}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = - 1}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 0}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = - 1}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={1 \over 2}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = - 1}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 1}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = - 1}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 2}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = - 1}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = -{{113}\over{64}}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = -{7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={\%A 5}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = -{7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 0}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = -{7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={\%A 6}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = -{7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={{339}\over{512}}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = -{7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={{49}\over{64}}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = -{7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={{113}\over{128}}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = -{7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={-{{\%A 1}^{2}}- 1}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x ={\%A 1}}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = -{{\%A 1}^{2}}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x ={\%A 1}}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 0}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x ={\%A 1}}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={{\%A 1}^{2}}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x ={\%A 1}}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={{{\%A 1}^{2}}+ 1}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x ={\%A 1}}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = - 2}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = 0}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={\%A 7}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = 0}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = -{1 \over 2}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = 0}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 0}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = 0}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={1 \over 2}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = 0}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={\%A 8}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = 0}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 2}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = 0}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={-{{\%A 2}^{2}}- 1}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x ={\%A 2}}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = -{{\%A 2}^{2}}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x ={\%A 2}}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 0}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x ={\%A 2}}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={{\%A 2}^{2}}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x ={\%A 2}}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={{{\%A 2}^{2}}+ 1}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x ={\%A 2}}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = -{{113}\over{64}}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x ={7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={\%A 9}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x ={7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 0}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x ={7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={\%A{10}}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x ={7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={{339}\over{512}}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x ={7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={{49}\over{64}}}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x ={7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={{113}\over{128}}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x ={7 \over 8}}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = - 2}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = 1}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 0}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = 1}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y ={1 \over 2}}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = 1}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 1}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = 1}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 2}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = 1}, \:  \mbox{\rm false} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = - 5}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = 2}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 4}, \:  \mbox{\rm false} \right\}}, \:{\left\{{x = 2}, \:  \mbox{\rm true} \right\}}\right)}, \: \right.
\
\
\displaystyle
\left.{\left({\left\{{y = 5}, \:  \mbox{\rm true} \right\}}, \:{\left\{{x = 2}, \:  \mbox{\rm true} \right\}}\right)}\right] (6)
Type: List(Cell(RealClosure?(Fraction(Integer))))
fricas
precision(30)

\label{eq7}68(7)
Type: PositiveInteger?
fricas
ls := [ samplePoint cell for cell in cad]

\label{eq8}\begin{array}{@{}l}
\displaystyle
\left[{\left[ - 5, \: - 2 \right]}, \:{\left[ 4, \: - 2 \right]}, \:{\left[ 5, \: - 2 \right]}, \:{\left[ - 2, \: - 1 \right]}, \:{\left[ 0, \: - 1 \right]}, \:{\left[{1 \over 2}, \: - 1 \right]}, \: \right.
\
\
\displaystyle
\left.{\left[ 1, \: - 1 \right]}, \:{\left[ 2, \: - 1 \right]}, \:{\left[ -{{113}\over{64}}, \: -{7 \over 8}\right]}, \:{\left[{\%A 5}, \: -{7 \over 8}\right]}, \:{\left[ 0, \: -{7 \over 8}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{\%A 6}, \: -{7 \over 8}\right]}, \:{\left[{{339}\over{5
12}}, \: -{7 \over 8}\right]}, \:{\left[{{49}\over{64}}, \: -{7 \over 8}\right]}, \:{\left[{{113}\over{128}}, \: -{7 \over 8}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{-{{\%A 1}^{2}}- 1}, \:{\%A 1}\right]}, \:{\left[ -{{\%A 1}^{2}}, \:{\%A 1}\right]}, \:{\left[ 0, \:{\%A 1}\right]}, \:{\left[{{\%A 1}^{2}}, \:{\%A 1}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{{{\%A 1}^{2}}+ 1}, \:{\%A 1}\right]}, \:{\left[ - 2, \: 0 \right]}, \:{\left[{\%A 7}, \: 0 \right]}, \:{\left[ -{1 \over 2}, \: 0 \right]}, \:{\left[ 0, \: 0 \right]}, \:{\left[{1 \over 2}, \: 0 \right]}, \: \right.
\
\
\displaystyle
\left.{\left[{\%A 8}, \: 0 \right]}, \:{\left[ 2, \: 0 \right]}, \:{\left[{-{{\%A 2}^{2}}- 1}, \:{\%A 2}\right]}, \:{\left[ -{{\%A 2}^{2}}, \:{\%A 2}\right]}, \:{\left[ 0, \:{\%A 2}\right]}, \right.
\
\
\displaystyle
\left.\:{\left[{{\%A 2}^{2}}, \:{\%A 2}\right]}, \:{\left[{{{\%A 2}^{2}}+ 1}, \:{\%A 2}\right]}, \:{\left[ -{{113}\over{64}}, \:{7 \over 8}\right]}, \:{\left[{\%A 9}, \:{7 \over 8}\right]}, \:{\left[ 0, \:{7 \over 8}\right]}, \right.
\
\
\displaystyle
\left.\:{\left[{\%A{10}}, \:{7 \over 8}\right]}, \:{\left[{{3
39}\over{512}}, \:{7 \over 8}\right]}, \:{\left[{{49}\over{64}}, \:{7 \over 8}\right]}, \:{\left[{{113}\over{128}}, \:{7 \over 8}\right]}, \:{\left[ - 2, \: 1 \right]}, \:{\left[ 0, \: 1 \right]}, \: \right.
\
\
\displaystyle
\left.{\left[{1 \over 2}, \: 1 \right]}, \:{\left[ 1, \: 1 \right]}, \:{\left[ 2, \: 1 \right]}, \:{\left[ - 5, \: 2 \right]}, \:{\left[ 4, \: 2 \right]}, \:{\left[ 5, \: 2 \right]}\right] 
(8)
Type: List(List(RealClosure?(Fraction(Integer))))
fricas
lf := [ [relativeApprox(coord,2^(-precision()))::Float for coord in point] for point in ls]

\label{eq9}\begin{array}{@{}l}
\displaystyle
\left[{\left[ -{5.0}, \: -{2.0}\right]}, \:{\left[{4.0}, \: -{2.0}\right]}, \:{\left[{5.0}, \: -{2.0}\right]}, \:{\left[ -{2.0}, \: -{1.0}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.0}, \: -{1.0}\right]}, \:{\left[{0.5}, \: -{1.0}\right]}, \:{\left[{1.0}, \: -{1.0}\right]}, \:{\left[{2.0}, \: -{1.0}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{1.765625}, \: -{0.875}\right]}, \:{\left[ -{0.4
8412292}, \: -{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.0}, \: -{0.875}\right]}, \:{\left[{0.48412292}, \: -{0.875}\right]}, \:{\left[{0.66210938}, \: -{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.765625}, \: -{0.875}\right]}, \:{\left[{0.882
8125}, \: -{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{1.618034}, \: -{0.78615138}\right]}, \:{\left[ -{0.61803399}, \: -{0.78615138}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.0}, \: -{0.78615138}\right]}, \:{\left[{0.618
03399}, \: -{0.78615138}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{1.618034}, \: -{0.78615138}\right]}, \:{\left[ -{2.0}, \:{0.0}\right]}, \:{\left[ -{1.0}, \:{0.0}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{0.5}, \:{0.0}\right]}, \:{\left[{0.0}, \:{0.0}\right]}, \:{\left[{0.5}, \:{0.0}\right]}, \:{\left[{1.0}, \:{0.0}\right]}, \:{\left[{2.0}, \:{0.0}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{1.618034}, \:{0.78615138}\right]}, \:{\left[ -{0.61803399}, \:{0.78615138}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.0}, \:{0.78615138}\right]}, \:{\left[{0.61803
399}, \:{0.78615138}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{1.618034}, \:{0.78615138}\right]}, \:{\left[ -{1.7
65625}, \:{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{0.48412292}, \:{0.875}\right]}, \:{\left[{0.0}, \:{0.875}\right]}, \:{\left[{0.48412292}, \:{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.66210938}, \:{0.875}\right]}, \:{\left[{0.765
625}, \:{0.875}\right]}, \:{\left[{0.8828125}, \:{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{2.0}, \:{1.0}\right]}, \:{\left[{0.0}, \:{1.0}\right]}, \:{\left[{0.5}, \:{1.0}\right]}, \:{\left[{1.0}, \:{1.0}\right]}, \:{\left[{2.0}, \:{1.0}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{5.0}, \:{2.0}\right]}, \:{\left[{4.0}, \:{2.0}\right]}, \:{\left[{5.0}, \:{2.0}\right]}\right] 
(9)
Type: List(List(Float))
fricas
lp := [ point(term::List(DoubleFloat))$Point(DoubleFloat) for term in lf ]

\label{eq10}\begin{array}{@{}l}
\displaystyle
\left[{\left[ -{5.0}, \: -{2.0}\right]}, \:{\left[{4.0}, \: -{2.0}\right]}, \:{\left[{5.0}, \: -{2.0}\right]}, \:{\left[ -{2.0}, \: -{1.0}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.0}, \: -{1.0}\right]}, \:{\left[{0.5}, \: -{1.0}\right]}, \:{\left[{1.0}, \: -{1.0}\right]}, \:{\left[{2.0}, \: -{1.0}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{1.765625}, \: -{0.875}\right]}, \:{\left[ -{0.4
8412291845306754}, \: -{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.0}, \: -{0.875}\right]}, \:{\left[{0.48412291
845306754}, \: -{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.662109375}, \: -{0.875}\right]}, \:{\left[{0.7
65625}, \: -{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.8828125}, \: -{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{1.6180339884012938}, \: -{0.7861513774842024}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{0.6180339893326163}, \: -{0.7861513774842024}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.0}, \: -{0.7861513774842024}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.6180339893326163}, \: -{0.7861513774842024}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{1.6180339884012938}, \: -{0.7861513774842024}\right]}, \:{\left[ -{2.0}, \:{0.0}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{1.0}, \:{0.0}\right]}, \:{\left[ -{0.5}, \:{0.0}\right]}, \:{\left[{0.0}, \:{0.0}\right]}, \:{\left[{0.5}, \:{0.0}\right]}, \:{\left[{1.0}, \:{0.0}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{2.0}, \:{0.0}\right]}, \:{\left[ -{1.6180339884
012938}, \:{0.7861513774842024}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{0.6180339893326163}, \:{0.7861513774842024}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.0}, \:{0.7861513774842024}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.6180339893326163}, \:{0.7861513774842024}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{1.6180339884012938}, \:{0.7861513774842024}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{1.765625}, \:{0.875}\right]}, \:{\left[ -{0.4
8412291845306754}, \:{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.0}, \:{0.875}\right]}, \:{\left[{0.4841229184
5306754}, \:{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[{0.662109375}, \:{0.875}\right]}, \:{\left[{0.76
5625}, \:{0.875}\right]}, \:{\left[{0.8828125}, \:{0.875}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{2.0}, \:{1.0}\right]}, \:{\left[{0.0}, \:{1.0}\right]}, \:{\left[{0.5}, \:{1.0}\right]}, \:{\left[{1.0}, \:{1.0}\right]}, \:{\left[{2.0}, \:{1.0}\right]}, \: \right.
\
\
\displaystyle
\left.{\left[ -{5.0}, \:{2.0}\right]}, \:{\left[{4.0}, \:{2.0}\right]}, \:{\left[{5.0}, \:{2.0}\right]}\right] 
(10)
Type: List(Point(DoubleFloat?))
fricas
[ sign(eval(p1,variables(p1),samplePoint(cell))::Ran) for cell in cad ]

\label{eq11}\begin{array}{@{}l}
\displaystyle
\left[ 1, \: 1, \: 1, \: 1, \: 0, \: 1, \: 1, \: 1, \: 1, \: 0, \: - 1, \: 0, \: 1, \: 1, \: 1, \: 1, \: 0, \: - 1, \: 0, \: 1, \: 1, \: 0, \: - 1, \right.
\
\
\displaystyle
\left.\: - 1, \: - 1, \: 0, \: 1, \: 1, \: 0, \: - 1, \: 0, \: 1, \: 1, \: 0, \: - 1, \: 0, \: 1, \: 1, \: 1, \: 1, \: 0, \: 1, \: 1, \: 1, \right.
\
\
\displaystyle
\left.\: 1, \: 1, \: 1 \right] 
(11)
Type: List(Integer)