Initial population.

1 files changed, 486 insertions, 0 deletions

diff --git a/src/algebra/allfact.spad.pamphlet b/src/algebra/allfact.spad.pamphlet
new file mode 100644
index 00000000..ccc9497d
--- /dev/null
+++ b/src/algebra/allfact.spad.pamphlet
@@ -0,0 +1,486 @@
+\documentclass{article}
+\usepackage{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 ug^=0 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
+       degree(denom r,xs)>0 => 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}