\documentclass{article} \usepackage{open-axiom} \begin{document} \title{\$SPAD/src/algebra facutil.spad} \author{Barry Trager} \maketitle \begin{abstract} \end{abstract} \eject \tableofcontents \eject \section{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} <>= )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} <>= --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}