Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gbufd;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.List;
011import java.util.Map;
012
013import org.apache.logging.log4j.LogManager;
014import org.apache.logging.log4j.Logger;
015
016import edu.jas.gb.Reduction;
017import edu.jas.gb.ReductionSeq;
018import edu.jas.gb.SolvableReduction;
019import edu.jas.gb.SolvableReductionSeq;
020import edu.jas.poly.ExpVector;
021import edu.jas.poly.GenPolynomial;
022import edu.jas.poly.GenSolvablePolynomial;
023import edu.jas.poly.GenSolvablePolynomialRing;
024import edu.jas.poly.ModuleList;
025import edu.jas.poly.PolynomialList;
026import edu.jas.structure.GcdRingElem;
027import edu.jas.structure.RingElem;
028import edu.jas.vector.BasicLinAlg;
029
030
031/**
032 * Syzygy abstract class for solvable polynomials. Implements Syzygy
033 * computations and tests.
034 * @param <C> coefficient type
035 * @author Heinz Kredel
036 */
037
038public abstract class SolvableSyzygyAbstract<C extends GcdRingElem<C>> implements SolvableSyzygy<C> {
039
040
041    private static final Logger logger = LogManager.getLogger(SolvableSyzygyAbstract.class);
042
043
044    private static final boolean debug = logger.isDebugEnabled();
045
046
047    /**
048     * Solvable reduction engine.
049     */
050    public final SolvableReduction<C> sred;
051
052
053    /**
054     * Reduction engine.
055     */
056    protected Reduction<C> red;
057
058
059    /**
060     * Linear algebra engine.
061     */
062    protected BasicLinAlg<GenPolynomial<C>> blas;
063    //protected BasicLinAlg<GenSolvablePolynomial<C>> blas;
064
065
066    /**
067     * Constructor.
068     */
069    public SolvableSyzygyAbstract() {
070        red = new ReductionSeq<C>();
071        sred = new SolvableReductionSeq<C>();
072        blas = new BasicLinAlg<GenPolynomial<C>>();
073        //blas = new BasicLinAlg<GenSolvablePolynomial<C>>();
074    }
075
076
077    /**
078     * Left syzygy for left Groebner base.
079     * @param F a Groebner base.
080     * @return leftSyz(F), a basis for the left module of syzygies for F.
081     */
082    public List<List<GenSolvablePolynomial<C>>> leftZeroRelations(List<GenSolvablePolynomial<C>> F) {
083        return leftZeroRelations(0, F);
084    }
085
086
087    /**
088     * Left syzygy for left Groebner base.
089     * @param modv number of module variables.
090     * @param F a Groebner base.
091     * @return leftSyz(F), a basis for the left module of syzygies for F.
092     */
093    public List<List<GenSolvablePolynomial<C>>> leftZeroRelations(int modv,
094                    List<GenSolvablePolynomial<C>> F) {
095        List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>();
096        ArrayList<GenSolvablePolynomial<C>> S = new ArrayList<GenSolvablePolynomial<C>>(F.size());
097        for (int i = 0; i < F.size(); i++) {
098            S.add(null);
099        }
100        GenSolvablePolynomial<C> pi, pj, s, h, zero;
101        zero = null;
102        for (int i = 0; i < F.size(); i++) {
103            pi = F.get(i);
104            if (zero == null) {
105                zero = pi.ring.getZERO();
106            }
107            for (int j = i + 1; j < F.size(); j++) {
108                pj = F.get(j);
109                //logger.info("p{}, p{} = {}", j, i, pj);
110
111                if (!red.moduleCriterion(modv, pi, pj)) {
112                    continue;
113                }
114                // if ( ! red.criterion4( pi, pj ) ) continue;
115                List<GenSolvablePolynomial<C>> row = new ArrayList<GenSolvablePolynomial<C>>(S);
116                s = sred.leftSPolynomial(row, i, pi, j, pj);
117                //logger.info("row = {}", row);
118                if (s.isZERO()) {
119                    Z.add(row);
120                    continue;
121                }
122
123                h = sred.leftNormalform(row, F, s);
124                if (!h.isZERO()) {
125                    System.out.println("s   = " + s);
126                    System.out.println("F   = " + F);
127                    System.out.println("row = " + row);
128                    throw new ArithmeticException("Syzygy no leftGB: h != 0, " + h);
129                }
130                Z.add(row);
131            }
132        }
133        // set null to zero
134        for (List<GenSolvablePolynomial<C>> vr : Z) {
135            for (int j = 0; j < vr.size(); j++) {
136                if (vr.get(j) == null) {
137                    vr.set(j, zero);
138                }
139            }
140        }
141        return Z;
142    }
143
144
145    /**
146     * Left syzygy for left module Groebner base.
147     * @param M a Groebner base.
148     * @return leftSyz(M), a basis for the left module of syzygies for M.
149     */
150    @SuppressWarnings("unchecked")
151    public ModuleList<C> leftZeroRelations(ModuleList<C> M) {
152        ModuleList<C> N = null;
153        if (M == null || M.list == null) {
154            return N;
155        }
156        if (M.rows == 0 || M.cols == 0) {
157            return N;
158        }
159        GenSolvablePolynomial<C> zero = (GenSolvablePolynomial<C>) M.ring.getZERO();
160        //logger.info("zero = {}", zero);
161
162        //ModuleList<C> Np = null;
163        PolynomialList<C> F = M.getPolynomialList();
164        int modv = M.cols; // > 0  
165        logger.info("modv = {}", modv);
166        List<List<GenSolvablePolynomial<C>>> G = leftZeroRelations(modv, F.castToSolvableList());
167        //if (G == null) {
168        //    return N;
169        //}
170        List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>();
171        for (int i = 0; i < G.size(); i++) {
172            List<GenSolvablePolynomial<C>> Gi = G.get(i);
173            List<GenSolvablePolynomial<C>> Zi = new ArrayList<GenSolvablePolynomial<C>>();
174            //System.out.println("\nG("+i+") = " + G.get(i));
175            for (int j = 0; j < Gi.size(); j++) {
176                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
177                GenSolvablePolynomial<C> p = Gi.get(j);
178                if (p != null) {
179                    Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
180                    //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() );
181                    if (r.size() == 0) {
182                        Zi.add(zero);
183                    } else if (r.size() == 1) {
184                        GenSolvablePolynomial<C> vi = (GenSolvablePolynomial<C>) (r.values().toArray())[0];
185                        Zi.add(vi);
186                    } else { // will not happen
187                        throw new RuntimeException("Map.size() > 1 = " + r.size());
188                    }
189                }
190            }
191            //System.out.println("\nZ("+i+") = " + Zi);
192            Z.add(Zi);
193        }
194        N = new ModuleList<C>((GenSolvablePolynomialRing<C>) M.ring, Z);
195        //System.out.println("\n\nN = " + N);
196        return N;
197    }
198
199
200    /**
201     * Right syzygy module from Groebner base.
202     * @param F a solvable polynomial list, a Groebner base.
203     * @return syz(F), a basis for the module of right syzygies for F.
204     */
205    public List<List<GenSolvablePolynomial<C>>> rightZeroRelations(List<GenSolvablePolynomial<C>> F) {
206        return rightZeroRelations(0, F);
207    }
208
209
210    /**
211     * Right syzygy module from Groebner base.
212     * @param modv number of module variables.
213     * @param F a solvable polynomial list, a Groebner base.
214     * @return syz(F), a basis for the module of right syzygies for F.
215     */
216    @SuppressWarnings("unchecked")
217    public List<List<GenSolvablePolynomial<C>>> rightZeroRelations(int modv,
218                    List<GenSolvablePolynomial<C>> F) {
219        GenSolvablePolynomialRing<C> ring = null;
220        for (GenSolvablePolynomial<C> p : F) {
221            if (p != null) {
222                ring = p.ring;
223                break;
224            }
225        }
226        List<List<GenSolvablePolynomial<C>>> Z;
227        if (ring == null) { // all null
228            Z = new ArrayList<List<GenSolvablePolynomial<C>>>(1);
229            Z.add(F);
230            return Z;
231        }
232        //System.out.println("ring to reverse = " + ring.toScript());
233        GenSolvablePolynomialRing<C> rring = ring.reverse(true);
234        GenSolvablePolynomial<C> q;
235        List<GenSolvablePolynomial<C>> rF;
236        rF = new ArrayList<GenSolvablePolynomial<C>>(F.size());
237        for (GenSolvablePolynomial<C> p : F) {
238            if (p != null) {
239                q = (GenSolvablePolynomial<C>) p.reverse(rring);
240                rF.add(q);
241            }
242        }
243        if (debug) {
244            PolynomialList<C> pl = new PolynomialList<C>(rring, rF);
245            logger.info("reversed problem = {}", pl); //.toScript()
246        }
247        List<List<GenSolvablePolynomial<C>>> rZ = leftZeroRelations(modv, rF);
248        if (debug) {
249            boolean isit = isLeftZeroRelation(rZ, rF);
250            logger.debug("isLeftZeroRelation = {}", isit);
251        }
252        GenSolvablePolynomialRing<C> oring = rring.reverse(true);
253        if (debug) {
254            logger.debug("ring == oring: {}", ring.equals(oring));
255        }
256        ring = oring;
257        Z = new ArrayList<List<GenSolvablePolynomial<C>>>(rZ.size());
258        for (List<GenSolvablePolynomial<C>> z : rZ) {
259            if (z == null) {
260                continue;
261            }
262            List<GenSolvablePolynomial<C>> s;
263            s = new ArrayList<GenSolvablePolynomial<C>>(z.size());
264            for (GenSolvablePolynomial<C> p : z) {
265                if (p != null) {
266                    q = (GenSolvablePolynomial<C>) p.reverse(ring);
267                    s.add(q);
268                }
269            }
270            Z.add(s);
271        }
272        return Z;
273    }
274
275
276    /**
277     * Right syzygy for right module Groebner base.
278     * @param M a Groebner base.
279     * @return rightSyz(M), a basis for the right module of syzygies for M.
280     */
281    @SuppressWarnings("unchecked")
282    public ModuleList<C> rightZeroRelations(ModuleList<C> M) {
283        ModuleList<C> N = null;
284        if (M == null || M.list == null) {
285            return N;
286        }
287        if (M.rows == 0 || M.cols == 0) {
288            return N;
289        }
290        GenSolvablePolynomial<C> zero = (GenSolvablePolynomial<C>) M.ring.getZERO();
291        //logger.info("zero = {}", zero);
292
293        //ModuleList<C> Np = null;
294        PolynomialList<C> F = M.getPolynomialList();
295        int modv = M.cols; // > 0  
296        logger.info("modv = {}", modv);
297        List<List<GenSolvablePolynomial<C>>> G = rightZeroRelations(modv, F.castToSolvableList());
298        //if (G == null) {
299        //    return N;
300        //}
301        List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>();
302        for (int i = 0; i < G.size(); i++) {
303            List<GenSolvablePolynomial<C>> Gi = G.get(i);
304            List<GenSolvablePolynomial<C>> Zi = new ArrayList<GenSolvablePolynomial<C>>();
305            //System.out.println("\nG("+i+") = " + G.get(i));
306            for (int j = 0; j < Gi.size(); j++) {
307                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
308                GenSolvablePolynomial<C> p = Gi.get(j);
309                if (p != null) {
310                    Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
311                    //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() );
312                    if (r.size() == 0) {
313                        Zi.add(zero);
314                    } else if (r.size() == 1) {
315                        GenSolvablePolynomial<C> vi = (GenSolvablePolynomial<C>) (r.values().toArray())[0];
316                        Zi.add(vi);
317                    } else { // will not happen
318                        throw new RuntimeException("Map.size() > 1 = " + r.size());
319                    }
320                }
321            }
322            //System.out.println("\nZ("+i+") = " + Zi);
323            Z.add(Zi);
324        }
325        N = new ModuleList<C>((GenSolvablePolynomialRing<C>) M.ring, Z);
326        //System.out.println("\n\nN = " + N);
327        return N;
328    }
329
330
331    /**
332     * Test if left syzygy.
333     * @param Z list of sysygies.
334     * @param F a polynomial list.
335     * @return true, if Z is a list of left syzygies for F, else false.
336     */
337    public boolean isLeftZeroRelation(List<List<GenSolvablePolynomial<C>>> Z,
338                    List<GenSolvablePolynomial<C>> F) {
339        List<GenPolynomial<C>> Fp = PolynomialList.<C> castToList(F);
340        for (List<GenSolvablePolynomial<C>> row : Z) {
341            List<GenPolynomial<C>> yrow = PolynomialList.<C> castToList(row);
342            GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) blas.scalarProduct(yrow, Fp);
343            if (p == null) {
344                continue;
345            }
346            if (!p.isZERO()) {
347                logger.info("is not ZeroRelation = {}", p);
348                return false;
349            }
350        }
351        return true;
352    }
353
354
355    /**
356     * Test if right syzygy.
357     * @param Z list of sysygies.
358     * @param F a polynomial list.
359     * @return true, if Z is a list of right syzygies for F, else false.
360     */
361    public boolean isRightZeroRelation(List<List<GenSolvablePolynomial<C>>> Z,
362                    List<GenSolvablePolynomial<C>> F) {
363        List<GenPolynomial<C>> Fp = PolynomialList.<C> castToList(F);
364        for (List<GenSolvablePolynomial<C>> row : Z) {
365            List<GenPolynomial<C>> yrow = PolynomialList.<C> castToList(row);
366            // param order:
367            GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) blas.scalarProduct(Fp, yrow);
368            if (p == null) {
369                continue;
370            }
371            if (!p.isZERO()) {
372                logger.info("is not ZeroRelation = {}", p);
373                return false;
374            }
375        }
376        return true;
377    }
378
379
380    /**
381     * Test if left sysygy of modules
382     * @param Z list of sysygies.
383     * @param F a module list.
384     * @return true, if Z is a list of left syzygies for F, else false.
385     */
386    public boolean isLeftZeroRelation(ModuleList<C> Z, ModuleList<C> F) {
387        if (Z == null || Z.list == null) {
388            return true;
389        }
390        List<List<GenPolynomial<C>>> Fp = F.list; //F.castToSolvableList();
391        for (List<GenPolynomial<C>> row : Z.list) {
392            List<GenPolynomial<C>> zr = blas.leftScalarProduct(row, Fp);
393            //List<GenSolvablePolynomial<C>> zp = PolynomialList.<C> castToSolvableList(zr);
394            if (!blas.isZero(zr)) {
395                logger.info("is not ZeroRelation ({}) = {}", zr.size(), zr);
396                return false;
397            }
398        }
399        return true;
400    }
401
402
403    /**
404     * Test if right sysygy of modules
405     * @param Z list of sysygies.
406     * @param F a module list.
407     * @return true, if Z is a list of right syzygies for F, else false.
408     */
409    public boolean isRightZeroRelation(ModuleList<C> Z, ModuleList<C> F) {
410        if (Z == null || Z.list == null) {
411            return true;
412        }
413        List<List<GenPolynomial<C>>> Fp = F.list; //F.castToSolvableList();
414        for (List<GenPolynomial<C>> row : Z.list) {
415            List<GenPolynomial<C>> zr = blas.rightScalarProduct(row, Fp);
416            //List<GenSolvablePolynomial<C>> zp = PolynomialList.<C> castToSolvableList(zr);
417            if (!blas.isZero(zr)) {
418                logger.info("is not ZeroRelation ({}) = {}", zr.size(), zr);
419                return false;
420            }
421        }
422        return true;
423    }
424
425
426    /**
427     * Left syzygy module from arbitrary base.
428     * @param F a solvable polynomial list.
429     * @return syz(F), a basis for the module of left syzygies for F.
430     */
431    public List<List<GenSolvablePolynomial<C>>> leftZeroRelationsArbitrary(List<GenSolvablePolynomial<C>> F) {
432        return leftZeroRelationsArbitrary(0, F);
433    }
434
435
436    /**
437     * Left syzygy for arbitrary left module base.
438     * @param M an arbitrary base.
439     * @return leftSyz(M), a basis for the left module of syzygies for M.
440     */
441    @SuppressWarnings("unchecked")
442    public ModuleList<C> leftZeroRelationsArbitrary(ModuleList<C> M) {
443        ModuleList<C> N = null;
444        if (M == null || M.list == null) {
445            return N;
446        }
447        if (M.rows == 0 || M.cols == 0) {
448            return N;
449        }
450        GenSolvablePolynomial<C> zero = (GenSolvablePolynomial<C>) M.ring.getZERO();
451        //logger.info("zero = {}", zero);
452
453        //ModuleList<C> Np = null;
454        PolynomialList<C> F = M.getPolynomialList();
455        int modv = M.cols; // > 0  
456        logger.info("modv = {}", modv);
457        List<List<GenSolvablePolynomial<C>>> G = leftZeroRelationsArbitrary(modv, F.castToSolvableList());
458        if (G == null) {
459            return N;
460        }
461        List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>();
462        for (int i = 0; i < G.size(); i++) {
463            List<GenSolvablePolynomial<C>> Gi = G.get(i);
464            List<GenSolvablePolynomial<C>> Zi = new ArrayList<GenSolvablePolynomial<C>>();
465            //System.out.println("\nG("+i+") = " + G.get(i));
466            for (int j = 0; j < Gi.size(); j++) {
467                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
468                GenSolvablePolynomial<C> p = Gi.get(j);
469                if (p != null) {
470                    Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
471                    //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() );
472                    if (r.size() == 0) {
473                        Zi.add(zero);
474                    } else if (r.size() == 1) {
475                        GenSolvablePolynomial<C> vi = (GenSolvablePolynomial<C>) (r.values().toArray())[0];
476                        Zi.add(vi);
477                    } else { // will not happen
478                        throw new RuntimeException("Map.size() > 1 = " + r.size());
479                    }
480                }
481            }
482            //System.out.println("\nZ("+i+") = " + Zi);
483            Z.add(Zi);
484        }
485        N = new ModuleList<C>((GenSolvablePolynomialRing<C>) M.ring, Z);
486        //System.out.println("\n\nN = " + N);
487        return N;
488    }
489
490
491    /**
492     * Right syzygy module from arbitrary base.
493     * @param F a solvable polynomial list.
494     * @return syz(F), a basis for the module of right syzygies for F.
495     */
496    public List<List<GenSolvablePolynomial<C>>> rightZeroRelationsArbitrary(
497                    List<GenSolvablePolynomial<C>> F) {
498        return rightZeroRelationsArbitrary(0, F);
499    }
500
501
502    /**
503     * Right syzygy module from arbitrary base.
504     * @param modv number of module variables.
505     * @param F a solvable polynomial list.
506     * @return syz(F), a basis for the module of right syzygies for F.
507     */
508    @SuppressWarnings("unchecked")
509    public List<List<GenSolvablePolynomial<C>>> rightZeroRelationsArbitrary(int modv,
510                    List<GenSolvablePolynomial<C>> F) {
511        GenSolvablePolynomialRing<C> ring = null;
512        for (GenSolvablePolynomial<C> p : F) {
513            if (p != null) {
514                ring = p.ring;
515                break;
516            }
517        }
518        List<List<GenSolvablePolynomial<C>>> Z;
519        if (ring == null) { // all null
520            Z = new ArrayList<List<GenSolvablePolynomial<C>>>(1);
521            Z.add(F);
522            return Z;
523        }
524        GenSolvablePolynomialRing<C> rring = ring.reverse(true);
525        //System.out.println("rightZeroRelationsArbitrary: ring = " + ring.toScript() + ", reversed ring = " + rring.toScript());
526        GenSolvablePolynomial<C> q;
527        List<GenSolvablePolynomial<C>> rF;
528        rF = new ArrayList<GenSolvablePolynomial<C>>(F.size());
529        for (GenSolvablePolynomial<C> p : F) {
530            if (p != null) {
531                q = (GenSolvablePolynomial<C>) p.reverse(rring);
532                rF.add(q);
533            }
534        }
535        if (debug) {
536            PolynomialList<C> pl = new PolynomialList<C>(rring, rF);
537            logger.info("reversed problem = {}", rF); //pl.toScript()
538        }
539        List<List<GenSolvablePolynomial<C>>> rZ = leftZeroRelationsArbitrary(modv, rF);
540        if (debug) {
541            ModuleList<C> pl = new ModuleList<C>(rring, rZ);
542            logger.info("reversed syzygies = {}", rZ); //pl.toScript()
543            boolean isit = isLeftZeroRelation(rZ, rF);
544            logger.info("isLeftZeroRelation = {}", isit);
545        }
546        GenSolvablePolynomialRing<C> oring = rring.reverse(true);
547        if (debug) {
548            logger.info("ring == oring: {}", ring.equals(oring));
549        }
550        ring = oring;
551        Z = new ArrayList<List<GenSolvablePolynomial<C>>>(rZ.size());
552        for (List<GenSolvablePolynomial<C>> z : rZ) {
553            if (z == null) {
554                continue;
555            }
556            List<GenSolvablePolynomial<C>> s;
557            s = new ArrayList<GenSolvablePolynomial<C>>(z.size());
558            for (GenSolvablePolynomial<C> p : z) {
559                if (p != null) {
560                    q = (GenSolvablePolynomial<C>) p.reverse(ring);
561                    s.add(q);
562                    //System.out.println("p = " + p + "\nreverse(p) = " + q);
563                }
564            }
565            Z.add(s);
566        }
567        return Z;
568    }
569
570
571    /**
572     * Right syzygy for arbitrary base.
573     * @param M an arbitrary base.
574     * @return rightSyz(M), a basis for the right module of syzygies for M.
575     */
576    @SuppressWarnings("unchecked")
577    public ModuleList<C> rightZeroRelationsArbitrary(ModuleList<C> M) {
578        ModuleList<C> N = null;
579        if (M == null || M.list == null) {
580            return N;
581        }
582        if (M.rows == 0 || M.cols == 0) {
583            return N;
584        }
585        GenSolvablePolynomial<C> zero = (GenSolvablePolynomial<C>) M.ring.getZERO();
586        //logger.info("zero = {}", zero);
587
588        //ModuleList<C> Np = null;
589        PolynomialList<C> F = M.getPolynomialList();
590        int modv = M.cols; // > 0  
591        logger.info("modv = {}", modv);
592        List<List<GenSolvablePolynomial<C>>> G = rightZeroRelationsArbitrary(modv, F.castToSolvableList());
593        //if (G == null) {
594        //    return N;
595        //}
596        List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>();
597        for (int i = 0; i < G.size(); i++) {
598            List<GenSolvablePolynomial<C>> Gi = G.get(i);
599            List<GenSolvablePolynomial<C>> Zi = new ArrayList<GenSolvablePolynomial<C>>();
600            //System.out.println("G("+i+") = " + Gi);
601            for (int j = 0; j < Gi.size(); j++) {
602                GenSolvablePolynomial<C> p = Gi.get(j);
603                //System.out.println("G("+i+","+j+") = " + p);
604                if (p != null) {
605                    Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
606                    //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() );
607                    if (r.size() == 0) {
608                        Zi.add(zero);
609                    } else if (r.size() == 1) {
610                        GenSolvablePolynomial<C> vi = (GenSolvablePolynomial<C>) (r.values().toArray())[0];
611                        Zi.add(vi);
612                    } else { // will not happen
613                        logger.error("p = {}, r = {}", p, r);
614                        throw new RuntimeException("Map.size() > 1 = " + r.size());
615                    }
616                }
617            }
618            //System.out.println("\nZ("+i+") = " + Zi);
619            Z.add(Zi);
620        }
621        N = new ModuleList<C>((GenSolvablePolynomialRing<C>) M.ring, Z);
622        //System.out.println("\n\nN = " + N);
623        return N;
624    }
625
626
627    /**
628     * Test left Ore condition.
629     * @param a solvable polynomial
630     * @param b solvable polynomial
631     * @param oc = [p,q] two solvable polynomials
632     * @return true if p*a = q*b, else false
633     */
634    public boolean isLeftOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b,
635                    GenSolvablePolynomial<C>[] oc) {
636        if (oc == null) {
637            throw new IllegalArgumentException("oc array must be non null");
638        }
639        return isLeftOreCond(a, b, oc[0], oc[1]);
640    }
641
642
643    /**
644     * Is left Ore condition. Test left Ore condition of two solvable
645     * polynomials.
646     * @param a solvable polynomial
647     * @param b solvable polynomial
648     * @param p solvable polynomial
649     * @param q solvable polynomial
650     * @return true, if p*a = q*b, else false
651     */
652    public boolean isLeftOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b,
653                    GenSolvablePolynomial<C> p, GenSolvablePolynomial<C> q) {
654        if (a == null || a.isZERO() || b == null || b.isZERO()) {
655            throw new IllegalArgumentException("a and b must be non zero");
656        }
657        GenSolvablePolynomial<C> pa = p.multiply(a);
658        GenSolvablePolynomial<C> qb = q.multiply(b);
659        return pa.equals(qb);
660    }
661
662
663    /**
664     * Test right Ore condition.
665     * @param a solvable polynomial
666     * @param b solvable polynomial
667     * @param oc = [p,q] two solvable polynomials
668     * @return true if a*p = b*q, else false
669     */
670    public boolean isRightOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b,
671                    GenSolvablePolynomial<C>[] oc) {
672        if (oc == null) {
673            throw new IllegalArgumentException("oc array must be non null");
674        }
675        return isRightOreCond(a, b, oc[0], oc[1]);
676    }
677
678
679    /**
680     * Is right Ore condition. Test right Ore condition of two solvable
681     * polynomials.
682     * @param a solvable polynomial
683     * @param b solvable polynomial
684     * @param p solvable polynomial
685     * @param q solvable polynomial
686     * @return true, if a*p = b*q, else false
687     */
688    public boolean isRightOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b,
689                    GenSolvablePolynomial<C> p, GenSolvablePolynomial<C> q) {
690        if (a == null || a.isZERO() || b == null || b.isZERO()) {
691            throw new IllegalArgumentException("a and b must be non zero");
692        }
693        GenSolvablePolynomial<C> ap = a.multiply(p);
694        GenSolvablePolynomial<C> bq = b.multiply(q);
695        return ap.equals(bq);
696    }
697
698
699    /**
700     * Left simplifier. Method of Apel &amp; Lassner (1987).
701     * @param a solvable polynomial
702     * @param b solvable polynomial
703     * @return [p,q] with a/b = p/q and q is minimal and monic
704     */
705    public abstract GenSolvablePolynomial<C>[] leftSimplifier(GenSolvablePolynomial<C> a,
706                    GenSolvablePolynomial<C> b);
707
708
709    /**
710     * Comparison like SolvableLocal or SolvableQuotient.
711     * @param num SolvablePolynomial.
712     * @param den SolvablePolynomial.
713     * @param n SolvablePolynomial.
714     * @param d SolvablePolynomial.
715     * @return sign((num/den)-(n/d)).
716     */
717    public int compare(GenSolvablePolynomial<C> num, GenSolvablePolynomial<C> den, GenSolvablePolynomial<C> n,
718                    GenSolvablePolynomial<C> d) {
719        if (n == null || n.isZERO()) {
720            return num.signum();
721        }
722        if (num.isZERO()) {
723            return -n.signum();
724        }
725        // assume sign(den,b.den) > 0
726        int s1 = num.signum();
727        int s2 = n.signum();
728        int t = (s1 - s2) / 2;
729        if (t != 0) {
730            System.out.println("compareTo: t = " + t);
731            //return t;
732        }
733        if (den.compareTo(d) == 0) {
734            return num.compareTo(n);
735        }
736        GenSolvablePolynomial<C> r, s;
737        // if (den.isONE()) { }
738        // if (b.den.isONE()) { }
739        GenSolvablePolynomial<C>[] oc = leftOreCond(den, d);
740        if (debug) {
741            System.out.println("oc[0] den =<>= oc[1] d: (" + oc[0] + ") (" + den + ") = (" + oc[1] + ") (" + d
742                            + ")");
743        }
744        //System.out.println("oc[0] = " + oc[0]);
745        //System.out.println("oc[1] = " + oc[1]);
746        r = oc[0].multiply(num);
747        s = oc[1].multiply(n);
748        logger.info("compare: r = {}, s = {}", r, s);
749        return r.compareTo(s);
750    }
751
752}
753
754
755/**
756 * Container for module resolution components.
757 * @param <C> coefficient type
758 */
759class SolvResPart<C extends RingElem<C>> implements Serializable {
760
761
762    public final ModuleList<C> module;
763
764
765    public final ModuleList<C> GB;
766
767
768    public final ModuleList<C> syzygy;
769
770
771    /**
772     * SolvResPart.
773     * @param m a module list.
774     * @param g a module list GB.
775     * @param z a syzygy module list.
776     */
777    public SolvResPart(ModuleList<C> m, ModuleList<C> g, ModuleList<C> z) {
778        module = m;
779        GB = g;
780        syzygy = z;
781    }
782
783
784    /**
785     * toString.
786     */
787    @Override
788    public String toString() {
789        StringBuffer s = new StringBuffer("SolvResPart(\n");
790        s.append("module = " + module);
791        s.append("\n GB = " + GB);
792        s.append("\n syzygy = " + syzygy);
793        s.append(")");
794        return s.toString();
795    }
796}
797
798
799/**
800 * Container for polynomial resolution components.
801 * @param <C> coefficient type
802 */
803class SolvResPolPart<C extends RingElem<C>> implements Serializable {
804
805
806    public final PolynomialList<C> ideal;
807
808
809    public final PolynomialList<C> GB;
810
811
812    public final ModuleList<C> syzygy;
813
814
815    /**
816     * SolvResPolPart.
817     * @param m a polynomial list.
818     * @param g a polynomial list GB.
819     * @param z a syzygy module list.
820     */
821    public SolvResPolPart(PolynomialList<C> m, PolynomialList<C> g, ModuleList<C> z) {
822        ideal = m;
823        GB = g;
824        syzygy = z;
825    }
826
827
828    /**
829     * toString.
830     */
831    @Override
832    public String toString() {
833        StringBuffer s = new StringBuffer("SolvResPolPart(\n");
834        s.append("ideal = " + ideal);
835        s.append("\n GB = " + GB);
836        s.append("\n syzygy = " + syzygy);
837        s.append(")");
838        return s.toString();
839    }
840
841}