\documentclass{article} \usepackage{open-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} <>= )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 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} <>= --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}