1module cali; 2 3% Author H.-G. Graebe | Univ. Leipzig 4% graebe@informatik.uni-leipzig.de 5 6% Redistribution and use in source and binary forms, with or without 7% modification, are permitted provided that the following conditions are met: 8% 9% * Redistributions of source code must retain the relevant copyright 10% notice, this list of conditions and the following disclaimer. 11% * Redistributions in binary form must reproduce the above copyright 12% notice, this list of conditions and the following disclaimer in the 13% documentation and/or other materials provided with the distribution. 14% 15% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 17% THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 18% PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNERS OR 19% CONTRIBUTORS 20% BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21% CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22% SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23% INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24% CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25% ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26% POSSIBILITY OF SUCH DAMAGE. 27% 28 29 30% terpri(); write "CALI 2.2.1 Last update June 22, 1995"; terpri(); 31 32COMMENT 33 34 ######################### 35 #### #### 36 #### HEADER MODULE #### 37 #### #### 38 ######################### 39 40This is the header module of the package CALI, a package for 41computational commutative algebra. 42 43Author : H.-G. Graebe 44 Univ. Leipzig 45 Institut fuer Informatik 46 Augustusplatz 10 - 11 47 D - 04109 Leipzig 48 Germany 49 50 email : graebe@informatik.uni-leipzig.de 51 52 53Version : 2.2.1, finished at June 22, 1995. 54 55See cali.chg for change's documentation. 56 57Please send all Comments, bugs, hints, wishes, criticisms etc. to the 58above email address. 59 60 61Abstract : 62 63This package contains algorithms for computations in commutative 64algebra closely related to the Groebner algorithm for ideals and 65modules. There are facilities for local computations, using a modern 66implementation of Mora's standard basis algorithm, that works for 67arbitrary term orders. This reflects the full analogy between modules 68over local rings and homogeneous (in fact H-local) modules over 69polynomial rings. 70 71CALI extends also the term order facilities of the REDUCE internal 72groebner package, defining term orders by degree vector lists, and 73the rigid implementation of the sugar idea, by a more flexible ecart 74vector, in particular useful for local computations. Version 2.2. has 75also a common view on normal forms for noetherian and non-noetherian 76term orders. 77 78The package was designed mainly as a symbolic mode programming 79environment extending the build-in facilities of REDUCE for the 80computational approach to problems arising naturally in commutative 81algebra. An algebraic mode interface allows to access (in a more 82rigid frame) all important features implemented symbolically. 83 84As main topics CALI contains facilities for 85 86-- defining rings, ideals and modules, 87 88-- computing Groebner bases and local standard bases, 89 90-- computing syzygies, resolutions and (graded) Betti numbers, 91 92-- computing (also weighted) Hilbert series, multiplicities, 93 independent sets, dimensions, 94 95-- computing normal forms and representations, 96 97-- computing sums, products, intersections, elimination ideals etc., 98 99-- primality tests, computation of radicals, unmixed radicals, 100 equidimensional parts, primary decompositions etc. of ideals 101 and modules, 102 103-- advanced applications of Groebner bases (blowup, associated graded 104 ring, analytic spread, symmetric algebra, monomial curves), 105 106-- applications of linear algebra techniques to zerodimensional 107 ideals, as e.g. the FGLM change of term orders, border bases 108 and affine and projective ideals of sets of points, 109 110-- splitting polynomial systems of equations mixing factorization and 111 Groebner algorithm, triangular systems, and different versions 112 of the extended Groebner factorizer. 113 114Reduce version required : 115 116The program was tested under v. 3.4 - 3.6. 117(I had some trouble with the module dualbases under 3.4.1) 118 119Relevant publications : 120 121See the bibliography in the manual. 122 123 124Key words : 125 126Groebner algorithm for ideals and modules, local standard bases, 127Groebner factorizer, extended Groebner factorizer, triangular systems, 128normal forms, ideal and module operations, Hilbert series, independent 129sets, dual bases, border bases, affine and projective sets of points, 130free resolution, constructive commutative algebra, primality test, 131radical, unmixed radical, equidimensional part, primary decomposition, 132blowup, associated graded ring, analytic spread, symmetric algebra, 133monomial curves. 134 135 136 137To be done : 138 139eo(vars) : test cali!=basering for eliminationorder according to vars 140 -> eliminate 141 142Remind : 143 144Never "put" variables, that are subject to rebounding via "where" ! 145 146end comment; 147 148create!-package( '( 149 cali % This header module. 150 bcsf % Base coeff. arithmetics. 151 ring % Base ring and monomial arithmetics. 152 mo % Monomial arithmetic. 153 dpoly % Distr. polynomial (and vector) arithmetics. 154 bas % Polynomial lists. 155 dpmat % dpmat's arithmetic. 156 red % Normal form algorithms and related topics. 157 groeb % Groebner algorithm and related topics. 158 groebf % Groebner factorizer and extensions. 159 matop % Module operations on dpmats. 160 quot % Different quotients. 161 moid % Lead. term ideal algorithms. 162 hf % Hilbert series. 163 res % Resolutions. 164 intf % Interface to algebraic mode. 165 odim % Alg. for zerodimensional ideals and 166 % modules. 167 prime % Primality test, radical, and primary 168 % decomposition. 169 scripts % Advanced applications, inspired by the 170 % scripts of Bayer/Stillman. 171 calimat % CALI's extension of the matrix package. 172 lf % The dual bases approach (FGLM etc.). 173 triang % (Zero dimensional) triangular systems. 174 ),'(contrib cali)); 175 176load!-package 'matrix; 177 178fluid '( 179 cali!=basering % see rings 180 cali!=degrees % see mons in rings 181 cali!=monset % see groeb 182 ); 183 184 % Default : 185switch 186 hardzerotest, % (off) see bcsf, try simp for each zerotest. 187 red_total, % (on) see red, do total reductions. 188 bcsimp, % (on) see red, cancel coefficient's gcd. 189 noetherian, % (on) see interf, test term orders and 190 % choose non local algorithms. 191 factorprimes, % (on) see primes, invoke groebfactor during 192 % prime decomposition. 193 factorunits, % (off) see groeb, try to remove units from 194 % polynomials by factorization. 195 detectunits, % (off) see groeb, detect generators of the form 196 % monomial * unit. 197 lexefgb; % (off) see groebf, invoke the extended 198 % Groebner factorizer with pure 199 % lex zerosolve. 200 201% The first initialization : 202 203put('cali,'trace,0); % No tracing. 204% linelength 79; % This is much more convenient than 80. 205 % However, it causes problems in window sys. 206 207% The new tracing. We hope that this shape will easily interface to a 208% forthcoming general trace utility. 209 210symbolic operator setcalitrace; 211symbolic procedure setcalitrace(n); 212% Set trace intensity. 213 put('cali,'trace,n); 214 215symbolic operator setcaliprintterms; 216symbolic procedure setcaliprintterms(n); 217% Set number of terms to be printed in intermediate output. 218 if n<=0 then typerr(n,"number of terms to be printed") 219 else put('cali,'printterms,n); 220 221symbolic operator clearcaliprintterms; 222symbolic procedure clearcaliprintterms; 223% Set intermediate output printing to "all". 224 << remprop('cali,'printterms); write"Term print bound cleared"; 225 terpri(); 226 >>; 227 228symbolic procedure cali_trace(); 229% Get the trace intensity. 230 get('cali,'trace); 231 232% ---- Some useful things, probably implemented also elsewhere 233% ---- in the system. 234 235symbolic procedure strcat l; 236% Concatenate the items in the list l to a string. 237 begin scalar u; 238 u:=for each x in l join explode x; 239 while memq('!!,u) do u:=delete('!!,u); 240 while memq('!",u) do u:=delete('!",u); 241 return compress append(append('(!"),u),'(!")); 242 end; 243 244symbolic procedure numberlistp l; 245% l is a list of numbers. 246 if null l then t 247 else fixp car l and numberlistp cdr l; 248 249symbolic procedure merge(l1,l2,fn); 250% Returns the (physical) merge of the two sorted lists l1 and l2. 251 if null l1 then l2 252 else if null l2 then l1 253 else if apply2(fn,car l1,car l2) then rplacd(l1,merge(cdr l1,l2,fn)) 254 else rplacd(l2,merge(l1,cdr l2,fn)); 255 256symbolic procedure listexpand(fn,l); eval expand(l,fn); 257 258symbolic procedure listtest(a,b,f); 259% Return the first u in a s.th. f(u,b) or nil. 260 if null a then nil 261 else if apply2(f,car a,b) then if car a=nil then t else car a 262 else listtest(cdr a,b,f); 263 264symbolic procedure listminimize(a,f); 265% Returns a minimal list b such that for all v in a ex. u in b such 266% that f(u,v). The elements are in the same order as in a. 267 if null a then nil else reverse cali!=min(nil,a,f); 268 269symbolic procedure cali!=min(b,a,f); 270 if null a then b 271 else if listtest(b,car a,f) or listtest(cdr a,car a,f) then 272 cali!=min(b,cdr a,f) 273 else cali!=min(car a . b,cdr a,f); 274 275% symbolic procedure makelist u; 'list . u; 276 277%% commented out 2015-01-24 since defined in rlisp/rsupport.red 278%%symbolic procedure subsetp(u,v); 279%%% true :<=> u \subset v 280%% if null u then t else member(car u,v) and subsetp(cdr u,v); 281 282symbolic procedure disjoint(a,b); 283 if null a then t else not member(car a,b) and disjoint(cdr a,b); 284 285symbolic procedure print_lf u; 286% Line feed after about 70 characters. 287 <<if posn()>69 then <<terpri();terpri()>>; prin2 u>>; 288 289symbolic procedure cali_choose(m,k); 290% Returns the list of k-subsets of m. 291 if (length m < k) then nil 292 else if k=1 then for each x in m collect list x 293 else nconc( 294 for each x in cali_choose(cdr m,k-1) collect (car m . x), 295 cali_choose(cdr m,k)); 296 297fluid '(cali!:varindex!!); 298cali!:varindex!! := 0; 299 300symbolic procedure make_cali_varname(); 301 <<cali!:varindex!! := cali!:varindex!!+1; 302 mkid('cali!:var,cali!:varindex!!)>>; 303 304endmodule; 305 306end; 307