001 /*
002 * $Id: SyzygyAbstract.java 3584 2011-03-26 11:39:39Z kredel $
003 */
004
005 package edu.jas.gbmod;
006
007
008 import java.io.Serializable;
009 import java.util.ArrayList;
010 import java.util.Iterator;
011 import java.util.List;
012 import java.util.Map;
013
014 import org.apache.log4j.Logger;
015
016 import edu.jas.gb.ExtendedGB;
017 import edu.jas.gb.GroebnerBase;
018 import edu.jas.gb.Reduction;
019 import edu.jas.gb.ReductionSeq;
020 import edu.jas.gbufd.GBFactory;
021 import edu.jas.poly.ExpVector;
022 import edu.jas.poly.GenPolynomial;
023 import edu.jas.poly.GenPolynomialRing;
024 import edu.jas.poly.ModuleList;
025 import edu.jas.poly.PolynomialList;
026 import edu.jas.structure.GcdRingElem;
027 import edu.jas.structure.RingElem;
028 import edu.jas.vector.BasicLinAlg;
029 import edu.jas.vector.GenVector;
030 import edu.jas.vector.GenVectorModul;
031
032
033 /**
034 * SyzygyAbstract class. Implements Syzygy computations and tests.
035 * @param <C> coefficient type
036 * @author Heinz Kredel
037 */
038
039 public class SyzygyAbstract<C extends GcdRingElem<C>> implements Syzygy<C> {
040
041
042 private static final Logger logger = Logger.getLogger(SyzygyAbstract.class);
043
044
045 private final boolean debug = logger.isDebugEnabled();
046
047
048 /**
049 * Reduction engine.
050 */
051 protected Reduction<C> red;
052
053
054 /**
055 * Linear algebra engine.
056 */
057 protected BasicLinAlg<GenPolynomial<C>> blas;
058
059
060 /**
061 * Constructor.
062 */
063 public SyzygyAbstract() {
064 red = new ReductionSeq<C>();
065 blas = new BasicLinAlg<GenPolynomial<C>>();
066 //gb = new GroebnerBaseSeqPairSeq<C>();
067 //gb = new GroebnerBaseSeq<C>();
068 //gb = GBFactory. getImplementation();
069 }
070
071
072 /**
073 * Syzygy module from Groebner base. F must be a Groebner base.
074 * @param F a Groebner base.
075 * @return syz(F), a basis for the module of syzygies for F.
076 */
077 public List<List<GenPolynomial<C>>> zeroRelations(List<GenPolynomial<C>> F) {
078 return zeroRelations(0, F);
079 }
080
081
082 /**
083 * Syzygy module from Groebner base. F must be a Groebner base.
084 * @param modv number of module variables.
085 * @param F a Groebner base.
086 * @return syz(F), a basis for the module of syzygies for F.
087 */
088 public List<List<GenPolynomial<C>>> zeroRelations(int modv, List<GenPolynomial<C>> F) {
089 List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
090 if (F == null) {
091 return Z;
092 }
093 GenVectorModul<GenPolynomial<C>> mfac = null;
094 int i = 0;
095 while (mfac == null && i < F.size()) {
096 GenPolynomial<C> p = F.get(i);
097 if (p != null) {
098 mfac = new GenVectorModul<GenPolynomial<C>>(p.ring, F.size());
099 }
100 }
101 if (mfac == null) {
102 return Z;
103 }
104 GenVector<GenPolynomial<C>> v = mfac.fromList(F);
105 //System.out.println("F = " + F + " v = " + v);
106 return zeroRelations(modv, v);
107 }
108
109
110 /**
111 * Syzygy module from Groebner base. v must be a Groebner base.
112 * @param modv number of module variables.
113 * @param v a Groebner base.
114 * @return syz(v), a basis for the module of syzygies for v.
115 */
116 public List<List<GenPolynomial<C>>> zeroRelations(int modv, GenVector<GenPolynomial<C>> v) {
117
118 List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
119
120 GenVectorModul<GenPolynomial<C>> mfac = v.modul;
121 List<GenPolynomial<C>> F = v.val;
122 GenVector<GenPolynomial<C>> S = mfac.getZERO();
123 GenPolynomial<C> pi, pj, s, h, zero;
124 zero = mfac.coFac.getZERO();
125 for (int i = 0; i < F.size(); i++) {
126 pi = F.get(i);
127 for (int j = i + 1; j < F.size(); j++) {
128 pj = F.get(j);
129 //logger.info("p"+i+", p"+j+" = " + pi + ", " +pj);
130
131 if (!red.moduleCriterion(modv, pi, pj)) {
132 continue;
133 }
134 // if ( ! red.criterion4( pi, pj ) ) { continue; }
135 List<GenPolynomial<C>> row = S.clone().val;
136
137 s = red.SPolynomial(row, i, pi, j, pj);
138 if (s.isZERO()) {
139 Z.add(row);
140 continue;
141 }
142
143 h = red.normalform(row, F, s);
144 if (!h.isZERO()) {
145 throw new RuntimeException("Syzygy no GB");
146 }
147 if (debug) {
148 logger.info("row = " + row.size());
149 }
150 Z.add(row);
151 }
152 }
153 return Z;
154 }
155
156
157 /**
158 * Syzygy module from module Groebner base. M must be a module Groebner
159 * base.
160 * @param M a module Groebner base.
161 * @return syz(M), a basis for the module of syzygies for M.
162 */
163 public ModuleList<C> zeroRelations(ModuleList<C> M) {
164 ModuleList<C> N = M;
165 if (M == null || M.list == null) {
166 return N;
167 }
168 if (M.rows == 0 || M.cols == 0) {
169 return N;
170 }
171 GenPolynomial<C> zero = M.ring.getZERO();
172 //System.out.println("zero = " + zero);
173
174 //ModuleList<C> Np = null;
175 PolynomialList<C> F = M.getPolynomialList();
176 int modv = M.cols; // > 0
177 //System.out.println("modv = " + modv);
178 List<List<GenPolynomial<C>>> G = zeroRelations(modv, F.list);
179 if (G == null) {
180 return N;
181 }
182 List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
183 for (int i = 0; i < G.size(); i++) {
184 //F = new PolynomialList(F.ring,(List)G.get(i));
185 List<GenPolynomial<C>> Gi = G.get(i);
186 List<GenPolynomial<C>> Zi = new ArrayList<GenPolynomial<C>>();
187 // System.out.println("\nG("+i+") = " + G.get(i));
188 for (int j = 0; j < Gi.size(); j++) {
189 //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
190 GenPolynomial<C> p = Gi.get(j);
191 if (p != null) {
192 Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
193 int s = 0;
194 for (GenPolynomial<C> vi : r.values()) {
195 Zi.add(vi);
196 s++;
197 }
198 if (s == 0) {
199 Zi.add(zero);
200 } else if (s > 1) { // will not happen
201 System.out.println("p = " + p);
202 System.out.println("map(" + i + "," + j + ") = " + r + ", size = " + r.size());
203 throw new RuntimeException("Map.size() > 1 = " + r.size());
204 }
205 }
206 }
207 //System.out.println("\nZ("+i+") = " + Zi);
208 Z.add(Zi);
209 }
210 N = new ModuleList<C>(M.ring, Z);
211 //System.out.println("\n\nN = " + N);
212 return N;
213 }
214
215
216 /**
217 * Test if sysygy.
218 * @param Z list of sysygies.
219 * @param F a polynomial list.
220 * @return true, if Z is a list of syzygies for F, else false.
221 */
222
223 public boolean isZeroRelation(List<List<GenPolynomial<C>>> Z, List<GenPolynomial<C>> F) {
224 for (List<GenPolynomial<C>> row : Z) {
225 GenPolynomial<C> p = blas.scalarProduct(row, F);
226 if (p == null) {
227 continue;
228 }
229 if (!p.isZERO()) {
230 logger.info("is not ZeroRelation = " + p.toString(p.ring.getVars()));
231 logger.info("row = " + row);
232 //logger.info("F = " + F);
233 return false;
234 }
235 }
236 return true;
237 }
238
239
240 /**
241 * Test if sysygy of modules.
242 * @param Z list of sysygies.
243 * @param F a module list.
244 * @return true, if Z is a list of syzygies for F, else false.
245 */
246
247 public boolean isZeroRelation(ModuleList<C> Z, ModuleList<C> F) {
248 if (Z == null || Z.list == null) {
249 return true;
250 }
251 for (List<GenPolynomial<C>> row : Z.list) {
252 List<GenPolynomial<C>> zr = blas.leftScalarProduct(row, F.list);
253 if (!blas.isZero(zr)) {
254 logger.info("is not ZeroRelation (" + zr.size() + ") = " + zr);
255 return false;
256 }
257 }
258 return true;
259 }
260
261
262 /**
263 * Resolution of a module. Only with direct GBs.
264 * @param M a module list of a Groebner basis.
265 * @return a resolution of M.
266 */
267 public List<ResPart<C>> resolution(ModuleList<C> M) {
268 List<ResPart<C>> R = new ArrayList<ResPart<C>>();
269 ModuleList<C> MM = M;
270 ModuleList<C> GM;
271 ModuleList<C> Z;
272 ModGroebnerBase<C> mbb = new ModGroebnerBaseAbstract<C>(M.ring.coFac);
273 while (true) {
274 GM = mbb.GB(MM);
275 Z = zeroRelations(GM);
276 R.add(new ResPart<C>(MM, GM, Z));
277 if (Z == null || Z.list == null || Z.list.size() == 0) {
278 break;
279 }
280 MM = Z;
281 }
282 return R;
283 }
284
285
286 /**
287 * Resolution of a polynomial list. Only with direct GBs.
288 * @param F a polynomial list of a Groebner basis.
289 * @return a resolution of F.
290 */
291 public List // <ResPart<C>|ResPolPart<C>>
292 resolution(PolynomialList<C> F) {
293 List<List<GenPolynomial<C>>> Z;
294 ModuleList<C> Zm;
295 List<GenPolynomial<C>> G;
296 PolynomialList<C> Gl;
297
298 GroebnerBase<C> gb = GBFactory.getImplementation(F.ring.coFac);
299 G = gb.GB(F.list);
300 Z = zeroRelations(G);
301 Gl = new PolynomialList<C>(F.ring, G);
302 Zm = new ModuleList<C>(F.ring, Z);
303
304 List R = resolution(Zm); //// <ResPart<C>|ResPolPart<C>>
305 R.add(0, new ResPolPart<C>(F, Gl, Zm));
306 return R;
307 }
308
309
310 /**
311 * Resolution of a polynomial list.
312 * @param F a polynomial list of an arbitrary basis.
313 * @return a resolution of F.
314 */
315 public List // <ResPart<C>|ResPolPart<C>>
316 resolutionArbitrary(PolynomialList<C> F) {
317 List<List<GenPolynomial<C>>> Z;
318 ModuleList<C> Zm;
319 //List<GenPolynomial<C>> G;
320 PolynomialList<C> Gl = null;
321
322 //G = (new GroebnerBaseSeq<C>()).GB( F.list );
323 Z = zeroRelationsArbitrary(F.list);
324 //Gl = new PolynomialList<C>(F.ring, F.list);
325 Zm = new ModuleList<C>(F.ring, Z);
326
327 List R = resolutionArbitrary(Zm); //// <ResPart<C>|ResPolPart<C>>
328 R.add(0, new ResPolPart<C>(F, Gl, Zm));
329 return R;
330 }
331
332
333 /**
334 * Resolution of a module.
335 * @param M a module list of an arbitrary basis.
336 * @return a resolution of M.
337 */
338 public List<ResPart<C>> resolutionArbitrary(ModuleList<C> M) {
339 List<ResPart<C>> R = new ArrayList<ResPart<C>>();
340 ModuleList<C> MM = M;
341 ModuleList<C> GM = null;
342 ModuleList<C> Z;
343 //ModGroebnerBase<C> mbb = new ModGroebnerBaseAbstract<C>(M.ring.coFac);
344 while (true) {
345 //GM = mbb.GB(MM);
346 Z = zeroRelationsArbitrary(MM);
347 R.add(new ResPart<C>(MM, GM, Z));
348 if (Z == null || Z.list == null || Z.list.size() == 0) {
349 break;
350 }
351 MM = Z;
352 }
353 return R;
354 }
355
356
357 /**
358 * Syzygy module from arbitrary base.
359 * @param F a polynomial list.
360 * @return syz(F), a basis for the module of syzygies for F.
361 */
362 public List<List<GenPolynomial<C>>> zeroRelationsArbitrary(List<GenPolynomial<C>> F) {
363 return zeroRelationsArbitrary(0, F);
364 }
365
366
367 /**
368 * Syzygy module from arbitrary base.
369 * @param modv number of module variables.
370 * @param F a polynomial list.
371 * @return syz(F), a basis for the module of syzygies for F.
372 */
373 public List<List<GenPolynomial<C>>> zeroRelationsArbitrary(int modv, List<GenPolynomial<C>> F) {
374
375 if (F == null) {
376 return zeroRelations(modv, F);
377 }
378 if (F.size() <= 1) {
379 return zeroRelations(modv, F);
380 }
381 GroebnerBase<C> gb = GBFactory.getImplementation(F.get(0).ring.coFac);
382 final int lenf = F.size();
383 ExtendedGB<C> exgb = gb.extGB(F);
384 if (debug) {
385 logger.debug("exgb = " + exgb);
386 if (!gb.isReductionMatrix(exgb)) {
387 logger.error("is reduction matrix ? false");
388 }
389 }
390 List<GenPolynomial<C>> G = exgb.G;
391 List<List<GenPolynomial<C>>> G2F = exgb.G2F;
392 List<List<GenPolynomial<C>>> F2G = exgb.F2G;
393
394 List<List<GenPolynomial<C>>> sg = zeroRelations(modv, G);
395 GenPolynomialRing<C> ring = G.get(0).ring;
396 ModuleList<C> S = new ModuleList<C>(ring, sg);
397 if (debug) {
398 logger.debug("syz = " + S);
399 if (!isZeroRelation(sg, G)) {
400 logger.error("is syzygy ? false");
401 }
402 }
403 List<List<GenPolynomial<C>>> sf;
404 sf = new ArrayList<List<GenPolynomial<C>>>(sg.size());
405 //List<GenPolynomial<C>> row;
406 for (List<GenPolynomial<C>> r : sg) {
407 Iterator<GenPolynomial<C>> it = r.iterator();
408 Iterator<List<GenPolynomial<C>>> jt = G2F.iterator();
409
410 List<GenPolynomial<C>> rf;
411 rf = new ArrayList<GenPolynomial<C>>(lenf);
412 for (int m = 0; m < lenf; m++) {
413 rf.add(ring.getZERO());
414 }
415 while (it.hasNext() && jt.hasNext()) {
416 GenPolynomial<C> si = it.next();
417 List<GenPolynomial<C>> ai = jt.next();
418 //System.out.println("si = " + si);
419 //System.out.println("ai = " + ai);
420 if (si == null || ai == null) {
421 continue;
422 }
423 List<GenPolynomial<C>> pi = blas.scalarProduct(si, ai);
424 //System.out.println("pi = " + pi);
425 rf = blas.vectorAdd(rf, pi);
426 }
427 if (it.hasNext() || jt.hasNext()) {
428 logger.error("zeroRelationsArbitrary wrong sizes");
429 }
430 //System.out.println("\nrf = " + rf + "\n");
431 sf.add(rf);
432 }
433 List<List<GenPolynomial<C>>> M;
434 M = new ArrayList<List<GenPolynomial<C>>>(lenf);
435 for (List<GenPolynomial<C>> r : F2G) {
436 Iterator<GenPolynomial<C>> it = r.iterator();
437 Iterator<List<GenPolynomial<C>>> jt = G2F.iterator();
438
439 List<GenPolynomial<C>> rf;
440 rf = new ArrayList<GenPolynomial<C>>(lenf);
441 for (int m = 0; m < lenf; m++) {
442 rf.add(ring.getZERO());
443 }
444 while (it.hasNext() && jt.hasNext()) {
445 GenPolynomial<C> si = it.next();
446 List<GenPolynomial<C>> ai = jt.next();
447 //System.out.println("si = " + si);
448 //System.out.println("ai = " + ai);
449 if (si == null || ai == null) {
450 continue;
451 }
452 List<GenPolynomial<C>> pi = blas.scalarProduct(ai, si);
453 //System.out.println("pi = " + pi);
454 rf = blas.vectorAdd(rf, pi);
455 }
456 if (it.hasNext() || jt.hasNext()) {
457 logger.error("zeroRelationsArbitrary wrong sizes");
458 }
459 //System.out.println("\nMg Mf = " + rf + "\n");
460 M.add(rf);
461 }
462 //ModuleList<C> ML = new ModuleList<C>( ring, M );
463 //System.out.println("syz ML = " + ML);
464 // debug only:
465 /* not true in general
466 List<GenPolynomial<C>> F2 = new ArrayList<GenPolynomial<C>>( F.size() );
467 for ( List<GenPolynomial<C>> rr: M ) {
468 GenPolynomial<C> rrg = blas.scalarProduct( F, rr );
469 F2.add( rrg );
470 }
471 PolynomialList<C> pF = new PolynomialList<C>( ring, F );
472 PolynomialList<C> pF2 = new PolynomialList<C>( ring, F2 );
473 if ( ! pF.equals( pF2 ) ) {
474 logger.error("is FAB = F ? false");
475 }
476 */
477 int sflen = sf.size();
478 List<List<GenPolynomial<C>>> M2;
479 M2 = new ArrayList<List<GenPolynomial<C>>>(lenf);
480 int i = 0;
481 for (List<GenPolynomial<C>> ri : M) {
482 List<GenPolynomial<C>> r2i;
483 r2i = new ArrayList<GenPolynomial<C>>(ri.size());
484 int j = 0;
485 for (GenPolynomial<C> rij : ri) {
486 GenPolynomial<C> p = null;
487 if (i == j) {
488 p = ring.getONE().subtract(rij);
489 } else {
490 if (rij != null) {
491 p = rij.negate();
492 }
493 }
494 r2i.add(p);
495 j++;
496 }
497 M2.add(r2i);
498 if (!blas.isZero(r2i)) {
499 sf.add(r2i);
500 }
501 i++;
502 }
503 if (debug) {
504 ModuleList<C> M2L = new ModuleList<C>(ring, M2);
505 logger.debug("syz M2L = " + M2L);
506 ModuleList<C> SF = new ModuleList<C>(ring, sf);
507 logger.debug("syz sf = " + SF);
508 logger.debug("#syz " + sflen + ", " + sf.size());
509 if (!isZeroRelation(sf, F)) {
510 logger.error("is syz sf ? false");
511 }
512 }
513 return sf;
514 }
515
516
517 /**
518 * Syzygy module from arbitrary module base.
519 * @param M an arbitrary module base.
520 * @return syz(M), a basis for the module of syzygies for M.
521 */
522 public ModuleList<C> zeroRelationsArbitrary(ModuleList<C> M) {
523 ModuleList<C> N = M;
524 if (M == null || M.list == null) {
525 return N;
526 }
527 if (M.rows == 0 || M.cols == 0) {
528 return N;
529 }
530 GenPolynomial<C> zero = M.ring.getZERO();
531 //System.out.println("zero = " + zero);
532
533 //ModuleList<C> Np = null;
534 PolynomialList<C> F = M.getPolynomialList();
535 int modv = M.cols; // > 0
536 //System.out.println("modv = " + modv);
537 List<List<GenPolynomial<C>>> G = zeroRelationsArbitrary(modv, F.list);
538 if (G == null) {
539 return N;
540 }
541 List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
542 for (int i = 0; i < G.size(); i++) {
543 //F = new PolynomialList(F.ring,(List)G.get(i));
544 List<GenPolynomial<C>> Gi = G.get(i);
545 List<GenPolynomial<C>> Zi = new ArrayList<GenPolynomial<C>>();
546 // System.out.println("\nG("+i+") = " + G.get(i));
547 for (int j = 0; j < Gi.size(); j++) {
548 //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
549 GenPolynomial<C> p = Gi.get(j);
550 if (p != null) {
551 Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
552 int s = 0;
553 for (GenPolynomial<C> vi : r.values()) {
554 Zi.add(vi);
555 s++;
556 }
557 if (s == 0) {
558 Zi.add(zero);
559 } else if (s > 1) { // will not happen
560 System.out.println("p = " + p);
561 System.out.println("map(" + i + "," + j + ") = " + r + ", size = " + r.size());
562 throw new RuntimeException("Map.size() > 1 = " + r.size());
563 }
564 }
565 }
566 //System.out.println("\nZ("+i+") = " + Zi);
567 Z.add(Zi);
568 }
569 N = new ModuleList<C>(M.ring, Z);
570 //System.out.println("\n\nN = " + N);
571 return N;
572 }
573
574 }
575
576
577 /**
578 * Container for module resolution components.
579 * @param <C> coefficient type
580 */
581 class ResPart<C extends RingElem<C>> implements Serializable {
582
583
584 public final ModuleList<C> module;
585
586
587 public final ModuleList<C> GB;
588
589
590 public final ModuleList<C> syzygy;
591
592
593 /**
594 * ResPart.
595 * @param m a module list.
596 * @param g a module list GB.
597 * @param z a syzygy module list.
598 */
599 public ResPart(ModuleList<C> m, ModuleList<C> g, ModuleList<C> z) {
600 module = m;
601 GB = g;
602 syzygy = z;
603 }
604
605
606 /**
607 * toString.
608 */
609 @Override
610 public String toString() {
611 StringBuffer s = new StringBuffer("ResPart(\n");
612 s.append("module = " + module);
613 s.append("\n GB = " + GB);
614 s.append("\n syzygy = " + syzygy);
615 s.append(")");
616 return s.toString();
617 }
618 }
619
620
621 /**
622 * Container for polynomial resolution components.
623 */
624 class ResPolPart<C extends RingElem<C>> implements Serializable {
625
626
627 public final PolynomialList<C> ideal;
628
629
630 public final PolynomialList<C> GB;
631
632
633 public final ModuleList<C> syzygy;
634
635
636 /**
637 * ResPolPart.
638 * @param m a polynomial list.
639 * @param g a polynomial list GB.
640 * @param z a syzygy module list.
641 */
642 public ResPolPart(PolynomialList<C> m, PolynomialList<C> g, ModuleList<C> z) {
643 ideal = m;
644 GB = g;
645 syzygy = z;
646 }
647
648
649 /**
650 * toString.
651 */
652 @Override
653 public String toString() {
654 StringBuffer s = new StringBuffer("ResPolPart(\n");
655 s.append("ideal = " + ideal);
656 s.append("\n GB = " + GB);
657 s.append("\n syzygy = " + syzygy);
658 s.append(")");
659 return s.toString();
660 }
661
662 }