Artifact 680eaaeff7d73adfffc1f3583942ac5118f1676613142b7d7956b27b79204360:
- Executable file
r37/packages/cali/moid.red
— part of check-in
[f2fda60abd]
at
2011-09-02 18:13:33
on branch master
— Some historical releases purely for archival purposes
git-svn-id: https://svn.code.sf.net/p/reduce-algebra/code/trunk/historical@1375 2bfe0521-f11c-4a00-b80e-6202646ff360 (user: arthurcnorman@users.sourceforge.net, size: 7227) [annotate] [blame] [check-ins using] [more...]
- Executable file
r38/packages/cali/moid.red
— part of check-in
[f2fda60abd]
at
2011-09-02 18:13:33
on branch master
— Some historical releases purely for archival purposes
git-svn-id: https://svn.code.sf.net/p/reduce-algebra/code/trunk/historical@1375 2bfe0521-f11c-4a00-b80e-6202646ff360 (user: arthurcnorman@users.sourceforge.net, size: 7227) [annotate] [blame] [check-ins using]
module moid; COMMENT ########################### ## ## ## MONOMIAL IDEALS ## ## ## ########################### This module supports computations with leading term ideals. Moideal monomials are assumed to be without module component, since a module moideal decomposes into the direct sum of ideal moideals. Lit.: [BS] Bayer, Stillman : J. Symb. Comp. 14 (1992), 31 - 50. This module contains : - A moideal prime decomposition along [BS] - An algorithm to find all strongly independent sets using moideal primes (also for modules), - An algorithm to compute the dimension (dim M := dim in(M)) based on strongly independent sets. - An easy dimension computation, correct for puredimensional ideals and modules. Monomial ideals have the following informal syntax : <moideal> ::= list of monomials To manage module moideals they are stored as assoc. list of (<component number> . <ideal moideal>) Moideals are kept ordered with respect to the descending lexicographic order, see [BS]. END COMMENT; % ------------- monomial ideal constructors -------------- symbolic procedure moid_from_bas bas; % Returns the list of leading monomials of the base list bas % not removing module components. for each x in bas_zerodelete bas collect dp_lmon bas_dpoly x; symbolic procedure moid_from_dpmat m; % Returns the assoc. list of moideals of the columns of the dpmat m. (if dpmat_cols m = 0 then list (0 . u) else for i:=1:dpmat_cols m collect i . for each x in u join if mo_comp(x)=i then {mo_deletecomp x}) where u=moid_from_bas dpmat_list m; symbolic procedure moid_2a m; % Convert the moideal m to algebraic mode. 'list . for each x in m collect dp_2a list dp_term(bc_fi 1,x); symbolic procedure moid_from_a m; % Convert a moideal from algebraic mode. if not eqcar(m,'list) then typerr(m,"moideal") else for each x in cdr m collect dp_lmon dp_from_a x; symbolic procedure moid_print m; mathprint moid_2a m; % ------- moideal arithmetics ------------------------ symbolic procedure moid_sum(a,b); % (Reduced) sum of two (v)moideals. moid_red append(a,b); symbolic procedure moid_intersect(a,b); % Intersection of two (pure !) moideals. begin scalar c; while b do << c:=nconc(for each x in a collect mo_lcm(x,car b),c); b:=cdr b >>; return moid_red c end; symbolic procedure moid_sort m; % Sorting by descending (pure) lexicographic order, first by mo_comp. sort(m,function mo_dlexcomp); symbolic procedure moid_red m; % Returns a minimal generating set of the (v)moideal m. moid!=red moid_sort m; symbolic procedure moid!=red m; begin scalar v; while m do << if not moid_member(car m,cdr m) then v:=car m . v; m:=cdr m; >>; return reversip v; end; symbolic procedure moid_member(mo,m); % true <=> c \in m vdivides mo. if null m then nil else mo_vdivides!?(car m,mo) or moid_member(mo,cdr m); symbolic procedure moid_radical u; % Returns the radical of the (pure) moideal u. moid_red for each x in u collect mo_radical x; symbolic procedure moid_quot(m,x); % The quotient of the moideal m by the monomial x. moid_red for each u in m collect mo_diff(u,mo_gcd(u,x)); % --------------- moideal prime decomposition -------------- % Returns the minimal primes of the moideal m as a list of variable % lists. symbolic procedure moid_primes m; begin scalar c,m1,m2; m:=listminimize(for each x in m collect mo_support x, function subsetp); for each x in m do if length x=1 then m1:=car x . m1 else m2:=x . m2; return for each x in moid!=primes(m2,ring_names cali!=basering) collect append(m1,x); end; symbolic procedure moid!=primes(m,vars); if null m then list nil else begin scalar b; b:=t; for each x in m do b:=b and intersection(x,vars); if not b then return nil; return listminimize( for each x in intersection(car m,vars) join for each y in moid!=primes(moid!=sps(x,cdr m), vars:=delete(x,vars)) collect x . y, function subsetp); end; symbolic procedure moid!=sps(x,m); for each y in m join if not memq(x,y) then {y}; % ------------ (Strongly) independent sets ----------------- symbolic procedure moid_max l; if null l then nil else car sort(l,function (lambda(x,y);length x >= length y)); symbolic procedure indepvarsets!* m; % Returns the sets of (strongly) independent variables for the % dpmat m. m must be a Groebner basis. begin scalar u,n; u:=listminimize( for each x in moid_from_dpmat m join moid_primes cdr x, function subsetp); n:=ring_names cali!=basering; return for each x in u collect setdiff(n,x); end; % ---------- Dimension and codimension ------------ symbolic procedure moid_goodindepvarset m; % Returns the lexicographically last maximal independent set of the % dpmat m. begin scalar l,n,l1; l:=sort(indepvarsets!* m, function (lambda(x,y);length x >= length y)); if null l then return nil; n:=length first l; l:=for each x in l join if length x = n then {x}; for each x in reverse ring_names cali!=basering do if length l>1 then << l1:=for each y in l join if member(x,y) then {y}; if l1 then l:=l1; >>; return first l; end; symbolic procedure dim!* m; % The dpmat m must be a Groebner basis. Computes the dimension of % Coker m as the greatest size of a strongly independent set. if not eqcar(m,'dpmat) then typerr(m,"DPMAT") else length moid_max indepvarsets!* m; symbolic procedure codim!* m; length ring_names cali!=basering - dim!* m; % ---- An easy independent set procedure ------------- symbolic operator easyindepset; symbolic procedure easyindepset m; if !*mode='algebraic then makelist easyindepset!* dpmat_from_a reval m else easyindepset!* m; symbolic procedure easyindepset!* m; % Returns a maximal with respect to inclusion independent set for the % moideal m. begin scalar b,c,d; m:=for each x in m collect mo_support x; b:=c:=ring_names cali!=basering; for each x in b do if moid!=ept(d:=delete(x,c),m) then c:=d; return setdiff(ring_names cali!=basering,c); end; symbolic procedure moid!=ept(l,m); if null m then t else intersection(l,car m) and moid!=ept(l,cdr m); symbolic operator easydim; symbolic procedure easydim m; if !*mode='algebraic then easydim!* dpmat_from_a reval m else easydim!* m; symbolic procedure easydim!* m; % Returns a lower bound for the dimension. The bound is true for % unmixed ideals (e.g. primes). m must be a gbasis. if not eqcar(m,'dpmat) then typerr(m,"DPMAT") else listexpand(function max2, for each x in moid_from_dpmat m collect length easyindepset!* cdr x); endmodule; % moid end;