path: root/src/algebra/allfact.spad.pamphlet

\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}