# PolynomialSetUtilitiesPackage(R, E, V, P)ΒΆ

triset.spad line 580 [edit on github]

V: OrderedSet

P: RecursivePolynomialCategory(R, E, V)

This package provides modest routines for polynomial system solving. The aim of many of the operations of this package is to remove certain factors in some polynomials in order to avoid unnecessary computations in algorithms involving splitting techniques by partial factorization.

- bivariate?: P -> Boolean
`bivariate?(p)`

returns`true`

iff`p`

involves two and only two variables.

- bivariatePolynomials: List P -> Record(goodPols: List P, badPols: List P)
`bivariatePolynomials(lp)`

returns`bps, nbps`

where`bps`

is a list of the bivariate polynomials, and`nbps`

are the other ones.

- certainlySubVariety?: (List P, List P) -> Boolean
`certainlySubVariety?(newlp, lp)`

returns`true`

iff for every`p`

in`lp`

the remainder of`p`

by`newlp`

using the division algorithm of Groebner techniques is zero.

- crushedSet: List P -> List P
`crushedSet(lp)`

returns`lq`

such that`lp`

and and`lq`

generate the same ideal and no rough basic sets reduce (in the sense of Groebner bases) the other polynomials in`lq`

.

- interReduce: List P -> List P
`interReduce(lp)`

returns`lq`

such that`lp`

and`lq`

generate the same ideal and no polynomial in`lq`

is reducible by the others in the sense of Groebner bases. Since no assumptions are required the result may depend on the ordering the reductions are performed.

- irreducibleFactors: List P -> List P if R has CharacteristicZero and R has PolynomialFactorizationExplicit
`irreducibleFactors(lp)`

returns`lf`

such that if`lp = [p1, ..., pn]`

and`lf = [f1, ..., fm]`

then`p1*p2*...*pn=0`

means`f1*f2*...*fm=0`

, and the`fi`

are irreducible over`R`

and are pairwise distinct.

- lazyIrreducibleFactors: List P -> List P if R has CharacteristicZero and R has PolynomialFactorizationExplicit
`lazyIrreducibleFactors(lp)`

returns`lf`

such that if`lp = [p1, ..., pn]`

and`lf = [f1, ..., fm]`

then`p1*p2*...*pn=0`

means`f1*f2*...*fm=0`

, and the`fi`

are irreducible over`R`

and are pairwise distinct. The algorithm tries to avoid factorization into irreducible factors as far as possible and makes previously use of`gcd`

techniques over`R`

.

- linear?: P -> Boolean
`linear?(p)`

returns`true`

iff`p`

does not lie in the base ring`R`

and has main degree`1`

.

- linearPolynomials: List P -> Record(goodPols: List P, badPols: List P)
`linearPolynomials(lp)`

returns`lps, nlps`

where`lps`

is a list of the linear polynomials in`lp`

, and`nlps`

are the other ones.

- possiblyNewVariety?: (List P, List List P) -> Boolean
`possiblyNewVariety?(newlp, llp)`

returns`true`

iff for every`lp`

in`llp`

certainlySubVariety?(`newlp`

,`lp`

) does not hold.

- probablyZeroDim?: List P -> Boolean
`probablyZeroDim?(lp)`

returns`true`

iff the number of polynomials in`lp`

is not smaller than the number of variables occurring in these polynomials.

- quasiMonicPolynomials: List P -> Record(goodPols: List P, badPols: List P)
`quasiMonicPolynomials(lp)`

returns`qmps, nqmps`

where`qmps`

is a list of the quasi-monic polynomials in`lp`

and`nqmps`

are the other ones.

- removeIrreducibleRedundantFactors: (List P, List P) -> List P if R has CharacteristicZero and R has PolynomialFactorizationExplicit
`removeIrreducibleRedundantFactors(lp, lq)`

returns the same as`irreducibleFactors(concat(lp, lq))`

assuming that`irreducibleFactors(lp)`

returns`lp`

up to replacing some polynomial`pj`

in`lp`

by some polynomial`qj`

associated to`pj`

.

- removeRedundantFactors: (List P, List P) -> List P
`removeRedundantFactors(lp, lq)`

returns the same as`removeRedundantFactors(concat(lp, lq))`

assuming that`removeRedundantFactors(lp)`

returns`lp`

up to replacing some polynomial`pj`

in`lp`

by some polynomial`qj`

associated to`pj`

.

- removeRedundantFactors: (List P, List P, List P -> List P) -> List P
`removeRedundantFactors(lp, lq, remOp)`

returns the same as`concat(remOp(removeRoughlyRedundantFactorsInPols(lp, lq)), lq)`

assuming that`remOp(lq)`

returns`lq`

up to similarity.

- removeRedundantFactors: (List P, P) -> List P
`removeRedundantFactors(lp, q)`

returns the same as`removeRedundantFactors(cons(q, lp))`

assuming that`removeRedundantFactors(lp)`

returns`lp`

up to replacing some polynomial`pj`

in`lp`

by some some polynomial`qj`

associated to`pj`

.

- removeRedundantFactors: (P, P) -> List P
`removeRedundantFactors(p, q)`

returns the same as`removeRedundantFactors([p, q])`

- removeRedundantFactors: List P -> List P
`removeRedundantFactors(lp)`

returns`lq`

such that if`lp = [p1, ..., pn]`

and`lq = [q1, ..., qm]`

then the product`p1*p2*...*pn`

vanishes iff the product`q1*q2*...*qm`

vanishes, and the product of degrees of the`qi`

is not greater than the one of the`pj`

, and no polynomial in`lq`

divides another polynomial in`lq`

. In particular, polynomials lying in the base ring`R`

are removed. Moreover,`lq`

is sorted`w`

.`r`

.`t`

`infRittWu?`

. Furthermore, if`R`

is`gcd`

-domain, the polynomials in`lq`

are pairwise without common non trivial factor.

- removeRedundantFactorsInContents: (List P, List P) -> List P if R has GcdDomain
`removeRedundantFactorsInContents(lp, lf)`

returns`newlp`

where`newlp`

is obtained from`lp`

by removing in the content of every polynomial of`lp`

any non trivial factor of any polynomial`f`

in`lf`

. Moreover, squares over`R`

are first removed in the content of every polynomial of`lp`

.

- removeRedundantFactorsInPols: (List P, List P) -> List P if R has GcdDomain
`removeRedundantFactorsInPols(lp, lf)`

returns`newlp`

where`newlp`

is obtained from`lp`

by removing in every polynomial`p`

of`lp`

any non trivial factor of any polynomial`f`

in`lf`

. Moreover, squares over`R`

are first removed in every polynomial`lp`

.

- removeRoughlyRedundantFactorsInContents: (List P, List P) -> List P if R has GcdDomain
`removeRoughlyRedundantFactorsInContents(lp, lf)`

returns`newlp`

where`newlp`

is obtained from`lp`

by removing in the content of every polynomial of`lp`

any occurence of a polynomial`f`

in`lf`

. Moreover, squares over`R`

are first removed in the content of every polynomial of`lp`

.

- removeRoughlyRedundantFactorsInPol: (P, List P) -> P
`removeRoughlyRedundantFactorsInPol(p, lf)`

returns the same as removeRoughlyRedundantFactorsInPols([`p`

],`lf`

,`true`

)

- removeRoughlyRedundantFactorsInPols: (List P, List P) -> List P
`removeRoughlyRedundantFactorsInPols(lp, lf)`

returns`newlp`

where`newlp`

is obtained from`lp`

by removing in every polynomial`p`

of`lp`

any occurrence of a polynomial`f`

in`lf`

. This may involve a lot of exact-quotients computations.

- removeRoughlyRedundantFactorsInPols: (List P, List P, Boolean) -> List P
`removeRoughlyRedundantFactorsInPols(lp, lf, opt)`

returns the same as`removeRoughlyRedundantFactorsInPols(lp, lf)`

if`opt`

is`false`

and if the previous operation does not return any non null and constant polynomial, else return`[1]`

.

- removeSquaresIfCan: List P -> List P
`removeSquaresIfCan(lp)`

returns`removeDuplicates [squareFreePart(p)\$P for p in lp]`

if`R`

is`gcd`

-domain else returns`lp`

.

- rewriteIdealWithQuasiMonicGenerators: (List P, (P, P) -> Boolean, (P, P) -> P) -> List P
`rewriteIdealWithQuasiMonicGenerators(lp, redOp?, redOp)`

returns`lq`

where`lq`

and`lp`

generate the same ideal in`R^(-1) P`

and`lq`

has rank not higher than the one of`lp`

. Moreover,`lq`

is computed by reducing`lp`

`w`

.`r`

.`t`

. some basic set of the ideal generated by the quasi-monic polynomials in`lp`

.

- rewriteSetByReducingWithParticularGenerators: (List P, P -> Boolean, (P, P) -> Boolean, (P, P) -> P) -> List P
`rewriteSetByReducingWithParticularGenerators(lp, pred?, redOp?, redOp)`

returns`lq`

where`lq`

is computed by the following algorithm. Chose a basic set`w`

.`r`

.`t`

. the reduction-test`redOp?`

among the polynomials satisfying property`pred?`

, if it is empty then leave, else reduce the other polynomials by this basic set`w`

.`r`

.`t`

. the reduction-operation`redOp`

. Repeat while another basic set with smaller rank can be computed. See code. If`pred?`

is`quasiMonic?`

the ideal is unchanged.

- roughBasicSet: List P -> Union(Record(bas: GeneralTriangularSet(R, E, V, P), top: List P), failed)
`roughBasicSet(lp)`

returns the smallest (with Ritt-Wu ordering) triangular set contained in`lp`

.

- selectAndPolynomials: (List(P -> Boolean), List P) -> Record(goodPols: List P, badPols: List P)
`selectAndPolynomials(lpred?, ps)`

returns`gps, bps`

where`gps`

is a list of the polynomial`p`

in`ps`

such that`pred?(p)`

holds for every`pred?`

in`lpred?`

and`bps`

are the other ones.

- selectOrPolynomials: (List(P -> Boolean), List P) -> Record(goodPols: List P, badPols: List P)
`selectOrPolynomials(lpred?, ps)`

returns`gps, bps`

where`gps`

is a list of the polynomial`p`

in`ps`

such that`pred?(p)`

holds for some`pred?`

in`lpred?`

and`bps`

are the other ones.

- selectPolynomials: (P -> Boolean, List P) -> Record(goodPols: List P, badPols: List P)
`selectPolynomials(pred?, ps)`

returns`gps, bps`

where`gps`

is a list of the polynomial`p`

in`ps`

such that`pred?(p)`

holds and`bps`

are the other ones.

- squareFreeFactors: P -> List P if R has GcdDomain
`squareFreeFactors(p)`

returns the square-free factors of`p`

over`R`

- univariate?: P -> Boolean
`univariate?(p)`

returns`true`

iff`p`

involves one and only one variable.

- univariatePolynomials: List P -> Record(goodPols: List P, badPols: List P)
`univariatePolynomials(lp)`

returns`ups, nups`

where`ups`

is a list of the univariate polynomials, and`nups`

are the other ones.

- univariatePolynomialsGcds: (List P, Boolean) -> List P if R has GcdDomain
`univariatePolynomialsGcds(lp, opt)`

returns the same as`univariatePolynomialsGcds(lp)`

if`opt`

is`false`

and if the previous operation does not return any non null and constant polynomial, else return`[1]`

.

- univariatePolynomialsGcds: List P -> List P if R has GcdDomain
`univariatePolynomialsGcds(lp)`

returns`lg`

where`lg`

is a list of the gcds of every pair in`lp`

of univariate polynomials in the same main variable.

- unprotectedRemoveRedundantFactors: (P, P) -> List P
`unprotectedRemoveRedundantFactors(p, q)`

returns the same as`removeRedundantFactors(p, q)`

but does assume that neither`p`

nor`q`

lie in the base ring`R`

and assumes that`infRittWu?(p, q)`

holds. Moreover, if`R`

is`gcd`

-domain, then`p`

and`q`

are assumed to be square free.