Initial population.

1 files changed, 218 insertions, 0 deletions

diff --git a/src/algebra/facutil.spad.pamphlet b/src/algebra/facutil.spad.pamphlet
new file mode 100644
index 00000000..2b7de8de
--- /dev/null
+++ b/src/algebra/facutil.spad.pamphlet
@@ -0,0 +1,218 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra facutil.spad}
+\author{Barry Trager}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package FACUTIL FactoringUtilities}
+<<package FACUTIL FactoringUtilities>>=
+)abbrev package FACUTIL FactoringUtilities
+++ Author: Barry Trager
+++ Date Created: March 12, 1992
+++ Date Last Updated:
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++ This package provides utilities used by the factorizers
+++ which operate on polynomials represented as univariate polynomials
+++ with multivariate coefficients.
+
+FactoringUtilities(E,OV,R,P) : C == T where
+   E : OrderedAbelianMonoidSup
+   OV : OrderedSet
+   R : Ring
+   P : PolynomialCategory(R,E,OV)
+
+   SUP ==> SparseUnivariatePolynomial
+   NNI ==> NonNegativeInteger
+   Z   ==> Integer
+
+   C == with
+        completeEval   :      (SUP P,List OV,List R)        -> SUP R
+          ++ completeEval(upoly, lvar, lval) evaluates the polynomial upoly
+          ++ with each variable in lvar replaced by the corresponding value
+          ++ in lval. Substitutions are done for all variables in upoly
+          ++ producing a univariate polynomial over R.
+        degree         :       (SUP P,List OV)              -> List NNI
+          ++ degree(upoly, lvar) returns a list containing the maximum
+          ++ degree for each variable in lvar.
+        variables      :           SUP P                    -> List OV
+          ++ variables(upoly) returns the list of variables for the coefficients
+          ++ of upoly.
+        lowerPolynomial:           SUP P                    -> SUP R
+          ++ lowerPolynomial(upoly) converts upoly to be a univariate polynomial
+          ++ over R. An error if the coefficients contain variables.
+        raisePolynomial:           SUP R                    -> SUP P
+          ++ raisePolynomial(rpoly) converts rpoly from a univariate polynomial
+          ++ over r to be a univariate polynomial with polynomial coefficients.
+        normalDeriv     :        (SUP P,Z)                  -> SUP P
+          ++ normalDeriv(poly,i) computes the ith derivative of poly divided
+          ++ by i!.
+        ran        :                Z                       -> R
+          ++ ran(k) computes a random integer between -k and k as a member of R.
+
+   T == add
+
+     lowerPolynomial(f:SUP P) : SUP R ==
+       zero? f => 0$SUP(R)
+       monomial(ground leadingCoefficient f, degree f)$SUP(R) +
+           lowerPolynomial(reductum f)
+
+     raisePolynomial(u:SUP R) : SUP P ==
+       zero? u => 0$SUP(P)
+       monomial(leadingCoefficient(u)::P, degree u)$SUP(P) +
+           raisePolynomial(reductum u)
+
+     completeEval(f:SUP P,lvar:List OV,lval:List R) : SUP R ==
+       zero? f => 0$SUP(R)
+       monomial(ground eval(leadingCoefficient f,lvar,lval),degree f)$SUP(R) +
+              completeEval(reductum f,lvar,lval)
+
+     degree(f:SUP P,lvar:List OV) : List NNI ==
+       coefs := coefficients f
+       ldeg:= ["max"/[degree(fc,xx) for fc in coefs] for xx in lvar]
+
+     variables(f:SUP P) : List OV ==
+       "setUnion"/[variables cf for cf in coefficients f]
+
+     if R has FiniteFieldCategory then
+        ran(k:Z):R == random()$R
+     else
+	ran(k:Z):R == (random(2*k+1)$Z -k)::R
+
+  -- Compute the normalized m derivative
+     normalDeriv(f:SUP P,m:Z) : SUP P==
+       (n1:Z:=degree f) < m => 0$SUP(P)
+       n1=m => (leadingCoefficient f)::SUP(P)
+       k:=binomial(n1,m)
+       ris:SUP:=0$SUP(P)
+       n:Z:=n1
+       while n>= m repeat
+         while n1>n repeat
+           k:=(k*(n1-m)) quo n1
+           n1:=n1-1
+         ris:=ris+monomial(k*leadingCoefficient f,(n-m)::NNI)
+         f:=reductum f
+         n:=degree f
+       ris
+
+@
+\section{package PUSHVAR PushVariables}
+<<package PUSHVAR PushVariables>>=
+)abbrev package PUSHVAR PushVariables
+++ This package \undocumented{}
+PushVariables(R,E,OV,PPR):C == T where
+   E : OrderedAbelianMonoidSup
+   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
+   R  : Ring
+   PR ==> Polynomial R
+   PPR: PolynomialCategory(PR,E,OV)
+   SUP ==> SparseUnivariatePolynomial
+   C == with
+     pushdown : (PPR, OV) -> PPR
+	++ pushdown(p,v) \undocumented{}
+     pushdown : (PPR, List OV) -> PPR
+	++ pushdown(p,lv) \undocumented{}
+     pushup   : (PPR, OV) -> PPR
+	++ pushup(p,v) \undocumented{}
+     pushup   : (PPR, List OV) -> PPR
+	++ pushup(p,lv) \undocumented{}
+     map      : ((PR -> PPR), PPR) -> PPR
+	++ map(f,p) \undocumented{}
+
+   T == add
+     pushdown(g:PPR,x:OV) : PPR ==
+       eval(g,x,monomial(1,convert x,1)$PR)
+
+     pushdown(g:PPR, lv:List OV) : PPR ==
+       vals:=[monomial(1,convert x,1)$PR for x in lv]
+       eval(g,lv,vals)
+
+     map(f:(PR -> PPR), p: PPR) : PPR ==
+       ground? p => f(retract p)
+       v:=mainVariable(p)::OV
+       multivariate(map(map(f,#1),univariate(p,v)),v)
+
+               ----  push back the variable  ----
+     pushupCoef(c:PR, lv:List OV): PPR ==
+       ground? c => c::PPR
+       v:=mainVariable(c)::Symbol
+       v2 := variable(v)$OV
+       uc := univariate(c,v)
+       ppr : PPR := 0
+       v2 case OV =>
+          while not zero? uc repeat
+             ppr := ppr + monomial(1,v2,degree(uc))$PPR *
+                            pushupCoef(leadingCoefficient uc, lv)
+             uc := reductum uc
+          ppr
+       while not zero? uc repeat
+          ppr := ppr + monomial(1,v,degree(uc))$PR *
+                            pushupCoef(leadingCoefficient uc, lv)
+          uc := reductum uc
+       ppr
+
+     pushup(f:PPR,x:OV) :PPR ==
+       map(pushupCoef(#1,[x]), f)
+
+     pushup(g:PPR, lv:List OV) : PPR ==
+       map(pushupCoef(#1, lv), g)
+
+@
+\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 FACUTIL FactoringUtilities>>
+<<package PUSHVAR PushVariables>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}