--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.

)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("   ")
     []

