\documentclass{article} \usepackage{open-axiom} \begin{document} \title{\$SPAD/src/algebra ideal.spad} \author{Patrizia Gianni} \maketitle \begin{abstract} \end{abstract} \eject \tableofcontents \eject \section{domain IDEAL PolynomialIdeals} <>= )abbrev domain IDEAL PolynomialIdeals ++ Author: P. Gianni ++ Date Created: summer 1986 ++ Date Last Updated: September 1996 ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: GTZ ++ Description: This domain represents polynomial ideals with coefficients in any ++ field and supports the basic ideal operations, including intersection ++ sum and quotient. ++ An ideal is represented by a list of polynomials (the generators of ++ the ideal) and a boolean that is true if the generators are a Groebner ++ basis. ++ The algorithms used are based on Groebner basis computations. The ++ ordering is determined by the datatype of the input polynomials. ++ Users may use refinements of total degree orderings. PolynomialIdeals(F,Expon,VarSet,DPoly) : C == T where F : Field Expon : OrderedAbelianMonoidSup VarSet : OrderedSet DPoly : PolynomialCategory(F,Expon,VarSet) SUP ==> SparseUnivariatePolynomial(DPoly) NNI ==> NonNegativeInteger Z ==> Integer P ==> Polynomial F MF ==> Matrix(F) ST ==> SuchThat(List P, List Equation P) GenMPos ==> Record(mval:MF,invmval:MF,genIdeal:Ideal) Ideal ==> % C == SetCategory with * : (Ideal,Ideal) -> Ideal ++ I*J computes the product of the ideal I and J. ** : (Ideal,NNI) -> Ideal ++ I**n computes the nth power of the ideal I. + : (Ideal,Ideal) -> Ideal ++ I+J computes the ideal generated by the union of I and J. one? : Ideal -> Boolean ++ one?(I) tests whether the ideal I is the unit ideal, ++ i.e. contains 1. zero? : Ideal -> Boolean ++ zero?(I) tests whether the ideal I is the zero ideal element? : (DPoly,Ideal) -> Boolean ++ element?(f,I) tests whether the polynomial f belongs to ++ the ideal I. in? : (Ideal,Ideal) -> Boolean ++ in?(I,J) tests if the ideal I is contained in the ideal J. inRadical? : (DPoly,Ideal) -> Boolean ++ inRadical?(f,I) tests if some power of the polynomial f ++ belongs to the ideal I. zeroDim? : (Ideal,List VarSet) -> Boolean ++ zeroDim?(I,lvar) tests if the ideal I is zero dimensional, i.e. ++ all its associated primes are maximal, ++ in the ring \spad{F[lvar]} zeroDim? : Ideal -> Boolean ++ zeroDim?(I) tests if the ideal I is zero dimensional, i.e. ++ all its associated primes are maximal, ++ in the ring \spad{F[lvar]}, where lvar are the variables appearing in I intersect : (Ideal,Ideal) -> Ideal ++ intersect(I,J) computes the intersection of the ideals I and J. intersect : List(Ideal) -> Ideal ++ intersect(LI) computes the intersection of the list of ideals LI. quotient : (Ideal,Ideal) -> Ideal ++ quotient(I,J) computes the quotient of the ideals I and J, \spad{(I:J)}. quotient : (Ideal,DPoly) -> Ideal ++ quotient(I,f) computes the quotient of the ideal I by the principal ++ ideal generated by the polynomial f, \spad{(I:(f))}. groebner : Ideal -> Ideal ++ groebner(I) returns a set of generators of I that are a Groebner basis ++ for I. generalPosition : (Ideal,List VarSet) -> GenMPos ++ generalPosition(I,listvar) perform a random linear ++ transformation on the variables in listvar and returns ++ the transformed ideal along with the change of basis matrix. backOldPos : GenMPos -> Ideal ++ backOldPos(genPos) takes the result ++ produced by \spadfunFrom{generalPosition}{PolynomialIdeals} ++ and performs the inverse transformation, returning the original ideal ++ \spad{backOldPos(generalPosition(I,listvar))} = I. dimension : (Ideal,List VarSet) -> Z ++ dimension(I,lvar) gives the dimension of the ideal I, ++ in the ring \spad{F[lvar]} dimension : Ideal -> Z ++ dimension(I) gives the dimension of the ideal I. ++ in the ring \spad{F[lvar]}, where lvar are the variables appearing in I leadingIdeal : Ideal -> Ideal ++ leadingIdeal(I) is the ideal generated by the ++ leading terms of the elements of the ideal I. ideal : List DPoly -> Ideal ++ ideal(polyList) constructs the ideal generated by the list ++ of polynomials polyList. groebnerIdeal : List DPoly -> Ideal ++ groebnerIdeal(polyList) constructs the ideal generated by the list ++ of polynomials polyList which are assumed to be a Groebner ++ basis. ++ Note: this operation avoids a Groebner basis computation. groebner? : Ideal -> Boolean ++ groebner?(I) tests if the generators of the ideal I are a Groebner basis. generators : Ideal -> List DPoly ++ generators(I) returns a list of generators for the ideal I. coerce : List DPoly -> Ideal ++ coerce(polyList) converts the list of polynomials polyList to an ideal. saturate : (Ideal,DPoly) -> Ideal ++ saturate(I,f) is the saturation of the ideal I ++ with respect to the multiplicative ++ set generated by the polynomial f. saturate :(Ideal,DPoly,List VarSet) -> Ideal ++ saturate(I,f,lvar) is the saturation with respect to the prime ++ principal ideal which is generated by f in the polynomial ring ++ \spad{F[lvar]}. if VarSet has ConvertibleTo Symbol then relationsIdeal : List DPoly -> ST ++ relationsIdeal(polyList) returns the ideal of relations among the ++ polynomials in polyList. T == add --- Representation --- Rep := Record(idl:List DPoly,isGr:Boolean) ---- Local Functions ---- contractGrob : newIdeal -> Ideal npoly : DPoly -> newPoly oldpoly : newPoly -> Union(DPoly,"failed") leadterm : (DPoly,VarSet) -> DPoly choosel : (DPoly,DPoly) -> DPoly isMonic? : (DPoly,VarSet) -> Boolean randomat : List Z -> Record(mM:MF,imM:MF) monomDim : (Ideal,List VarSet) -> NNI variables : Ideal -> List VarSet subset : List VarSet -> List List VarSet makeleast : (List VarSet,List VarSet) -> List VarSet newExpon: OrderedAbelianMonoidSup newExpon:= Product(NNI,Expon) newPoly := PolynomialRing(F,newExpon) import GaloisGroupFactorizer(SparseUnivariatePolynomial Z) import GroebnerPackage(F,Expon,VarSet,DPoly) import GroebnerPackage(F,newExpon,VarSet,newPoly) newIdeal ==> List(newPoly) npoly(f:DPoly) : newPoly == f=0$DPoly => 0$newPoly monomial(leadingCoefficient f,makeprod(0,degree f))$newPoly + npoly(reductum f) oldpoly(q:newPoly) : Union(DPoly,"failed") == q=0$newPoly => 0$DPoly dq:newExpon:=degree q n:NNI:=selectfirst (dq) not zero? n => "failed" ((g:=oldpoly reductum q) case "failed") => "failed" monomial(leadingCoefficient q,selectsecond dq)$DPoly + (g::DPoly) leadterm(f:DPoly,lvar:List VarSet) : DPoly == empty?(lf:=variables f) or lf=lvar => f leadterm(leadingCoefficient univariate(f,lf.first),lvar) choosel(f:DPoly,g:DPoly) : DPoly == g=0 => f (f1:=f exquo g) case "failed" => f choosel(f1::DPoly,g) contractGrob(I1:newIdeal) : Ideal == J1:List(newPoly):=groebner(I1) while (oldpoly J1.first) case "failed" repeat J1:=J1.rest [[(oldpoly f)::DPoly for f in J1],true] makeleast(fullVars: List VarSet,leastVars:List VarSet) : List VarSet == n:= # leastVars #fullVars < n => error "wrong vars" n=0 => fullVars append([vv for vv in fullVars| not member?(vv,leastVars)],leastVars) isMonic?(f:DPoly,x:VarSet) : Boolean == ground? leadingCoefficient univariate(f,x) subset(lv : List VarSet) : List List VarSet == #lv =1 => [lv,empty()] v:=lv.1 ll:=subset(rest lv) l1:=[concat(v,set) for set in ll] concat(l1,ll) monomDim(listm:Ideal,lv:List VarSet) : NNI == monvar: List List VarSet := [] for f in generators listm repeat mvset := variables f #mvset > 1 => monvar:=concat(mvset,monvar) lv:=delete(lv,position(mvset.1,lv)) empty? lv => 0 lsubset : List List VarSet := sort(#(#1)>#(#2),subset(lv)) for subs in lsubset repeat ldif:List VarSet:= lv for mvset in monvar while ldif ~=[] repeat ldif:=setDifference(mvset,subs) if not (empty? ldif) then return #subs 0 -- Exported Functions ---- ---- is I = J ? ---- (I:Ideal = J:Ideal) == in?(I,J) and in?(J,I) ---- check if f is in I ---- element?(f:DPoly,I:Ideal) : Boolean == Id:=(groebner I).idl empty? Id => f = 0 normalForm(f,Id) = 0 ---- check if I is contained in J ---- in?(I:Ideal,J:Ideal):Boolean == J:= groebner J empty?(I.idl) => true "and"/[element?(f,J) for f in I.idl ] ---- groebner base for an Ideal ---- groebner(I:Ideal) : Ideal == I.isGr => "or"/[not zero? f for f in I.idl] => I [empty(),true] [groebner I.idl ,true] ---- Intersection of two ideals ---- intersect(I:Ideal,J:Ideal) : Ideal == empty?(Id:=I.idl) => I empty?(Jd:=J.idl) => J tp:newPoly := monomial(1,makeprod(1,0$Expon))$newPoly tp1:newPoly:= tp-1 contractGrob(concat([tp*npoly f for f in Id], [tp1*npoly f for f in Jd])) ---- intersection for a list of ideals ---- intersect(lid:List(Ideal)) : Ideal == "intersect"/[l for l in lid] ---- quotient by an element ---- quotient(I:Ideal,f:DPoly) : Ideal == --[[(g exquo f)::DPoly for g in (intersect(I,[f]::%)).idl ],true] import GroebnerInternalPackage(F,Expon,VarSet,DPoly) [minGbasis [(g exquo f)::DPoly for g in (intersect(I,[f]::%)).idl ],true] ---- quotient of two ideals ---- quotient(I:Ideal,J:Ideal) : Ideal == Jdl := J.idl empty?(Jdl) => ideal [1] [("intersect"/[quotient(I,f) for f in Jdl ]).idl ,true] ---- sum of two ideals ---- (I:Ideal + J:Ideal) : Ideal == [groebner(concat(I.idl ,J.idl )),true] ---- product of two ideals ---- (I:Ideal * J:Ideal):Ideal == [groebner([:[f*g for f in I.idl ] for g in J.idl ]),true] ---- power of an ideal ---- (I:Ideal ** n:NNI) : Ideal == n=0 => [[1$DPoly],true] (I * (I**(n-1):NNI)) ---- saturation with respect to the multiplicative set f**n ---- saturate(I:Ideal,f:DPoly) : Ideal == f=0 => error "f is zero" tp:newPoly := (monomial(1,makeprod(1,0$Expon))$newPoly * npoly f)-1 contractGrob(concat(tp,[npoly g for g in I.idl ])) ---- saturation with respect to a prime principal ideal in lvar --- saturate(I:Ideal,f:DPoly,lvar:List(VarSet)) : Ideal == Id := I.idl fullVars := "setUnion"/[variables g for g in Id] newVars:=makeleast(fullVars,lvar) subVars := [monomial(1,vv,1) for vv in newVars] J:List DPoly:=groebner([eval(g,fullVars,subVars) for g in Id]) ltJ:=[leadterm(g,lvar) for g in J] s:DPoly:=_*/[choosel(ltg,f) for ltg in ltJ] fullPol:=[monomial(1,vv,1) for vv in fullVars] [[eval(g,newVars,fullPol) for g in (saturate(J::%,s)).idl],true] ---- is the ideal zero dimensional? ---- ---- in the ring F[lvar]? ---- zeroDim?(I:Ideal,lvar:List VarSet) : Boolean == J:=(groebner I).idl empty? J => false J = [1] => false n:NNI := # lvar #J < n => false for f in J while not empty?(lvar) repeat x:=(mainVariable f)::VarSet if isMonic?(f,x) then lvar:=delete(lvar,position(x,lvar)) empty?(lvar) ---- is the ideal zero dimensional? ---- zeroDim?(I:Ideal):Boolean == zeroDim?(I,"setUnion"/[variables g for g in I.idl]) ---- test if f is in the radical of I ---- inRadical?(f:DPoly,I:Ideal) : Boolean == f=0$DPoly => true tp:newPoly :=(monomial(1,makeprod(1,0$Expon))$newPoly * npoly f)-1 Id:=I.idl normalForm(1$newPoly,groebner concat(tp,[npoly g for g in Id])) = 0 ---- dimension of an ideal ---- ---- in the ring F[lvar] ---- dimension(I:Ideal,lvar:List VarSet) : Z == I:=groebner I empty?(I.idl) => # lvar element?(1,I) => -1 truelist:="setUnion"/[variables f for f in I.idl] "or"/[not member?(vv,lvar) for vv in truelist] => error "wrong variables" truelist:=setDifference(lvar,setDifference(lvar,truelist)) ed:Z:=#lvar - #truelist leadid:=leadingIdeal(I) n1:Z:=monomDim(leadid,truelist)::Z ed+n1 dimension(I:Ideal) : Z == dimension(I,"setUnion"/[variables g for g in I.idl]) -- leading term ideal -- leadingIdeal(I : Ideal) : Ideal == Idl:= (groebner I).idl [[(f-reductum f) for f in Idl],true] ---- ideal of relations among the fi ---- if VarSet has ConvertibleTo Symbol then monompol(df:List NNI,lcf:F,lv:List VarSet) : P == g:P:=lcf::P for dd in df for v in lv repeat g:= monomial(g,convert v,dd) g relationsIdeal(listf : List DPoly): ST == empty? listf => [empty(),empty()]$ST nf:=#listf lvint := "setUnion"/[variables g for g in listf] vl: List Symbol := [convert vv for vv in lvint] nvar:List Symbol:=[new() for i in 1..nf] VarSet1:=OrderedVariableList(concat(vl,nvar)) lv1:=[variable(vv)$VarSet1::VarSet1 for vv in nvar] DirP:=DirectProduct(nf,NNI) nExponent:=Product(Expon,DirP) nPoly := PolynomialRing(F,nExponent) gp:=GroebnerPackage(F,nExponent,VarSet1,nPoly) lf:List nPoly :=[] lp:List P:=[] for f in listf for i in 1.. repeat vec2:Vector(NNI):=new(nf,0$NNI) vec2.i:=1 g:nPoly:=0$nPoly pol:=0$P while not zero? f repeat df:=degree(f-reductum f,lvint) lcf:=leadingCoefficient f pol:=pol+monompol(df,lcf,lvint) g:=g+monomial(lcf,makeprod(degree f,0))$nPoly f:=reductum f lp:=concat(pol,lp) lf:=concat(monomial(1,makeprod(0,directProduct vec2))-g,lf) npol:List P :=[v::P for v in nvar] leq : List Equation P := [p = pol for p in npol for pol in reverse lp ] lf:=(groebner lf)$gp while lf~=[] repeat q:=lf.first dq:nExponent:=degree q n:=selectfirst (dq) if n=0 then leave "done" lf:=lf.rest solsn:List P:=[] for q in lf repeat g:Polynomial F :=0 while not zero? q repeat dq:=degree q lcq:=leadingCoefficient q q:=reductum q vdq:=(selectsecond dq):Vector NNI g:=g+ lcq* _*/[p**vdq.j for p in npol for j in 1..] solsn:=concat(g,solsn) [solsn,leq]$ST coerce(Id:List DPoly) : Ideal == [Id,false] coerce(I:Ideal) : OutputForm == Idl := I.idl empty? Idl => [0$DPoly] :: OutputForm Idl :: OutputForm ideal(Id:List DPoly) :Ideal == [[f for f in Id|not zero? f],false] groebnerIdeal(Id:List DPoly) : Ideal == [Id,true] generators(I:Ideal) : List DPoly == I.idl groebner?(I:Ideal) : Boolean == I.isGr one?(I:Ideal) : Boolean == element?(1, I) zero?(I:Ideal) : Boolean == empty? (groebner I).idl @ \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}