| 1 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 2 |
% |
| 3 |
% Betti numbers calculation for modules |
| 4 |
% |
| 5 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 6 |
|
| 7 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 8 |
%% Copyright (C) 1996,2001 |
| 9 |
%% Alexander Podoplelov, Joergen Backelin |
| 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 |
% Created 2001-08-06 out of a copy of the file anbetti.sl, |
| 28 |
% in order to allow for calculation of more general Betti numbers. |
| 29 |
% We assume that we have a resolution Y_* of a right module M, |
| 30 |
% represented by a degree-list of chains |
| 31 |
% (where degrees are total degrees); and a left module N, |
| 32 |
% represented by a degree-list of "normal words", i.e., of |
| 33 |
% non-reducible monomials. |
| 34 |
|
| 35 |
% From subsets of these, various cartesian products may be |
| 36 |
% formed. For each such of the relevant total-degree and |
| 37 |
% homological degrees, the differentioal should be calculated, |
| 38 |
% and turned into a matrix line. Then the rank of the matrix |
| 39 |
% should be calculated. |
| 40 |
|
| 41 |
% Thus, the chains in the original file anbetti.sl should |
| 42 |
% be replaced by dotted pairs (chain . normal word); with |
| 43 |
% ensuing changes of homological degree calculation, rank |
| 44 |
% calculation, et cetera. |
| 45 |
|
| 46 |
% First of all, a 'more precise' version of anCHAINS, |
| 47 |
% anbnmSORTEDCHAINS, should be kept and updated. Likewise should |
| 48 |
% the degree-list bnmLeftModuleNormalWords. |
| 49 |
|
| 50 |
|
| 51 |
(OFF RAISE) |
| 52 |
|
| 53 |
(GLOBAL '(anZERO anBETTINUMS anCURRENTBETTINUMS btMacMx anCHAINS |
| 54 |
anbnmSORTEDCHAINS bnmLeftModuleNormalWords anbnmTensorMons |
| 55 |
anbnmTensorMonsAccess anbnmNewTensorMonsAccess |
| 56 |
anbnmIndexLimits NALGGEN NLMODGEN NRMODGEN |
| 57 |
anbnmLModNormalMonStartIndexLimits |
| 58 |
anbnmLModNormalMonEndIndexLimits)) |
| 59 |
|
| 60 |
|
| 61 |
(DM anbnmPair2AMon (rrg) (CONS 'CAR (CDR rrg))) |
| 62 |
(DM anbnmPair2Chn (rrg) (CONS 'CDR (CDR rrg))) |
| 63 |
(DE anbnmChn!&AMon2Pair (chn amon) |
| 64 |
(INTERNPAIR chn amon (CDR anbnmTensorMonsAccess)) ) |
| 65 |
|
| 66 |
% Creates a degree-list w.r.t. homological degree, out of the |
| 67 |
% degree item of anCHAINS. If such ones are formed, the resulting |
| 68 |
% list is placed on anbnmSORTEDCHAINS, and returned. Else, NIL |
| 69 |
% is returned. |
| 70 |
% Meaning of PROG variables: remaining InPut list; ReTurn list; |
| 71 |
% Return list Position; Return list Element position; Homological |
| 72 |
% Degree of input chain. |
| 73 |
|
| 74 |
%# anUPDATESORTEDCHAINS (degno) : gen(degno.dlchain) ; |
| 75 |
(DE anUPDATESORTEDCHAINS (deg) |
| 76 |
(PROG (ip rt rp re hd) |
| 77 |
(COND ((NOT (AND (SETQ ip (ATSOC deg anCHAINS)) |
| 78 |
(CDR ip))) |
| 79 |
(RETURN NIL))) |
| 80 |
(SETQ rt (NCONS deg)) |
| 81 |
Ml (COND ((NOT (SETQ ip (CDR ip))) |
| 82 |
(SETQ anbnmSORTEDCHAINS |
| 83 |
(CONS rt anbnmSORTEDCHAINS)) |
| 84 |
(RETURN rt))) |
| 85 |
(SETQ rp rt) |
| 86 |
(SETQ hd (anChn2Length (CAR ip))) |
| 87 |
Sl (COND ((OR (NOT (CDR rp)) (BMI!< hd (CAADR rp))) |
| 88 |
(RPLACD rp (CONS (LIST hd (CAR ip)) (CDR rp))) |
| 89 |
(GO Ml)) |
| 90 |
((NOT (BMI!= hd (CAAR (SETQ rp (CDR rp))))) |
| 91 |
(GO Sl))) |
| 92 |
(SETQ re (CAR rp)) |
| 93 |
Tl (COND ((CDR re) |
| 94 |
(SETQ re (CDR re)) |
| 95 |
(GO Tl))) |
| 96 |
(RPLACD re (NCONS (CAR ip))) |
| 97 |
(GO Ml) )) |
| 98 |
|
| 99 |
|
| 100 |
% For potentially different situations, the identifier anbnmIndexLimits |
| 101 |
% is used for setting the limits for the indices of the variables with |
| 102 |
% which the LMNW's (Left Module Normal Words) are to be prepended. |
| 103 |
|
| 104 |
%# anbnmSetIndexLimits ( ) : - ; |
| 105 |
(DE anbnmSetIndexLimits () (SETQ anbnmIndexLimits (CONS 0 NALGGEN)) ) |
| 106 |
|
| 107 |
% Meaning of PROG variables: Variable Index; Index Limit; ReTurn list. |
| 108 |
|
| 109 |
%# anbnmLMNWInit ( ) : - ; |
| 110 |
(DE anbnmLMNWInit () |
| 111 |
(PROG (vi il rt) |
| 112 |
(SETQ vi (CDR anbnmLModNormalMonEndIndexLimits)) |
| 113 |
(SETQ il (SUB1 (CAR anbnmLModNormalMonEndIndexLimits))) |
| 114 |
Ml |
| 115 |
(COND ((BMI!< il vi) |
| 116 |
(SETQ rt (CONS (MONINTERN (LIST vi)) rt)) |
| 117 |
(SETQ vi (SUB1 vi)) |
| 118 |
(GO Ml))) |
| 119 |
(SETQ bnmLeftModuleNormalWords (NCONS (CONS 1 rt))) )) |
| 120 |
|
| 121 |
|
| 122 |
%# anbnmUpdateLMNW (degno) : gen(degno.laugmon) ; |
| 123 |
(DE anbnmUpdateLMNW (deg) |
| 124 |
(PROG (rt) |
| 125 |
(COND ((SETQ rt |
| 126 |
(noncommordweightsNormalWords deg |
| 127 |
bnmLeftModuleNormalWords |
| 128 |
anbnmLModNormalMonStartIndexLimits)) |
| 129 |
(SETQ bnmLeftModuleNormalWords |
| 130 |
(CONS rt bnmLeftModuleNormalWords)) |
| 131 |
(RETURN rt)) ))) |
| 132 |
|
| 133 |
|
| 134 |
% Makes a list and an accesslist for all pairs (chn,augmon) of |
| 135 |
% chains of homological degree hd and of left module normal words, |
| 136 |
% such that the sum of the total degrees is deg. Returns the |
| 137 |
% number of such pairs. |
| 138 |
|
| 139 |
% In practise, we want the LIST for the present hd (for going |
| 140 |
% through item by item, calculating differentials); but the ACCESS |
| 141 |
% for the preceeding hd (since that's the one of the tensor |
| 142 |
% monomials appearing in the differentials). We solve this by |
| 143 |
% creating a new access list, after saving the old one as the |
| 144 |
% relevant one.) |
| 145 |
|
| 146 |
% SHOULD BE CHANGED, IF TOTAL DEGREE CONVENTIONS CHANGE. Now, I |
| 147 |
% assume that both chains and normal words have POSITIVE total |
| 148 |
% degrees. |
| 149 |
|
| 150 |
% Meaning of PROG variables: ReTurn value; Chain Input list; |
| 151 |
% Normal Word Input list; Degree Number. |
| 152 |
|
| 153 |
|
| 154 |
%# anbnmListTensorMons (degno, degno) : int ; |
| 155 |
(DE anbnmListTensorMons (deg hd) |
| 156 |
(PROG (rt ci nwi dn) |
| 157 |
% (PRIN2 "anbnmListTensorMons <-- ") (PRIN2 deg) (PRIN2 " ") (PRINT hd) |
| 158 |
(SETQ rt 0) |
| 159 |
(SETQ anbnmTensorMons (NCONS hd)) |
| 160 |
(SETQ anbnmTensorMonsAccess anbnmNewTensorMonsAccess) |
| 161 |
(SETQ anbnmNewTensorMonsAccess (NCONS hd)) |
| 162 |
(SETQ dn deg) |
| 163 |
Ml (COND ((BMI!= 0 (SETQ dn (SUB1 dn))) |
| 164 |
% (PRIN2 "anbnmListTensorWords --> ") (PRINT rt) |
| 165 |
(RETURN rt)) |
| 166 |
((AND (SETQ ci (ATSOC dn anbnmSORTEDCHAINS)) |
| 167 |
(SETQ ci (ATSOC hd (CDR ci))) |
| 168 |
(SETQ nwi (ATSOC (BMI!- deg dn) |
| 169 |
bnmLeftModuleNormalWords))) |
| 170 |
% (PRIN2 "Will enter XSETPRODUCT with deg = ") (PRINT deg) |
| 171 |
(SETQ rt (PLUS (XSETPRODUCT (CDR ci) |
| 172 |
(CDR nwi) |
| 173 |
anbnmNewTensorMonsAccess |
| 174 |
anbnmTensorMons) |
| 175 |
rt)))) |
| 176 |
(GO Ml) )) |
| 177 |
|
| 178 |
|
| 179 |
|
| 180 |
|
| 181 |
% This procedure initializes variables which are used to collect |
| 182 |
% information about Betti Numbers. It should be called before |
| 183 |
% Anick calculation. |
| 184 |
(DE anbnmTwoModulesBETTIINIT () |
| 185 |
(PROGN |
| 186 |
(SETQ anBETTINUMS (NCONS NIL)) |
| 187 |
(SETQ btMacMx NIL) |
| 188 |
) |
| 189 |
) |
| 190 |
|
| 191 |
|
| 192 |
%# anbtbnmTwoModulesMakeMatrixLine (id:ldpany, pol:sdp) : lcoeff ; |
| 193 |
% Returns a list of coefficients which are extracted from the pol. |
| 194 |
% The tensor polynomial is regarded as fully distributed. ALL |
| 195 |
% coefficients of distributed tensor monomials are sought. |
| 196 |
% The interned dotted pairs corresponding to those tensor monomials |
| 197 |
% appearing are placed into |
| 198 |
% "id" list. Extracted coefficients are arranged according to the |
| 199 |
% list "id" which is updated every time. |
| 200 |
% colsIDlist = ( NIL (amonn.chnn) ... (amon2.chn2) (amon1.chn1) ). |
| 201 |
|
| 202 |
(DE anbtbnmTwoModulesMakeMatrixLine (colsIDlist sdp) |
| 203 |
(PROG (a rt locols lcp ch pl tm) |
| 204 |
(SETQ a (anSDPTail sdp)) |
| 205 |
L1 (SETQ ch (anSDP2FirstChn a)) |
| 206 |
(SETQ pl (anSDP2FirstQPol a)) |
| 207 |
Subl (SETQ tm (QPol2LRatTm pl)) |
| 208 |
(SETQ locols |
| 209 |
(CONS (CONS (anbnmChn!&AMon2Pair ch (Mon tm)) |
| 210 |
(Cf tm)) |
| 211 |
locols)) |
| 212 |
(COND ((PPol!? (RemoveNextTm pl)) |
| 213 |
(GO Subl)) |
| 214 |
((anNextSDPTail a) |
| 215 |
(GO L1))) |
| 216 |
(COND ( (NULL locols) (RETURN NIL) ) ) |
| 217 |
(SETQ locols (CONS NIL locols) ) |
| 218 |
(COND ( (NULL (SETQ a (CDR colsIDlist))) (GO L4) ) ) |
| 219 |
(SETQ rt (TCONC NIL NIL)) |
| 220 |
L2 (COND ( (NOT (CDR (SETQ lcp locols))) (GO L5) )) |
| 221 |
L3 (COND ( (anChn!= (CAR a) (CAADR lcp)) |
| 222 |
(TCONC rt (CDADR lcp)) % extracting the coefficient |
| 223 |
(RPLACD lcp (CDDR lcp)) |
| 224 |
) |
| 225 |
|
| 226 |
( (NULL (CDR (SETQ lcp (CDR lcp)))) (TCONC rt anZERO) ) |
| 227 |
( T (GO L3) ) |
| 228 |
) |
| 229 |
(COND ( (SETQ a (CDR a)) (GO L2) ) ) |
| 230 |
(SETQ rt (CDAR rt)) |
| 231 |
L4 (COND ( (NULL (SETQ locols (CDR locols))) (RETURN rt) ) ) |
| 232 |
(RPLACD colsIDlist (CONS (CAAR locols) (CDR colsIDlist))) |
| 233 |
(SETQ rt (CONS (CDAR locols) rt)) |
| 234 |
(GO L4) |
| 235 |
L5 (TCONC rt anZERO) |
| 236 |
(COND ( (SETQ a (CDR a)) (GO L5) ) ) |
| 237 |
(RETURN (CDAR rt)) |
| 238 |
) |
| 239 |
) |
| 240 |
|
| 241 |
|
| 242 |
% anbtMAKEMATRIX (order:int, chains:lchn) : llcoeff ; |
| 243 |
% This procedure accepts homological degree "order" and a list |
| 244 |
% of chains "lchn", and returns a "matrix" of coefficients of |
| 245 |
% all the semi-distributed tensor polynomials corresponding |
| 246 |
% to chains of that degree. The lines of its output "matrix" |
| 247 |
% may have different lengths, however. |
| 248 |
% chains = ( (chn1) (chn2) ... ) |
| 249 |
(DE anbtbnmTwoModulesMAKEMATRIX (order chains) |
| 250 |
(PROG (cols i rt cp) |
| 251 |
(SETQ cols (NCONS NIL)) |
| 252 |
(SETQ cp anbnmTensorMons) |
| 253 |
Ml (COND ((NULL (SETQ cp (CDR cp))) |
| 254 |
(RETURN (anbtALIGN rt))) |
| 255 |
((AND (anChn2Diff (anbnmPair2Chn (CAR cp))) |
| 256 |
(SETQ i (anCONCATTENSPOLMON (anChn2Diff |
| 257 |
(anbnmPair2Chn (CAR cp))) |
| 258 |
(anbnmPair2AMon (CAR cp)))) |
| 259 |
(anSDPTail i)) |
| 260 |
(SETQ rt (CONS (anbtbnmTwoModulesMakeMatrixLine cols i) |
| 261 |
rt)))) |
| 262 |
(GO Ml) )) |
| 263 |
|
| 264 |
|
| 265 |
% The procedure accepts as its argument a list which is an |
| 266 |
% element of the anCHAINS degree list. More precisely, |
| 267 |
% its tail is a list of chains, but the first element equals |
| 268 |
% their homological degree. The procedure updates Betti |
| 269 |
% numbers which are storied in anCURRENTBETTINUMS for this |
| 270 |
% particular homological degree. anCURRENTBETTINUMS is some |
| 271 |
% tail of the anBETTINUMS list. |
| 272 |
% chains - an element from anCHAINS - is hardly employed in this |
| 273 |
% variant. It is only used in order to extract the current degree |
| 274 |
% information. |
| 275 |
|
| 276 |
%# anTwoModulesBETTI (chains:lchn) : - ; |
| 277 |
(DE anTwoModulesBETTI (chains) |
| 278 |
(PROG (Qc Qn Rc Rn order top chns B lp cp) |
| 279 |
% (SETQ chns (CDR chains)) |
| 280 |
(SETQ top (CAR chains)) |
| 281 |
(SETQ order (SETQ Rc 0)) |
| 282 |
(SETQ cp anBETTINUMS) |
| 283 |
% (anUPDATESORTEDCHAINS top)% Done in anifTwoModulesResolutionFixDegree |
| 284 |
(anbnmUpdateLMNW top) |
| 285 |
L2 (COND ((CDR cp) |
| 286 |
(SETQ cp (CDR cp)) |
| 287 |
(GO L2))) |
| 288 |
(SETQ lp cp) |
| 289 |
L3 (COND ((BMI!= (SETQ Qc (anbnmListTensorMons top order)) 0) |
| 290 |
(COND ((BMI!< (SETQ order (ADD1 order)) top) |
| 291 |
(GO L3)) |
| 292 |
(T |
| 293 |
(GO End))))) |
| 294 |
L1 (SETQ Qn (anbnmListTensorMons top (ADD1 order))) |
| 295 |
(SETQ Rn |
| 296 |
(COND ((OR (EQ Qn 0) (EQ (ADD1 order) top)) 0) |
| 297 |
(T (anRANK (anbtbnmTwoModulesMAKEMATRIX))))) |
| 298 |
(SETQ B (DIFFERENCE Qc (PLUS2 Rc Rn))) |
| 299 |
(COND ( (NEQ B 0) |
| 300 |
(RPLACD cp (NCONS (CONS (CONS order top) B) )) |
| 301 |
(SETQ cp (CDR cp)) |
| 302 |
(anbtMacSet order top B) |
| 303 |
)) |
| 304 |
(SETQ Qc Qn) |
| 305 |
(SETQ Rc Rn) |
| 306 |
(SETQ order (ADD1 order)) |
| 307 |
(COND ( (LESSP order top) (GO L1) )) |
| 308 |
% Here conditional printing of the new BETTINUMs should be inserted; |
| 309 |
% or (more modularised): |
| 310 |
End (SETQ anCURRENTBETTINUMS (CDR lp)) |
| 311 |
(SETQ anbnmTensorMons NIL) |
| 312 |
(SETQ anbnmTensorMonsAccess NIL) |
| 313 |
(SETQ anbnmNewTensorMonsAccess NIL) )) |
| 314 |
|
| 315 |
|
| 316 |
(ON RAISE) |