Debian Codegraph @

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