diff options
Diffstat (limited to 'src/algebra/gb.spad.pamphlet')
| -rw-r--r-- | src/algebra/gb.spad.pamphlet | 211 |
1 files changed, 211 insertions, 0 deletions
diff --git a/src/algebra/gb.spad.pamphlet b/src/algebra/gb.spad.pamphlet new file mode 100644 index 00000000..e62ca71f --- /dev/null +++ b/src/algebra/gb.spad.pamphlet @@ -0,0 +1,211 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra gb.spad} +\author{Rudiger Gebauer, Barry Trager} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\begin{verbatim} +--------- GROEBNER PACKAGE DRAFT 06 12/01/1986 +--------- +--------- Example to call groebner: +--------- +--------- s1:DMP[w,p,z,t,s,b]RN:= 45*p + 35*s - 165*b - 36 +--------- s2:DMP[w,p,z,t,s,b]RN:= 35*p + 40*z + 25*t - 27*s +--------- s3:DMP[w,p,z,t,s,b]RN:= 15*w + 25*p*s + 30*z - 18*t - 165*b**2 +--------- s4:DMP[w,p,z,t,s,b]RN:= -9*w + 15*p*t + 20*z*s +--------- s5:DMP[w,p,z,t,s,b]RN:= w*p + 2*z*t - 11*b**3 +--------- s6:DMP[w,p,z,t,s,b]RN:= 99*w - 11*b*s + 3*b**2 +--------- s7:DMP[w,p,z,t,s,b]RN:= b**2 + 33/50*b + 2673/10000 +--------- +--------- sn7:=[s1,s2,s3,s4,s5,s6,s7] +--------- +--------- groebner(sn7,info) +--------- +------------------------------------------------------------------------- +--------- +--------- groebner -> calculate minimal Groebner Basis +--------- +--------- all reductions are TOTAL reductions +--------- +--------- use string " redcrit " and you get the reduced critpairs +--------- printed +--------- +--------- use string " info " and you get information about +--------- +--------- ci => Leading monomial for critpair calculation +--------- tci => Number of terms of polynomial i +--------- cj => Leading monomial for critpair calculation +--------- tcj => Number of terms of polynomial j +--------- c => Leading monomial of critpair polynomial +--------- tc => Number of terms of critpair polynomial +--------- rc => Leading monomial of redcritpair polynomial +--------- trc => Number of terms of redcritpair polynomial +--------- tF => Number of polynomials in reduction list F +--------- tD => Number of critpairs still to do +--------- +\end{verbatim} +\section{package GB GroebnerPackage} +<<package GB GroebnerPackage>>= +)abbrev package GB GroebnerPackage +++ Authors: Gebauer, Trager +++ Date Created: 12-1-86 +++ Date Last Updated: 2-28-91 +++ Basic Functions: groebner normalForm +++ Related Constructors: Ideal, IdealDecompositionPackage +++ Also See: +++ AMS Classifications: +++ Keywords: groebner basis, polynomial ideal +++ References: +++ Description: \spadtype{GroebnerPackage} computes groebner +++ bases for polynomial ideals. The basic computation provides +++ a distinguished set of generators for polynomial ideals over fields. +++ This basis allows an easy test for membership: the operation \spadfun{normalForm} +++ returns zero on ideal members. When the provided coefficient domain, Dom, +++ is not a field, the result is equivalent to considering the extended +++ ideal with \spadtype{Fraction(Dom)} as coefficients, but considerably more efficient +++ since all calculations are performed in Dom. Additional argument "info" and "redcrit" +++ can be given to provide incremental information during +++ computation. Argument "info" produces a computational summary for each s-polynomial. +++ Argument "redcrit" prints out the reduced critical pairs. The term ordering +++ is determined by the polynomial type used. Suggested types include +++ \spadtype{DistributedMultivariatePolynomial}, +++ \spadtype{HomogeneousDistributedMultivariatePolynomial}, +++ \spadtype{GeneralDistributedMultivariatePolynomial}. + +GroebnerPackage(Dom, Expon, VarSet, Dpol): T == C where + + Dom: GcdDomain + Expon: OrderedAbelianMonoidSup + VarSet: OrderedSet + Dpol: PolynomialCategory(Dom, Expon, VarSet) + + T== with + + groebner: List(Dpol) -> List(Dpol) + ++ groebner(lp) computes a groebner basis for a polynomial ideal + ++ generated by the list of polynomials lp. + groebner: ( List(Dpol), String ) -> List(Dpol) + ++ groebner(lp, infoflag) computes a groebner basis + ++ for a polynomial ideal + ++ generated by the list of polynomials lp. + ++ Argument infoflag is used to get information on the computation. + ++ If infoflag is "info", then summary information + ++ is displayed for each s-polynomial generated. + ++ If infoflag is "redcrit", the reduced critical pairs are displayed. + ++ If infoflag is any other string, no information is printed during computation. + groebner: ( List(Dpol), String, String ) -> List(Dpol) + ++ groebner(lp, "info", "redcrit") computes a groebner basis + ++ for a polynomial ideal generated by the list of polynomials lp, + ++ displaying both a summary of the critical pairs considered ("info") + ++ and the result of reducing each critical pair ("redcrit"). + ++ If the second or third arguments have any other string value, + ++ the indicated information is suppressed. + + if Dom has Field then + normalForm: (Dpol, List(Dpol)) -> Dpol + ++ normalForm(poly,gb) reduces the polynomial poly modulo the + ++ precomputed groebner basis gb giving a canonical representative + ++ of the residue class. + C== add + import OutputForm + import GroebnerInternalPackage(Dom,Expon,VarSet,Dpol) + + if Dom has Field then + monicize(p: Dpol):Dpol == +-- one?(lc := leadingCoefficient p) => p + ((lc := leadingCoefficient p) = 1) => p + inv(lc)*p + + normalForm(p : Dpol, l : List(Dpol)) : Dpol == + redPol(p,map(monicize,l)) + + ------ MAIN ALGORITHM GROEBNER ------------------------ + + groebner( Pol: List(Dpol) ) == + Pol=[] => Pol + Pol:=[x for x in Pol | x ^= 0] + Pol=[] => [0] + minGbasis(sort( degree #1 > degree #2, gbasis(Pol,0,0))) + + groebner( Pol: List(Dpol), xx1: String) == + Pol=[] => Pol + Pol:=[x for x in Pol | x ^= 0] + Pol=[] => [0] + xx1 = "redcrit" => + minGbasis(sort( degree #1 > degree #2, gbasis(Pol,1,0))) + xx1 = "info" => + minGbasis(sort( degree #1 > degree #2, gbasis(Pol,2,1))) + messagePrint(" ") + messagePrint("WARNING: options are - redcrit and/or info - ") + messagePrint(" you didn't type them correct") + messagePrint(" please try again") + messagePrint(" ") + [] + + groebner( Pol: List(Dpol), xx1: String, xx2: String) == + Pol=[] => Pol + Pol:=[x for x in Pol | x ^= 0] + Pol=[] => [0] + (xx1 = "redcrit" and xx2 = "info") or + (xx1 = "info" and xx2 = "redcrit") => + minGbasis(sort( degree #1 > degree #2, gbasis(Pol,1,1))) + xx1 = "redcrit" and xx2 = "redcrit" => + minGbasis(sort( degree #1 > degree #2, gbasis(Pol,1,0))) + xx1 = "info" and xx2 = "info" => + minGbasis(sort( degree #1 > degree #2, gbasis(Pol,2,1))) + messagePrint(" ") + messagePrint("WARNING: options are - redcrit and/or info - ") + messagePrint(" you didn't type them correctly") + messagePrint(" please try again ") + messagePrint(" ") + [] + +@ +\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 GB GroebnerPackage>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |