\documentclass{article} \usepackage{open-axiom} \begin{document} \title{\$SPAD/src/algebra allfact.spad} \author{Patrizia Gianni} \maketitle \begin{abstract} \end{abstract} \eject \tableofcontents \eject \section{package MRATFAC MRationalFactorize} <>= )abbrev package MRATFAC MRationalFactorize ++ Author: P. Gianni ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: MultivariateFactorize ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: MRationalFactorize contains the factor function for multivariate ++ polynomials over the quotient field of a ring R such that the package ++ MultivariateFactorize can factor multivariate polynomials over R. MRationalFactorize(E,OV,R,P) : C == T where E : OrderedAbelianMonoidSup OV : OrderedSet R : Join(EuclideanDomain, CharacteristicZero) -- with factor over R[x] FR ==> Fraction R P : PolynomialCategory(FR,E,OV) MPR ==> SparseMultivariatePolynomial(R,OV) SUP ==> SparseUnivariatePolynomial C == with factor : P -> Factored P ++ factor(p) factors the multivariate polynomial p with coefficients ++ which are fractions of elements of R. T == add IE ==> IndexedExponents OV PCLFRR ==> PolynomialCategoryLifting(E,OV,FR,P,MPR) PCLRFR ==> PolynomialCategoryLifting(IE,OV,R,MPR,P) MFACT ==> MultivariateFactorize(OV,IE,R,MPR) UPCF2 ==> UnivariatePolynomialCategoryFunctions2 numer1(c:FR): MPR == (numer c) :: MPR numer2(pol:P) : MPR == map(coerce,numer1,pol)$PCLFRR coerce1(d:R) : P == (d::FR)::P coerce2(pp:MPR) :P == map(coerce,coerce1,pp)$PCLRFR factor(p:P) : Factored P == pden:R:=lcm([denom c for c in coefficients p]) pol :P:= (pden::FR)*p ipol:MPR:= map(coerce,numer1,pol)$PCLFRR ffact:=(factor ipol)$MFACT (1/pden)*map(coerce,coerce1,(unit ffact))$PCLRFR * _*/[primeFactor(map(coerce,coerce1,u.factor)$PCLRFR, u.exponent) for u in factors ffact] @ \section{package MPRFF MPolyCatRationalFunctionFactorizer} <>= )abbrev package MPRFF MPolyCatRationalFunctionFactorizer ++ Author: P. Gianni ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ This package exports a factor operation for multivariate polynomials ++ with coefficients which are rational functions over ++ some ring R over which we can factor. It is used internally by packages ++ such as primary decomposition which need to work with polynomials ++ with rational function coefficients, i.e. themselves fractions of ++ polynomials. MPolyCatRationalFunctionFactorizer(E,OV,R,PRF) : C == T where R : IntegralDomain F ==> Fraction Polynomial R RN ==> Fraction Integer E : OrderedAbelianMonoidSup OV : OrderedSet with convert : % -> Symbol ++ convert(x) converts x to a symbol PRF : PolynomialCategory(F,E,OV) NNI ==> NonNegativeInteger P ==> Polynomial R ISE ==> IndexedExponents SE SE ==> Symbol UP ==> SparseUnivariatePolynomial P UF ==> SparseUnivariatePolynomial F UPRF ==> SparseUnivariatePolynomial PRF QuoForm ==> Record(sup:P,inf:P) C == with totalfract : PRF -> QuoForm ++ totalfract(prf) takes a polynomial whose coefficients are ++ themselves fractions of polynomials and returns a record ++ containing the numerator and denominator resulting from ++ putting prf over a common denominator. pushdown : (PRF,OV) -> PRF ++ pushdown(prf,var) pushes all top level occurences of the ++ variable var into the coefficient domain for the polynomial prf. pushdterm : (UPRF,OV) -> PRF ++ pushdterm(monom,var) pushes all top level occurences of the ++ variable var into the coefficient domain for the monomial monom. pushup : (PRF,OV) -> PRF ++ pushup(prf,var) raises all occurences of the ++ variable var in the coefficients of the polynomial prf ++ back to the polynomial level. pushucoef : (UP,OV) -> PRF ++ pushucoef(upoly,var) converts the anonymous univariate ++ polynomial upoly to a polynomial in var over rational functions. pushuconst : (F,OV) -> PRF ++ pushuconst(r,var) takes a rational function and raises ++ all occurances of the variable var to the polynomial level. factor : PRF -> Factored PRF ++ factor(prf) factors a polynomial with rational function ++ coefficients. --- Local Functions ---- T == add ---- factorization of p ---- factor(p:PRF) : Factored PRF == truelist:List OV :=variables p tp:=totalfract(p) nump:P:= tp.sup denp:F:=inv(tp.inf ::F) ffact : List(Record(irr:PRF,pow:Integer)) flist:Factored P if R is Fraction Integer then flist:= ((factor nump)$MRationalFactorize(ISE,SE,Integer,P)) pretend (Factored P) else if R has FiniteFieldCategory then flist:= ((factor nump)$MultFiniteFactorize(SE,ISE,R,P)) pretend (Factored P) else if R has Field then error "not done yet" else if R has CharacteristicZero then flist:= ((factor nump)$MultivariateFactorize(SE,ISE,R,P)) pretend (Factored P) else error "can't happen" ffact:=[[u.factor::F::PRF,u.exponent] for u in factors flist] fcont:=(unit flist)::F::PRF for x in truelist repeat fcont:=pushup(fcont,x) ffact:=[[pushup(ff.irr,x),ff.pow] for ff in ffact] (denp*fcont)*(_*/[primeFactor(ff.irr,ff.pow) for ff in ffact]) -- the following functions are used to "push" x in the coefficient ring - ---- push x in the coefficient domain for a polynomial ---- pushdown(g:PRF,x:OV) : PRF == ground? g => g rf:PRF:=0$PRF ug:=univariate(g,x) while not zero? ug repeat rf:=rf+pushdterm(ug,x) ug := reductum ug rf ---- push x in the coefficient domain for a term ---- pushdterm(t:UPRF,x:OV):PRF == n:=degree(t) cf:=monomial(1,convert x,n)$P :: F cf * leadingCoefficient t ---- push back the variable ---- pushup(f:PRF,x:OV) :PRF == ground? f => pushuconst(retract f,x) v:=mainVariable(f)::OV g:=univariate(f,v) multivariate(map(pushup(#1,x),g),v) ---- push x back from the coefficient domain ---- pushuconst(r:F,x:OV):PRF == xs:SE:=convert x positive? degree(denom r,xs) => error "bad polynomial form" inv((denom r)::F)*pushucoef(univariate(numer r,xs),x) pushucoef(c:UP,x:OV):PRF == c = 0 => 0 monomial((leadingCoefficient c)::F::PRF,x,degree c) + pushucoef(reductum c,x) ---- write p with a common denominator ---- totalfract(p:PRF) : QuoForm == p=0 => [0$P,1$P]$QuoForm for x in variables p repeat p:=pushdown(p,x) g:F:=retract p [numer g,denom g]$QuoForm @ \section{package MPCPF MPolyCatPolyFactorizer} <>= )abbrev package MPCPF MPolyCatPolyFactorizer ++ Author: P. Gianni ++ Date Created: ++ Date Last Updated: March 1995 ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ This package exports a factor operation for multivariate polynomials ++ with coefficients which are polynomials over ++ some ring R over which we can factor. It is used internally by packages ++ such as the solve package which need to work with polynomials in a specific ++ set of variables with coefficients which are polynomials in all the other ++ variables. MPolyCatPolyFactorizer(E,OV,R,PPR) : C == T where R : EuclideanDomain E : OrderedAbelianMonoidSup -- following type is required by PushVariables OV : OrderedSet with convert : % -> Symbol ++ convert(x) converts x to a symbol variable: Symbol -> Union(%, "failed") ++ variable(s) makes an element from symbol s or fails. PR ==> Polynomial R PPR : PolynomialCategory(PR,E,OV) NNI ==> NonNegativeInteger ISY ==> IndexedExponents Symbol SE ==> Symbol UP ==> SparseUnivariatePolynomial PR UPPR ==> SparseUnivariatePolynomial PPR C == with factor : PPR -> Factored PPR ++ factor(p) factors a polynomial with polynomial ++ coefficients. --- Local Functions ---- T == add import PushVariables(R,E,OV,PPR) ---- factorization of p ---- factor(p:PPR) : Factored PPR == ground? p => nilFactor(p,1) c := content p p := (p exquo c)::PPR vars:List OV :=variables p g:PR:=retract pushdown(p, vars) flist := factor(g)$GeneralizedMultivariateFactorize(Symbol,ISY,R,R,PR) ffact : List(Record(irr:PPR,pow:Integer)) ffact:=[[pushup(u.factor::PPR,vars),u.exponent] for u in factors flist] fcont:=(unit flist)::PPR nilFactor(c*fcont,1)*(_*/[primeFactor(ff.irr,ff.pow) for ff in ffact]) @ \section{package GENMFACT GeneralizedMultivariateFactorize} <>= )abbrev package GENMFACT GeneralizedMultivariateFactorize ++ Author: P. Gianni ++ Date Created: 1983 ++ Date Last Updated: Sept. 1990 ++ Basic Functions: ++ Related Constructors: MultFiniteFactorize, AlgebraicMultFact, MultivariateFactorize ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ This is the top level package for doing multivariate factorization ++ over basic domains like \spadtype{Integer} or \spadtype{Fraction Integer}. GeneralizedMultivariateFactorize(OV,E,S,R,P) : C == T where R : IntegralDomain -- with factor on R[x] S : IntegralDomain OV : OrderedSet with convert : % -> Symbol ++ convert(x) converts x to a symbol variable: Symbol -> Union(%, "failed") ++ variable(s) makes an element from symbol s or fails. E : OrderedAbelianMonoidSup P : PolynomialCategory(R,E,OV) C == with factor : P -> Factored P ++ factor(p) factors the multivariate polynomial p over its coefficient ++ domain T == add factor(p:P) : Factored P == R has FiniteFieldCategory => factor(p)$MultFiniteFactorize(OV,E,R,P) R is Polynomial(S) and S has EuclideanDomain => factor(p)$MPolyCatPolyFactorizer(E,OV,S,P) R is Fraction(S) and S has CharacteristicZero and S has EuclideanDomain => factor(p)$MRationalFactorize(E,OV,S,P) R is Fraction Polynomial S => factor(p)$MPolyCatRationalFunctionFactorizer(E,OV,S,P) R has CharacteristicZero and R has EuclideanDomain => factor(p)$MultivariateFactorize(OV,E,R,P) squareFree p @ \section{package RFFACTOR RationalFunctionFactorizer} <>= )abbrev package RFFACTOR RationalFunctionFactorizer ++ Author: P. Gianni ++ Date Created: ++ Date Last Updated: March 1995 ++ Basic Functions: ++ Related Constructors: Fraction, Polynomial ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ \spadtype{RationalFunctionFactorizer} contains the factor function ++ (called factorFraction) which factors fractions of polynomials by factoring ++ the numerator and denominator. Since any non zero fraction is a unit ++ the usual factor operation will just return the original fraction. RationalFunctionFactorizer(R) : C == T where R : EuclideanDomain -- R with factor for R[X] P ==> Polynomial R FP ==> Fraction P SE ==> Symbol C == with factorFraction : FP -> Fraction Factored(P) ++ factorFraction(r) factors the numerator and the denominator of ++ the polynomial fraction r. T == add factorFraction(p:FP) : Fraction Factored(P) == R is Fraction Integer => MR:=MRationalFactorize(IndexedExponents SE,SE, Integer,P) (factor(numer p)$MR)/ (factor(denom p)$MR) R has FiniteFieldCategory => FF:=MultFiniteFactorize(SE,IndexedExponents SE,R,P) (factor(numer p))$FF/(factor(denom p))$FF R has CharacteristicZero => MFF:=MultivariateFactorize(SE,IndexedExponents SE,R,P) (factor(numer p))$MFF/(factor(denom p))$MFF error "case not handled" @ \section{package SUPFRACF SupFractionFactorizer} <>= )abbrev package SUPFRACF SupFractionFactorizer ++ Author: P. Gianni ++ Date Created: October 1993 ++ Date Last Updated: March 1995 ++ Basic Functions: ++ Related Constructors: MultivariateFactorize ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: SupFractionFactorize ++ contains the factor function for univariate ++ polynomials over the quotient field of a ring S such that the package ++ MultivariateFactorize works for S SupFractionFactorizer(E,OV,R,P) : C == T where E : OrderedAbelianMonoidSup OV : OrderedSet R : GcdDomain P : PolynomialCategory(R,E,OV) FP ==> Fraction P SUP ==> SparseUnivariatePolynomial C == with factor : SUP FP -> Factored SUP FP ++ factor(p) factors the univariate polynomial p with coefficients ++ which are fractions of polynomials over R. squareFree : SUP FP -> Factored SUP FP ++ squareFree(p) returns the square-free factorization of the univariate polynomial p with coefficients ++ which are fractions of polynomials over R. Each factor has no repeated roots and the factors are ++ pairwise relatively prime. T == add MFACT ==> MultivariateFactorize(OV,E,R,P) MSQFR ==> MultivariateSquareFree(E,OV,R,P) UPCF2 ==> UnivariatePolynomialCategoryFunctions2 factor(p:SUP FP) : Factored SUP FP == p=0 => 0 R has CharacteristicZero and R has EuclideanDomain => pden : P := lcm [denom c for c in coefficients p] pol : SUP FP := (pden::FP)*p ipol: SUP P := map(numer,pol)$UPCF2(FP,SUP FP,P,SUP P) ffact: Factored SUP P := 0 ffact := factor(ipol)$MFACT makeFR((1/pden * map(coerce,unit ffact)$UPCF2(P,SUP P,FP,SUP FP)), [["prime",map(coerce,u.factor)$UPCF2(P,SUP P,FP,SUP FP), u.exponent] for u in factors ffact]) squareFree p squareFree(p:SUP FP) : Factored SUP FP == p=0 => 0 pden : P := lcm [denom c for c in coefficients p] pol : SUP FP := (pden::FP)*p ipol: SUP P := map(numer,pol)$UPCF2(FP,SUP FP,P,SUP P) ffact: Factored SUP P := 0 if R has CharacteristicZero and R has EuclideanDomain then ffact := squareFree(ipol)$MSQFR else ffact := squareFree(ipol) makeFR((1/pden * map(coerce,unit ffact)$UPCF2(P,SUP P,FP,SUP FP)), [["sqfr",map(coerce,u.factor)$UPCF2(P,SUP P,FP,SUP FP), u.exponent] for u in factors ffact]) @ \section{License} <>= --Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. --All rights reserved. -- --Redistribution and use in source and binary forms, with or without --modification, are permitted provided that the following conditions are --met: -- -- - Redistributions of source code must retain the above copyright -- notice, this list of conditions and the following disclaimer. -- -- - Redistributions in binary form must reproduce the above copyright -- notice, this list of conditions and the following disclaimer in -- the documentation and/or other materials provided with the -- distribution. -- -- - Neither the name of The Numerical ALgorithms Group Ltd. nor the -- names of its contributors may be used to endorse or promote products -- derived from this software without specific prior written permission. -- --THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS --IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED --TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A --PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER --OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, --EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, --PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR --PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF --LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING --NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS --SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. @ <<*>>= <> <> <> <> <> <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}