Source code

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