Debian Codegraph @

tests/prep/0206tests/tmpexport/chrecord.sl

raw
1 % Chains in anick.
2
3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
4 %% Copyright (C) 1996
5 %% Joergen Backelin and Alexander Podoplelov
6 %%
7 %% Bergman and Anick are distributed in the hope that they will be
8 %% useful, but WITHOUT ANY WARRANTY. No author or distributor
9 %% accepts responsibility to anyone for the consequences of using them
10 %% or for whether they serve any particular purpose or work at all,
11 %% unless (s)he says so in writing. Refer to the Bergman General Public
12 %% License for full details.
13
14 %% Everyone is granted permission to copy, modify and redistribute
15 %% bergman, but only under the conditions described in the
16 %% Bergman General Public License. A copy of this license is
17 %% supposed to have been given to you along with bergman so you
18 %% can know your rights and responsibilities. It should be in a
19 %% file named copyright. Among other things, the copyright notice
20 %% and this notice must be preserved on all copies.
21 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
22
23
24 % CHANGES:
25
26 % $Log: chrecord.sl,v $
27 % Revision 1.12 1999/11/19 11:38:33 joeb
28 % (Minor corrections to the preceeding commitment.)
29 %
30 % Revision 1.11 1999/11/15 16:26:14 joeb
31 % Added the "length -1 chain" anUNITCHAIN representing the generator
32 % of the homological degree 0 generator. Used this in order create
33 % correct differentials of the 0-chains (for output purposes). Also
34 % entered a anUNITCHAIN clause into PRINTCHAIN, making this slightly
35 % slower as well. /JoeB
36 %
37 % Revision 1.10 1999/11/05 15:07:10 joeb
38 % Changed MONP to MON!?
39 %
40 % Revision 1.9 1998/11/07 21:37:11 sanya
41 % Mode settings handling are added
42 %
43 % Revision 1.8 1998/11/07 17:11:33 joeb
44 % Added anExtractChnModes/JoeB
45 %
46 % Revision 1.7 1998/11/07 17:03:47 sanya
47 % Modifications for modes of Chn
48 %
49 % Revision 1.6 1998/11/05 15:48:27 sanya
50 % Name changes of some functions
51 %
52 % Revision 1.5 1998/11/04 15:50:46 joeb
53 % *** empty log message ***
54 %
55 % Revision 1.4 1998/11/04 13:53:16 joeb
56 % Updated chrecord type documentation
57 %
58 % Revision 1.3 1998/11/03 14:00:54 sanya
59 % Modification of some source modules so that it is corresponds logically
60 % more to advanced and developer guides. The TeX documentation is updated.
61 %
62 % Revision 1.2 1998/10/24 14:50:04 sanya
63 % A copy of all the anick source files from Joergen's directory.
64 % These files are used in compilcation of the latest version of BERGMAN.
65 %
66 %Revision 1.2 1997/02/14 11:54:19 joeb
67 %Corrected name of 'redand' variable to 'quotpol' variable,
68 %and added a PreenQPol (as a preparation for positive
69 %characteristics coefficient domains)/JoeB
70 %
71
72 % Created 1996-06-23.
73
74
75 % Chains should contain or make accessible all relevant
76 % informations about the 'chains', i.e. the generators in the Anick
77 % resolution. They should only be accessed by means of the procedures
78 % and macros given the protocol.
79 % The macros are found on the file anmacros.sl (which should be read
80 % in together with the bergman source file macros.sl at the time of
81 % compilation of this and other anick source files).
82
83 % Import: Mon!=, Mon!?, LeftMonFactorP, PMon, MonIntern1, MONPRINT,
84 % GETVARNO, MONINTERN, MODULEOBJECT; MONONE, NALGGEN, NMODGEN.
85
86 % Export:
87
88 (OFF RAISE)
89
90 (GLOBAL '(anchEdgeString!* !*anchPrintEdgeString anCHAINS
91 anNEWCHAINS MONONE !*anDEBUG REDANDCOEFFONE ModeProperties!*
92 anUNITCHAIN NALGGEN NMODGEN NLMODGEN NRMODGEN
93 anbnmChainStartIndexLimits anbnmChainEndIndexLimits))
94
95 % (PUT 'ModeProperties!* '!*anchPrintEdgeString 'anFLIPFLAG)
96 % (PUT 'ModeProperties!* 'anchEdgeString!* 'anASSIGNSTRING)
97
98 % In this implementation, a chain (Chn) is represented as dotted
99 % pair of dotted pairs: Chn = ( (Vx . Chn1) . ( (n . df) . ChnList) ),
100 % where Vx is the last vertex of the chain seen as a path in the graph,
101 % represented as an augmented monomial; n is the length of Chn; Chn1 is
102 % the "preceeding chain", i.e. the chain representing
103 % the unique chain of length n-1 which is a left factor of the chain
104 % represented by Chn; df either is NIL or is the calculated differential
105 % of the chain, represented by a semi-distributed tensor
106 % polynomial; and ChnList is a list of succeeding chains, i.e.,
107 % of chains representing chains of length n+1, eac of which has
108 % the chain represented by Chn as a left factor.
109
110 % (As usual, the individual parts of chains should be accessed
111 % from other parts of anick only by the protocolled macros and
112 % procedures for this purpose. The internal representation may change
113 % without notice.)
114
115
116 % If the chain chn is an n-chain then this returns a dotted pair
117 % (chn1 . augmon1), where the n+1 -chain "chn1" and the augmented monomial
118 % "augmon1" fulfil chn * augmon = chn1 * augmon1. It returns an error if
119 % there is no n+1 -chain left factor of chn * augmon. (IS THIS NECESSARY?)
120 % Meaning of prog variables: List of chains (prolonging chn);
121 % Last vertex of the first of these; Right quotient pure polynomial.
122
123 (DE anPROLONGCHAIN (chn augmon)
124 (PROG (lcr vx rq)
125 (COND (!*anDEBUG (PRIN2 "anPROLONGCHAIN <-- ")
126 (PRINTCHAIN chn) (PRIN2 ":") (MONPRINT augmon) (TERPRI)))
127 (SETQ lcr (anChn2HiChns chn))
128 Ml (COND ((NOT lcr)
129 (ERROR 1001 "No prolongation found in anPROLONGCHAIN"))
130 ((Mon!= (SETQ vx (anChn2LastVx (CAR lcr))) augmon)
131 (COND (!*anDEBUG (PRIN2 "anPROLONGCHAIN --> ")
132 (PRINTCHAIN (CAR lcr)) (PRIN2 ":") (PRINT 1)))
133 (RETURN (CONS (CAR lcr) MONONE)))
134 ((SETQ rq (LeftMonFactorP (PMon vx) (PMon augmon)))
135 (SETQ vx (MonIntern1 rq))
136 (COND (!*anDEBUG (PRIN2 "anPROLONGCHAIN --> ")
137 (PRINTCHAIN (CAR lcr)) (PRIN2 ":")
138 (MONPRINT vx) (TERPRI)))
139 (RETURN (CONS (CAR lcr) vx))
140 %(RETURN (CONS (CAR lcr) (MonIntern1 rq)))
141 ))
142 (SETQ lcr (CDR lcr))
143 (GO Ml) ))
144
145
146 % Print the vertices of the chain in a row. The vertices are printed
147 % as strings of variable names. If !*anchPrintEdgeString is ON, then
148 % print the value of anchEdgeString!* between them.
149 % Meaning of PROG variables: List of vertices; (Previous) chain.
150
151 (DE PRINTCHAIN (chn)
152 (PROG (lv pc)
153 (COND ((anChn!= chn anUNITCHAIN)
154 (PRIN2 1)
155 (RETURN 1)))
156 (SETQ lv (NCONS (anChn2LastVx (SETQ pc chn))))
157 Fl (COND ((NOT (ZEROP (anChn2Length pc)))
158 (SETQ lv (CONS (anChn2LastVx
159 (SETQ pc (anChn2LowerChn pc)))
160 lv))
161 (GO Fl)))
162 (MONPRINT (CAR lv))
163 Sl (COND ((SETQ lv (CDR lv))
164 (COND ( !*anchPrintEdgeString (PRIN2 anchEdgeString!*)))
165 (MONPRINT (CAR lv))
166 (GO Sl))) ))
167
168
169 % Depending on the object type mode, there maay be restrictions on
170 % which of the potentially possibe chains actually to construct. There
171 % should be rich possibilities to handle this; whence the input
172 % procedures should be FEXPRs.
173 % Meaning of PROG variables: Lower Limit, Higher Limit (inclusive).
174
175 %# SETCHAINSTARTS (any) : - ; FEXPR
176 (DF SETCHAINSTARTS (ints)
177 (PROG (ll hl)
178 (COND ((OR (NOT (PAIRP ints))
179 (NOT (PAIRP (CDR ints)))
180 (NOT (FIXP (SETQ ll (EVAL (CAR ints)))))
181 (NOT (FIXP (SETQ hl (EVAL (CADR ints)))))
182 (LESSP hl ll)
183 (LESSP ll 0))
184 (ERROR 99 ints " bad input to SETCHAINSTARTS")))
185 (SETQ anbnmChainStartIndexLimits (CONS ll hl)) ))
186
187 %# SETCHAINENDS (any) : - ; FEXPR
188 (DF SETCHAINENDS (ints)
189 (PROG (ll hl)
190 (COND ((OR (NOT (PAIRP ints))
191 (NOT (PAIRP (CDR ints)))
192 (NOT (FIXP (SETQ ll (EVAL (CAR ints)))))
193 (NOT (FIXP (SETQ hl (EVAL (CADR ints)))))
194 (LESSP hl ll)
195 (LESSP ll 0))
196 (ERROR 99 ints " bad input to SETCHAINENDS")))
197 (SETQ anbnmChainEndIndexLimits (CONS ll hl)) ))
198
199
200 % Returns a list (chn1, chn2, ...) of new chains from an old
201 % one, chn, and a total degree different number, degdiff. ch1, ch2 ...
202 % represent the chains of length = 1 + length[chn] and
203 % total-degree = degdiff + totaldegree[chn], and with chn as a left factor.
204 % Meaning of prog values: Return list; Input last vertex following
205 % vertices list position; New chain length.
206
207 (DE anRingCONSTRUCTNEWCHAINS (chn degdiff)
208 (PROG (rt ip nl)
209 % (COND (!*anDEBUG (PRIN2 "anCONSTRUCTNEWCHAINS<--")
210 % (PRINTCHAIN chn) (PRIN2 " degdiff = ") (PRINT degdiff)))
211 (SETQ rt (NCONS NIL))
212 (SETQ ip (LGET (Mplst (anChn2LastVx chn)) 'InvRecDef))
213 (SETQ nl (ADD1 (anChn2Length chn)))
214 Ml (COND (ip
215 (COND ((AND (Mon!? (CAR ip))
216 (EQN degdiff (TOTALDEGREE (PMon (CAR ip)))))
217 (ancrInsertChn (ancrMakeChain chn
218 NIL
219 (CAR ip)
220 NIL
221 nl)
222 rt)))
223 (SETQ ip (CDR ip))
224 (GO Ml))
225 ((NULL (SETQ rt (CDR rt)))
226 (RETURN NIL)))
227
228 % Insert the new chains at chn and in anNEWCHAINS:
229 (anSETHIGHERCHAINS chn (APPEND rt (anChn2HiChns chn)))
230 (COND ((NULL (CDR (SETQ ip anNEWCHAINS)))
231 (COND (!*anDEBUG (PRIN2T "anCONSTRUCTNEWCHAINS--> 1")))
232 (RETURN (RPLACD ip rt))))
233 (SETQ nl (CAR rt))
234 Sl (COND ((anLESSCHAIN nl (CADR ip))
235 (COND (!*anDEBUG (PRIN2T "anCONSTRUCTNEWCHAINS--> 2")))
236 (RETURN (RPLACD ip (NCONC rt (CDR ip)))))
237 ((CDR (SETQ ip (CDR ip)))
238 (GO Sl)))
239 (RPLACD ip rt) ))
240
241 % The only difference in the TwoModules variant is, that here
242 % we must explicitly test a potential new chain in order to
243 % ensure that it indeed ends in ring variables.
244
245
246 (DE anTwoModulesCONSTRUCTNEWCHAINS (chn degdiff)
247 (PROG (rt ip nl)
248 % (COND (!*anDEBUG (PRIN2 "anCONSTRUCTNEWCHAINS<--")
249 % (PRINTCHAIN chn) (PRIN2 " degdiff = ") (PRIN2 degdiff)
250 % (PRIN2 "; NALGGEN = ") (PRINT NALGGEN)))
251 (SETQ rt (NCONS NIL))
252 (SETQ ip (LGET (Mplst (anChn2LastVx chn)) 'InvRecDef))
253 (SETQ nl (ADD1 (anChn2Length chn)))
254 Ml (COND (ip
255 (COND ((AND (Mon!? (CAR ip))
256 (EQN degdiff (TOTALDEGREE (PMon (CAR ip))))
257 (NOT (BMI!< (CDR anbnmChainEndIndexLimits)
258 (MonLeastSignifVar (CAR ip)))))
259 (ancrInsertChn (ancrMakeChain chn
260 NIL
261 (CAR ip)
262 NIL
263 nl)
264 rt)))
265 (SETQ ip (CDR ip))
266 (GO Ml))
267 ((NULL (SETQ rt (CDR rt)))
268 (RETURN NIL)))
269
270 % Insert the new chains at chn and in anNEWCHAINS:
271 (anSETHIGHERCHAINS chn (APPEND rt (anChn2HiChns chn)))
272 (COND ((NULL (CDR (SETQ ip anNEWCHAINS)))
273 % (COND (!*anDEBUG (PRIN2T "anCONSTRUCTNEWCHAINS--> 1")))
274 (RETURN (RPLACD ip rt))))
275 (SETQ nl (CAR rt))
276 Sl (COND ((anLESSCHAIN nl (CADR ip))
277 % (COND (!*anDEBUG (PRIN2T "anCONSTRUCTNEWCHAINS--> 2")))
278 (RETURN (RPLACD ip (NCONC rt (CDR ip)))))
279 ((CDR (SETQ ip (CDR ip)))
280 (GO Sl)))
281 (RPLACD ip rt) ))
282
283
284
285 % This routine should be called before the calculation of the Anick
286 % resolution to construct the chains for the chains of length
287 % zero, as a list (in increasing order).
288 % Also construct the chain anUNITCHAIN of length -1.
289 % Mening of prog variables: Return list of chains; Variable index;
290 % Variable as a monomial; Differential.
291
292 (DE anCONSTRUCTZEROCHAINS ()
293 (PROG (rt vi vm df)
294 (SETQ vi (COND ((EQ (GETOBJECTTYPE) 'RING) (GETVARNO))
295 (T (CDR anbnmChainStartIndexLimits))))
296 (SETQ NALGGEN
297 (COND ((OR (EQ (GETOBJECTTYPE) 'TWOMODULES)
298 (EQ (GETOBJECTTYPE) 'MODULE)
299 (EQ (GETOBJECTTYPE) 'FACTORALGEBRA))
300 (SUB1 (CAR anbnmChainStartIndexLimits)))
301 (T 0)))
302 (SETQ anUNITCHAIN (ancrMakeChain NIL NIL MONONE NIL -1))
303 Ml (COND ((NOT (LESSP NALGGEN vi))
304 (RETURN (SETQ anCHAINS (NCONS (CONS 1 rt))))))
305 (SETQ df (anMakeNewSDP))
306 (anAppendSDPTail df
307 (anChn!&QPol2SDPTail
308 anUNITCHAIN
309 (Tm2QPol
310 (Cf!&Mon2Tm REDANDCOEFFONE
311 (SETQ vm
312 (MONINTERN (NCONS vi)))))))
313 (SETQ rt (CONS (ancrMakeChain anUNITCHAIN NIL vm df 0)
314 rt))
315 (SETQ vi (SUB1 vi))
316 (GO Ml) ))
317
318
319 % Converts data from one structure format to another - from the leading
320 % monomial of a new Groebner basis element to a 1-chain. Also calculates
321 % the differential of the chain.
322 % Meaning of prog variables: Return chain differential; part thereof;
323 % return position; input position; new quotpol; new quotpol position;
324 % index of most significant variable; new index; input leading coefficient.
325
326 (DE anNEWGBELM2CHAIN (augmon)
327 (PROG (rt rp ip nq np ix ni ic)
328
329 % First calculate the differential.
330 (SETQ rp (SETQ rt (anMakeNewSDP)))
331 (SETQ ic (Lc (SETQ ip (PPol (Mpt augmon)))))
332 (SETQ ix (MonSignifVar (Lm ip)))
333 Ml (SETQ np (SETQ nq (Num!&Den2QPol REDANDCOEFFONE ic)))
334 Sl (ConcPol np (Cf!&Mon2Pol (RedorCoeff2RedandCoeff (Lc ip))
335 (RestOfMon (Lm ip))))
336 (COND ((AND (PolDecap ip)
337 (EQ (SETQ ni (MonSignifVar (Lm ip)))
338 ix))
339 (PolDecap np)
340 (GO Sl)))
341 (PreenQPol nq)
342 (anAppendSDPTail rp (anChn!&QPol2SDPTail (ancrIndex2Chn ix) nq))
343 (COND (ip
344 (anNextSDPTail rp)
345 (SETQ ix ni)
346 (GO Ml)))
347
348 % Now put rp := the leading 0-chain; create the new chain;
349 % and place it on rp.
350 (SETQ rt
351 (ancrMakeChain (SETQ rp (anSDP2NextChn rt))
352 NIL
353 (APol2Lm (anSDP2NextQPol rt))
354 rt
355 1))
356 (anSETHIGHERCHAINS rp (CONS rt (anChn2HiChns rp)))
357 (RETURN rt) ))
358
359
360 % Returns NIL if chn1 doesn't preceed chn2 in "monomial deglex" order.
361
362 (DE anLESSCHAIN (chn1 chn2)
363 (PROG (lg1 lg2 ncr)
364 (COND (!*anDEBUG (PRIN2 "anLESSCHAIN <-- ")
365 (PRINTCHAIN chn1) (PRIN2 ", ") (PRINTCHAIN chn2) (TERPRI)))
366 (COND ((anChn!= chn1 chn2)
367 (COND (!*anDEBUG (PRIN2T "anLESSCHAIN --> 1.")))
368 (RETURN NIL))
369 ((EQN (SETQ lg1 (anChn2Length chn1))
370 (SETQ lg2 (anChn2Length chn2)))
371 (RETURN (ancrLESSCHAIN1 chn1 chn2)))
372 ((LESSP lg1 lg2)
373 (SETQ ncr (anChn2LowerChn chn2))
374 (GO Sl)))
375 (SETQ ncr (anChn2LowerChn chn1))
376
377 Fl
378 (COND ((EQN (SETQ lg1 (SUB1 lg1)) lg2)
379 (RETURN (ancrLESSCHAIN1 ncr chn2))))
380 (SETQ ncr (anChn2LowerChn ncr))
381 (GO Fl)
382
383 Sl
384 (COND ((EQN (SETQ lg2 (SUB1 lg2)) lg1)
385 (RETURN (ancrLESSCHAIN1 chn1 ncr))))
386 (SETQ ncr (anChn2LowerChn ncr))
387 (GO Sl) ))
388
389
390 % AUXILIARIES:
391
392
393 (DE ancrLESSCHAIN1 (chn1 chn2)
394 (COND ((anChn!= (anChn2LowerChn chn1) (anChn2LowerChn chn2))
395 (COND (!*anDEBUG (PRIN2T "anLESSCHAIN --> 2.")))
396 (MONLESSP (PMon (anChn2LastVx chn1))
397 (PMon (anChn2LastVx chn2))))
398 (T
399 (ancrLESSCHAIN1 (anChn2LowerChn chn1)
400 (anChn2LowerChn chn2)))) )
401
402 (DE ancrIndex2Chn (ix)
403 (PROG (c0)
404 % ONLY FOR DEBUGGING; remove later:
405 (COND ((OR (ATOM anCHAINS) (ATOM (CAR anCHAINS))) (ERROR 1001 "anCHAINS improperly set for ancrIndex2Chn")))
406 (SETQ c0 (CDAR anCHAINS))
407 Ml % ONLY FOR DEBUGGING; remove later:
408 (COND ((NULL c0) (PRIN2 "***** ") (PRIN2T ix) (ERROR 1001 "bad input to ancrIndex2Chn")))
409 (COND ((EQ (MonSignifVar (anChn2LastVx (CAR c0))) ix)
410 (RETURN (CAR c0))))
411 (SETQ c0 (CDR c0))
412 (GO Ml) ))
413
414
415 (DE ancrInsertChn (chn auglchn)
416 (PROG (lcr)
417 (COND ((NOT (CDR (SETQ lcr auglchn)))
418 (RETURN (RPLACD lcr (NCONS chn)))))
419 Ml (COND ((anLESSCHAIN chn (CADR lcr))
420 (RETURN (RPLACD lcr (CONS chn (CDR lcr)))))
421 ((CDR (SETQ lcr (CDR lcr)))
422 (GO Ml)))
423 (RETURN (RPLACD lcr (NCONS chn))) ))
424
425
426 % Create a new chain out of the lower chain, the higher
427 % chains (or their position), the last vertex, the differential
428 % (or its position), and the length of the chain, in this order.
429
430 (DE ancrMakeChain (chn lchn vx df lg)
431 (CONS (CONS vx chn) (CONS (CONS lg df) lchn)))
432
433
434 % Mode settings.
435
436
437 % Sets value for anchEdgeString!* variable and returns its old one.
438 (DE SETEDGESTRING (strng)
439 (PROG (OldEStr)
440 (COND ((NOT (OR (STRINGP strng) (IDP strng)))
441 (ERROR 1011 "Bad input to SETEDGESTRING")))
442 (SETQ OldEStr anchEdgeString!*)
443 (SETQ anchEdgeString!* strng)
444 (ON PRINTEDGESTRING)
445 (RETURN OldEStr) ))
446
447 (SETEDGESTRING " ")
448
449 % Returns the value of string which is printed between chain vertexes.
450 (DE GETEDGESTRING () (PROGN anchEdgeString!*))
451
452 (DE SETEDGESTRINGPRINTING (b)
453 (PROG (rt)
454 (SETQ rt (GETEDGESTRINGPRINTING))
455 (COND (b (ON !*anchPrintEdgeString))
456 (T (OFF !*anchPrintEdgeString)))
457 (RETURN rt) ))
458
459 (DE GETEDGESTRINGPRINTING () (PROGN !*anchPrintEdgeString))
460
461 (DE anExtractChnModes ()
462 (LIST (LIST 'EDGE!-STRING (GETEDGESTRING))
463 (LIST 'EDGE!-STRING!-PRINTING (GETEDGESTRINGPRINTING)) ))
464
465 (ON RAISE)