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