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