PolynomialSetUtilitiesPackage(R, E, V, P)¶

triset.spad line 580 [edit on github]

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 PolynomialFactorizationExplicit and R has CharacteristicZero: 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 PolynomialFactorizationExplicit and R has CharacteristicZero: 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 PolynomialFactorizationExplicit and R has CharacteristicZero: 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 newlpwhere 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 newlpwhere 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.