| 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) |