open-axiom repository from github
\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}
<<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}
<<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}
<<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}
<<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}
<<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}
<<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}
<<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.
@
<<*>>=
<<license>>
<<package MRATFAC MRationalFactorize>>
<<package MPRFF MPolyCatRationalFunctionFactorizer>>
<<package MPCPF MPolyCatPolyFactorizer>>
<<package GENMFACT GeneralizedMultivariateFactorize>>
<<package RFFACTOR RationalFunctionFactorizer>>
<<package SUPFRACF SupFractionFactorizer>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}