Debian Codegraph @

tests/prep/0206tests/tmpexport/anbetti.sl

raw
1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2 %
3 % Betti numbers calculation
4 %
5 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6
7 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8 %% Copyright (C) 1996
9 %% Alexander Podoplelov
10 %%
11 %% Bergman and Anick are distributed in the hope that they will be
12 %% useful, but WITHOUT ANY WARRANTY. No author or distributor
13 %% accepts responsibility to anyone for the consequences of using them
14 %% or for whether they serve any particular purpose or work at all,
15 %% unless (s)he says so in writing. Refer to the Bergman General
16 %% Public License for full details.
17
18 %% Everyone is granted permission to copy, modify and redistribute
19 %% bergman, but only under the conditions described in the
20 %% Bergman General Public License. A copy of this license is
21 %% supposed to have been given to you along with bergman so you
22 %% can know your rights and responsibilities. It should be in a
23 %% file named copyright. Among other things, the copyright notice
24 %% and this notice must be preserved on all copies.
25 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
26
27 % CHANGES:
28
29 % 2001-08-10: Various changes, in order to get Betti numbers for
30 % other objects than rings.
31 % In particular, anBETTI was split into object type depending
32 % versions./JoeB, SK, VU
33
34 % 1998-07-03: Added MEMBER2NIL and made minor changes in
35 % anbtMAKEMATRIXLINE (as a temporary patch)./JoeB
36
37 (OFF RAISE)
38
39 (GLOBAL '(anZERO anBETTINUMS anCURRENTBETTINUMS btMacMx !*CALCBETTI
40 !*ONFLYBETTI))
41
42 % This procedure initializes variables which are used to collect
43 % information about Betti Numbers. It should be called before
44 % Anick calculation.
45 (DE anBETTIINIT ()
46 (PROGN
47 (SETQ anBETTINUMS (NCONS NIL))
48 (SETQ btMacMx NIL)
49 )
50 )
51
52 % This function accepts a homological degree of a chain,
53 % a list of all chains, and returns the number of chains
54 % of that degree in that list.
55 (DE anbtNUMBEROFCHAINS(order chains)
56 (PROG (i)
57 (SETQ i 0)
58 (MAPC chains (FUNCTION (LAMBDA (u)
59 (COND ( (EQ (anChn2Length u) order) (SETQ i (ADD1 i)) ))
60 )))
61 (RETURN i)
62 )
63 )
64
65
66 %(DE anbtMEMBER (what theset)
67 % (PROG (ip rt) % Input; Return value
68 % (COND ((NULL (SETQ ip theset))
69 % (RETURN NIL)))
70 % (SETQ rt 0)
71 % Ml (COND ((EQ what (CAR ip))
72 % (RETURN rt))
73 % ((SETQ ip (CDR ip))
74 % (INCR rt)
75 % (GO Ml)))
76 % )
77 %)
78
79
80
81
82 % MEMBER2NIL (element:any, list:lany) : genint ; DESTRUCTIVE (2)
83 % Searches list for its first occurrence of element.
84 % If found, the occurrence is (destructively) replaced by
85 % NIL, and the number of the position of element in list is
86 % returned. If element is not found in list, NIL is returned.
87 (DE MEMBER2NIL (what theset)
88 (PROG (ip rt) % Input; Return value
89 (COND ((NULL (SETQ ip theset))
90 (RETURN NIL)))
91 (SETQ rt 0)
92 Ml (COND ((EQ what (CAR ip))
93 (RPLACA ip NIL)
94 (RETURN rt))
95 ((SETQ ip (CDR ip))
96 (SETQ rt (ADD1 rt))
97 (GO Ml)))
98 )
99 )
100
101
102 % anbtZEROPROLONG (c:lratcoeff, n:int) : lratcoeff ;
103 % Returns a list whose first n elements are NIL (representing
104 % the coefficient zero), and which than continues with the list
105 % ``tail''.
106 (DE anbtZEROPROLONG (lrtcf int)
107 (PROG (i rt)
108 (COND ((ZEROP (SETQ i int))
109 (RETURN lrtcf)))
110 (SETQ rt lrtcf)
111 L1 (SETQ rt (CONS anZERO rt))
112 (COND ((EQ (SETQ i (SUB1 i)) 0)
113 (RETURN rt)))
114 (GO L1)
115 )
116 )
117
118
119 % anbtALIGN (m:llgenredandcoeff) : matrix ; DESTRUCTIVE
120 % This procedure destructively modifies the matrix "m" so
121 % that all its lines are prolonged by zero coefficients and
122 % have equal length, the length of its first input line.
123 % (Consequently, no other input line may be longer than the
124 % first one.) Besides aligning, to each line of the
125 % matrix the INTEGERISE function is applied. The modified
126 % matrix is returned.
127 (DE anbtALIGN(matrix)
128 (PROG (m r i)
129 (COND ( (NULL matrix)
130 (RETURN NIL) ))
131 (SETQ m (LENGTH (CAR matrix)))
132 (SETQ r matrix)
133 Ml (INTEGERISE (CAR r))
134 (COND ((SETQ r (CDR r))
135 (RPLACA r
136 (anbtZEROPROLONG (CAR r)
137 (DIFFERENCE m (LENGTH (CAR r)))))
138 (GO Ml)))
139 (RETURN matrix)
140 )
141 )
142
143
144
145 % anbtMAKEMATRIXLINE (id:lchn, pol:sdp) : lcoeff ;
146 % Returns a list of coefficients which are extracted from the pol.
147 % Only coefficients of semi-distributed monomials where
148 % corresponding qpol is equal to one are looked for.
149 % The corresponding chains to those qpols are placed into
150 % "id" list. Extracted coefficients are arranged according to the
151 % list "id" which is updated every time.
152 % colsIDlist = ( NIL (chnn) ... (chn2) (chn1) ) or ( NIL ) for the first time.
153 (DE anbtMAKEMATRIXLINE (colsIDlist sdp)
154 (PROG (a rt locols lcp)
155 (SETQ a (CDR sdp))
156 L1 (COND ( (Mon!= (APol2Lm (anSDP2FirstQPol a)) MONONE)
157 (SETQ locols
158 (CONS (CONS (anSDP2FirstChn a)
159 (Cf (QPol2LRatTm (anSDP2FirstQPol a))))
160 locols)
161 )
162 )
163 )
164 (COND ( (anNextSDPTail a)
165 (GO L1)
166 )
167 )
168 (COND ( (NULL locols) (RETURN NIL) ) )
169 (SETQ locols (CONS NIL locols) )
170 (COND ( (NULL (SETQ a (CDR colsIDlist))) (GO L4) ) )
171 (SETQ rt (TCONC NIL NIL))
172 L2 (COND ( (NOT (CDR (SETQ lcp locols))) (GO L5) ))
173 L3 (COND ( (anChn!= (CAR a) (CAADR lcp))
174 (TCONC rt (CDADR lcp)) % extracting the coefficient
175 (RPLACD lcp (CDDR lcp))
176 )
177
178 ( (NULL (CDR (SETQ lcp (CDR lcp)))) (TCONC rt anZERO) )
179 ( T (GO L3) )
180 )
181 (COND ( (SETQ a (CDR a)) (GO L2) ) )
182 (SETQ rt (CDAR rt))
183 L4 (COND ( (NULL (SETQ locols (CDR locols))) (RETURN rt) ) )
184 (RPLACD colsIDlist (CONS (CAAR locols) (CDR colsIDlist)))
185 (SETQ rt (CONS (CDAR locols) rt))
186 (GO L4)
187 L5 (TCONC rt anZERO)
188 (COND ( (SETQ a (CDR a)) (GO L5) ) )
189 (RETURN (CDAR rt))
190 )
191 )
192
193
194 % anbtMAKEMATRIX (order:int, chains:lchn) : llcoeff ;
195 % This procedure accepts homological degree "order" and a list
196 % of chains "lchn", and returns a "matrix" of coefficients of
197 % all the semi-distributed tensor polynomials corresponding
198 % to chains of that degree. The lines of its output "matrix"
199 % may have different lengths, however.
200 % chains = ( (chn1) (chn2) ... )
201 (DE anbtMAKEMATRIX (order chains)
202 (PROG (cols i rt cp)
203 (SETQ cols (NCONS NIL))
204 (SETQ cp chains)
205 Ml (COND ( (NULL cp)
206 (RETURN (anbtALIGN rt))))
207 (COND ( (EQ (anChn2Length (CAR cp)) order)
208 (SETQ i
209 (anbtMAKEMATRIXLINE cols
210 (anChn2Diff (CAR cp))))
211 (COND ( (NOT (NULL i))
212 (SETQ rt (CONS i rt))
213 ))
214 ))
215 (SETQ cp (CDR cp))
216 (GO Ml)
217 )
218 )
219
220
221 % anRingBETTI (chains:lchn) : - ;
222 % The procedure accepts as its argument a list which is an
223 % element of the anCHAINS degree list. More precisely,
224 % its tail is a list of chains, but the first element equals
225 % their homological degree. The procedure updates Betti
226 % numbers which are storied in anCURRENTBETTINUMS for this
227 % particular homological degree. anCURRENTBETTINUMS is some
228 % tail of the anBETTINUMS list.
229 % chains = ( deg (chn1) (chn2) ... ) - an element from anCHAINS
230 (DE anRingBETTI(chains)
231 (PROG (Qc Qn Rc Rn order top chns B lp cp)
232 (SETQ lp (SETQ cp (LASTPAIR anBETTINUMS)))
233 (SETQ chns (CDR chains))
234 (SETQ top (CAR chains))
235 (SETQ order (SETQ Rc 0))
236 (SETQ Qc (anbtNUMBEROFCHAINS 0 chns))
237 L1 (SETQ Qn (anbtNUMBEROFCHAINS (ADD1 order) chns))
238 (SETQ Rn
239 (COND ( (OR (EQ Qn 0) (EQ (ADD1 order) top)) 0 )
240 ( T (anRANK (anbtMAKEMATRIX (ADD1 order) chns)) )
241 )
242 )
243 (SETQ B (DIFFERENCE Qc (PLUS2 Rc Rn)))
244 (COND ( (NEQ B 0)
245 (RPLACD cp (NCONS (CONS (CONS order top) B) ))
246 (SETQ cp (CDR cp))
247 (anbtMacSet order top B)
248 ))
249 (SETQ Qc Qn)
250 (SETQ Rc Rn)
251 (SETQ order (ADD1 order))
252 (COND ( (LESSP order top) (GO L1) ))
253 % Here conditional printing of the new BETTINUMs should be inserted;
254 % or (more modularised):
255 (SETQ anCURRENTBETTINUMS (CDR lp))
256 )
257 )
258
259
260 % anALLBETTI () : - ;
261 % This procedure applies the procedure anBETTI to all elements
262 % of the anCHAINS list. It should be called if the calculation
263 % of Betti numbers was not invoked during calculation of the Groebner
264 % basis.
265 (DE anALLBETTI () (MAPC anCHAINS (FUNCTION (LAMBDA (u) (anBETTI u)))))
266
267
268 % PRINTBETTINUMBER (btnumber:btnum) : - ;
269 % Prints Betti number btnumber as follows:
270 % B(order, degree) = value
271 % The procedure chould be changed when weights would be possible
272 % for Anick. Here artificially weights for module variables
273 % are made to be equal zero VU-01.08.16
274 (DE PRINTBETTINUMBER (btnum)
275 (PROGN (PRIN2 "B(")
276 (COND ((EQ (GETOBJECTTYPE) 'RING)(PRIN2 (ADD1 (CAAR btnum))))
277 (T (PRIN2 (CAAR btnum))))
278 (PRIN2 '!,)
279 (COND ((EQ (GETOBJECTTYPE) 'RING)(PRIN2 (CDAR btnum)))
280 ((EQ (GETOBJECTTYPE) 'TWOMODULES)
281 (PRIN2 (DIFFERENCE (CDAR btnum) 2)))
282 (T (PRIN2 (DIFFERENCE (CDAR btnum) 1))))
283 (PRIN2 ")=")
284 (PRINT (CDR btnum))
285 )
286 )
287
288 % PRINTBETTI () : - ;
289 % Prints all the calculated Betti numbers.
290 % ((Applies the procedure PRINTBETTINUMBER to all elements of the
291 % anBETTINUMS list.))
292 (DE PRINTBETTI () (MAPC (CDR anBETTINUMS) (FUNCTION PRINTBETTINUMBER)))
293
294 % PRINTCURRENTBETTI () : - ;
295 % Prints Betti numbers for the last calculated Groebner basis
296 % degree. Applies the procedure PRINTBETTINUMBER to all
297 % elements of the anCURRENTBETTINUMS list.
298 (DE PRINTCURRENTBETTI () (MAPC anCURRENTBETTINUMS (FUNCTION PRINTBETTINUMBER)))
299
300 % anbtMacCorrect (deg:int) : bool ;
301 % This procedure takes a degree for updating Betti numbers in
302 % a nice Macaulay form so that later it is possible to print them.
303 % It affects only internal btMacMx structure and return either
304 % T or NIL depending on whether the update actually changed
305 % btMacMx.
306 (DE anbtMacCorrect ( deg )
307 (PROG (i j cl)
308 (COND ( (LESSP (SETQ i (DIFFERENCE deg (LENGTH btMacMx))) 0)
309 (RETURN NIL) ))
310 (SETQ cl btMacMx)
311 L1 (COND ( (NULL cl) (GO LADD) ))
312 (SETQ j i)
313 L2 (COND ( (LESSP 0 j)
314 (NCONC (CAR cl) (NCONS NIL))
315 (SETQ j (SUB1 j))
316 (GO L2)))
317 (SETQ cl (CDR cl))
318 (GO L1)
319 LADD (COND ( (EQN i 0) (RETURN T) ))
320 (SETQ j (SETQ i (SUB1 i)))
321 (SETQ cl (NCONS NIL))
322 L3 (COND ( (LESSP 0 j)
323 (NCONC cl (NCONS NIL))
324 (SETQ j (SUB1 j))
325 (GO L3) ))
326 (COND ( (NULL btMacMx) (SETQ btMacMx (NCONS cl)) )
327 (T (NCONC btMacMx (NCONS cl)) ))
328 (GO LADD)
329 )
330 )
331
332 % anbtMacSet (order:int, degree:int, value:int) : bool ;
333 % Sets the value of Betti number in Macaulay form of corresponding
334 % "order" and "degree" to "value". Returns boolean value T.
335 (DE anbtMacSet (o p v)
336 (PROG (i j)
337 (COND ( (LESSP (LENGTH btMacMx) p) (anbtMacCorrect p) ))
338 (SETQ i btMacMx)
339 (SETQ j 1)
340 L1 (COND ( (LESSP j (DIFFERENCE p o)) (SETQ j (ADD1 j)) (SETQ i (CDR i)) (GO L1)))
341 (SETQ i (CAR i))
342 (SETQ j 0)
343 L2 (COND ( (LESSP j o) (SETQ j (ADD1 j)) (SETQ i (CDR i)) (GO L2)))
344 (RPLACA i v)
345 (RETURN T)
346 )
347 )
348
349 % MACBETTIPRINT () : bool ;
350 % Prints Betti numbers in Macaulay form. Returns boolean value T.
351 % The procedure chould be changed when weights would be possible
352 % for Anick. Here artificially weights for module variables
353 % are made to be equal zero VU-01.08.16
354 (DE MACBETTIPRINT ()
355 (PROG (i j len pos shift l cdeg)
356 (SETQ len 4)
357 (SETQ shift 4)
358 (SETQ cdeg (LENGTH btMacMx))
359 (SETQ l 0)
360 L0 (COND ( (LESSP l (ADD1 cdeg))
361 (TAB (PLUS2 shift (TIMES2 l len)))
362 (PRIN2 l) (SETQ l (ADD1 l)) (GO L0) ))
363 (SETQ l 0)
364 (TAB 0) (PRIN2 " +-")
365 L0_1 (COND ( (LESSP l (ADD1 (TIMES cdeg len)))
366 (PRIN2 '!-) (SETQ l (ADD1 l)) (GO L0_1) ))
367 (SETQ l 0)
368 (SETQ i btMacMx)
369 (COND ((EQ (GETOBJECTTYPE) 'TWOMODULES) (SETQ i (CDR i)))) %SK&VU
370 L1 (COND ( (NULL i) (TERPRI) (RETURN T) ))
371 (SETQ pos 1)
372 (SETQ j (CAR i))
373 L2 (COND ( (NULL j) (SETQ i (CDR i)) (GO L1)))
374 (COND ( (EQ j (CAR i))
375 (TERPRI) (PRIN2 l) (TAB 2) (PRIN2 "|")
376 (COND ((EQ (GETOBJECTTYPE) 'RING) %SK&VU
377 (TAB shift)
378 (COND ( (EQ i btMacMx) (PRIN2 1) )
379 (T (PRIN2 '!-) )))
380 )%endCond SK&VU
381 (SETQ l (ADD1 l))
382 )
383 )
384 (TAB (PLUS2 shift (TIMES2 len %SK&VU
385 (COND ((NOT (EQ (GETOBJECTTYPE) 'RING))
386 (SUB1 pos))
387 (T pos))))) % end SK&VU
388 (SETQ pos (ADD1 pos))
389 (COND ( (NULL (CAR j)) (PRIN2 '!-) )
390 (T (PRIN2 (CAR j))))
391 (SETQ j (CDR j))
392 (GO L2)
393 )
394 )
395
396 (DE anExtractBettiModes ()
397 (LIST (LIST 'BETTI !*CALCBETTI)
398 (LIST 'BETTI-FOREACHDEGREE !*ONFLYBETTI)
399 )
400 )
401
402 (ON RAISE)