/*
 * $Id$
 */

package edu.jas.gbmod;


import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import org.apache.log4j.Logger;

import edu.jas.gb.Reduction;
import edu.jas.gb.ReductionSeq;
import edu.jas.gb.SolvableExtendedGB;
import edu.jas.gb.SolvableGroebnerBase;
import edu.jas.gb.SolvableGroebnerBaseSeq;
import edu.jas.gb.SolvableReduction;
import edu.jas.gb.SolvableReductionSeq;
import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenSolvablePolynomial;
import edu.jas.poly.GenSolvablePolynomialRing;
import edu.jas.poly.ModuleList;
import edu.jas.poly.PolynomialList;
import edu.jas.structure.RingElem;
import edu.jas.vector.BasicLinAlg;


/**
 * Syzygy class for solvable polynomials. Implements Syzygy computations and
 * tests.
 * @param  coefficient type
 * @author Heinz Kredel
 */

public class SolvableSyzygyAbstract> implements SolvableSyzygy {


    private static final Logger logger = Logger.getLogger(SolvableSyzygyAbstract.class);


    private final boolean debug = logger.isDebugEnabled();


    /**
     * Solvable reduction engine.
     */
    public final SolvableReduction sred;


    /**
     * Reduction engine.
     */
    protected Reduction red;


    /**
     * Linear algebra engine.
     */
    protected BasicLinAlg> blas;


    /**
     * Groebner basis engine.
     */
    protected SolvableGroebnerBase sbb;


    /**
     * Module Groebner basis engine.
     */
    protected ModSolvableGroebnerBase msbb;


    /**
     * Constructor.
     */
    public SolvableSyzygyAbstract() {
        red = new ReductionSeq();
        sred = new SolvableReductionSeq();
        blas = new BasicLinAlg>();
        sbb = new SolvableGroebnerBaseSeq();
        msbb = new ModSolvableGroebnerBaseAbstract();
    }


    /**
     * Left syzygy for left Groebner base.
     * @param F a Groebner base.
     * @return leftSyz(F), a basis for the left module of syzygies for F.
     */
    public List>> leftZeroRelations(List> F) {
        return leftZeroRelations(0, F);
    }


    /**
     * Left syzygy for left Groebner base.
     * @param modv number of module variables.
     * @param F a Groebner base.
     * @return leftSyz(F), a basis for the left module of syzygies for F.
     */
    public List>> leftZeroRelations(int modv, List> F) {
        List>> Z = new ArrayList>>();
        ArrayList> S = new ArrayList>(F.size());
        for (int i = 0; i < F.size(); i++) {
            S.add(null);
        }
        GenSolvablePolynomial pi, pj, s, h, zero;
        zero = null;
        for (int i = 0; i < F.size(); i++) {
            pi = F.get(i);
            if (pi != null && zero == null) {
                zero = pi.ring.getZERO();
            }
            for (int j = i + 1; j < F.size(); j++) {
                pj = F.get(j);
                //logger.info("p"+i+", p"+j+" = " + pi + ", " +pj);

                if (!red.moduleCriterion(modv, pi, pj)) {
                    continue;
                }
                // if ( ! red.criterion4( pi, pj ) ) continue;
                List> row = new ArrayList>(S);
                s = sred.leftSPolynomial(row, i, pi, j, pj);
                //logger.info("row = " + row);
                if (s.isZERO()) {
                    Z.add(row);
                    continue;
                }

                h = sred.leftNormalform(row, F, s);
                if (!h.isZERO()) {
                    throw new ArithmeticException("Syzygy no leftGB");
                }
                if (logger.isDebugEnabled()) {
                    logger.info("row = " + row);
                }
                Z.add(row);
            }
        }
        // set null to zero
        for (List> vr : Z) {
            for (int j = 0; j < vr.size(); j++) {
                if (vr.get(j) == null) {
                    vr.set(j, zero);
                }
            }
        }
        return Z;
    }


    /**
     * Left syzygy for left module Groebner base.
     * @param M a Groebner base.
     * @return leftSyz(M), a basis for the left module of syzygies for M.
     */
    @SuppressWarnings("unchecked")
    public ModuleList leftZeroRelations(ModuleList M) {
        ModuleList N = null;
        if (M == null || M.list == null) {
            return N;
        }
        if (M.rows == 0 || M.cols == 0) {
            return N;
        }
        GenSolvablePolynomial zero = (GenSolvablePolynomial) M.ring.getZERO();
        //logger.info("zero = " + zero);

        //ModuleList Np = null;
        PolynomialList F = M.getPolynomialList();
        int modv = M.cols; // > 0  
        logger.info("modv = " + modv);
        List>> G = leftZeroRelations(modv, F.castToSolvableList());
        //if (G == null) {
        //    return N;
        //}
        List>> Z = new ArrayList>>();
        for (int i = 0; i < G.size(); i++) {
            List> Gi = G.get(i);
            List> Zi = new ArrayList>();
            // System.out.println("\nG("+i+") = " + G.get(i));
            for (int j = 0; j < Gi.size(); j++) {
                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
                GenSolvablePolynomial p = Gi.get(j);
                if (p != null) {
                    Map> r = p.contract(M.ring);
                    //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() );
                    if (r.size() == 0) {
                        Zi.add(zero);
                    } else if (r.size() == 1) {
                        GenSolvablePolynomial vi = (GenSolvablePolynomial) (r.values().toArray())[0];
                        Zi.add(vi);
                    } else { // will not happen
                        throw new RuntimeException("Map.size() > 1 = " + r.size());
                    }
                }
            }
            //System.out.println("\nZ("+i+") = " + Zi);
            Z.add(Zi);
        }
        N = new ModuleList((GenSolvablePolynomialRing) M.ring, Z);
        //System.out.println("\n\nN = " + N);
        return N;
    }


    /**
     * Test if left syzygy.
     * @param Z list of sysygies.
     * @param F a polynomial list.
     * @return true, if Z is a list of left syzygies for F, else false.
     */
    public boolean isLeftZeroRelation(List>> Z, List> F) {
        List> Fp = PolynomialList. castToList(F);
        for (List> row : Z) {
            // p has wrong type:
            GenPolynomial p = blas.scalarProduct(PolynomialList. castToList(row), Fp);
            if (p == null) {
                continue;
            }
            if (!p.isZERO()) {
                logger.info("is not ZeroRelation = " + p);
                return false;
            }
        }
        return true;
    }


    /**
     * Test if right syzygy.
     * @param Z list of sysygies.
     * @param F a polynomial list.
     * @return true, if Z is a list of right syzygies for F, else false.
     */
    public boolean isRightZeroRelation(List>> Z,
                    List> F) {
        List> Fp = PolynomialList. castToList(F);
        for (List> row : Z) {
            List> yrow = PolynomialList. castToList(row);
            // p has wrong type:
            GenPolynomial p = blas.scalarProduct(Fp, yrow); // param order
            if (p == null) {
                continue;
            }
            if (!p.isZERO()) {
                logger.info("is not ZeroRelation = " + p);
                return false;
            }
        }
        return true;
    }


    /**
     * Test if left sysygy of modules
     * @param Z list of sysygies.
     * @param F a module list.
     * @return true, if Z is a list of left syzygies for F, else false.
     */
    public boolean isLeftZeroRelation(ModuleList Z, ModuleList F) {
        if (Z == null || Z.list == null) {
            return true;
        }
        for (List> row : Z.list) {
            List> zr = blas.leftScalarProduct(row, F.list);
            if (!blas.isZero(zr)) {
                logger.info("is not ZeroRelation (" + zr.size() + ") = " + zr);
                return false;
            }
        }
        return true;
    }


    /**
     * Test if right sysygy of modules
     * @param Z list of sysygies.
     * @param F a module list.
     * @return true, if Z is a list of right syzygies for F, else false.
     */
    public boolean isRightZeroRelation(ModuleList Z, ModuleList F) {
        if (Z == null || Z.list == null) {
            return true;
        }
        for (List> row : Z.list) {
            List> zr = blas.rightScalarProduct(row, F.list);
            //List> zr = blas.scalarProduct(row,F.list);
            if (!blas.isZero(zr)) {
                logger.info("is not ZeroRelation (" + zr.size() + ") = " + zr);
                return false;
            }
        }
        return true;
    }


    /**
     * Resolution of a module. Only with direct GBs.
     * @param M a module list of a Groebner basis.
     * @return a resolution of M.
     */
    public List> resolution(ModuleList M) {
        List> R = new ArrayList>();
        ModuleList MM = M;
        ModuleList GM;
        ModuleList Z;
        while (true) {
            GM = msbb.leftGB(MM);
            Z = leftZeroRelations(GM);
            R.add(new SolvResPart(MM, GM, Z));
            if (Z == null || Z.list == null || Z.list.size() == 0) {
                break;
            }
            MM = Z;
        }
        return R;
    }


    /**
     * Resolution of a polynomial list. Only with direct GBs.
     * @param F a polynomial list of a Groebner basis.
     * @return a resolution of F.
     */
    @SuppressWarnings("unchecked")
    public List // |SolvResPolPart> 
      resolution(PolynomialList F) {
        List>> Z;
        ModuleList Zm;
        List> G;
        PolynomialList Gl;

        G = sbb.leftGB(F.castToSolvableList());
        Z = leftZeroRelations(G);
        Gl = new PolynomialList((GenSolvablePolynomialRing) F.ring, G);
        Zm = new ModuleList((GenSolvablePolynomialRing) F.ring, Z);

        List R = resolution(Zm);
        R.add(0, new SolvResPolPart(F, Gl, Zm));
        return R;
    }


    /**
     * Resolution of a module.
     * @param M a module list of an arbitrary basis.
     * @return a resolution of M.
     */
    public List> resolutionArbitrary(ModuleList M) {
        List> R = new ArrayList>();
        ModuleList MM = M;
        ModuleList GM = null;
        ModuleList Z;
        while (true) {
            //GM = msbb.leftGB(MM);
            Z = leftZeroRelationsArbitrary(MM);
            R.add(new SolvResPart(MM, GM, Z));
            if (Z == null || Z.list == null || Z.list.size() == 0) {
                break;
            }
            MM = Z;
        }
        return R;
    }


    /**
     * Resolution of a polynomial list.
     * @param F a polynomial list of an arbitrary basis.
     * @return a resolution of F.
     */
    @SuppressWarnings("unchecked")
    public List // |SolvResPolPart> 
      resolutionArbitrary(PolynomialList F) {
        List>> Z;
        ModuleList Zm;
        PolynomialList Gl = null;
        //List> G = sbb.leftGB( F.castToSolvableList() );
        //Gl = new PolynomialList((GenSolvablePolynomialRing)F.ring, G);
        Z = leftZeroRelationsArbitrary(F.castToSolvableList());
        Zm = new ModuleList((GenSolvablePolynomialRing) F.ring, Z);

        List R = resolutionArbitrary(Zm);
        R.add(0, new SolvResPolPart(F, Gl, Zm));
        return R;
    }


    /**
     * Left syzygy module from arbitrary base.
     * @param F a solvable polynomial list.
     * @return syz(F), a basis for the module of left syzygies for F.
     */
    public List>> leftZeroRelationsArbitrary(List> F) {
        return leftZeroRelationsArbitrary(0, F);
    }


    /**
     * Left syzygy module from arbitrary base.
     * @param modv number of module variables.
     * @param F a solvable polynomial list.
     * @return syz(F), a basis for the module of left syzygies for F.
     */
     @SuppressWarnings("unchecked")
     public List>> leftZeroRelationsArbitrary(int modv,
                    List> F) {
        if (F == null) {
            return null; //leftZeroRelations( modv, F );
        }
        if (F.size() <= 1) {
            return leftZeroRelations(modv, F);
        }
        final int lenf = F.size();
        SolvableExtendedGB exgb = sbb.extLeftGB(F);
        if (debug) {
            logger.info("exgb = " + exgb);
        }
        if (!sbb.isLeftReductionMatrix(exgb)) {
            logger.error("is reduction matrix ? false");
        }
        List> G = exgb.G;
        List>> G2F = exgb.G2F;
        List>> F2G = exgb.F2G;

        List>> sg = leftZeroRelations(modv, G);
        GenSolvablePolynomialRing ring = G.get(0).ring;
        ModuleList S = new ModuleList(ring, sg);
        if (debug) {
            logger.info("syz = " + S);
        }
        if (!isLeftZeroRelation(sg, G)) {
            logger.error("is syzygy ? false");
        }

        List>> sf;
        sf = new ArrayList>>(sg.size());
        //List> row;

        for (List> r : sg) {
            Iterator> it = r.iterator();
            Iterator>> jt = G2F.iterator();

            List> rf;
            rf = new ArrayList>(lenf);
            for (int m = 0; m < lenf; m++) {
                rf.add(ring.getZERO());
            }
            while (it.hasNext() && jt.hasNext()) {
                GenSolvablePolynomial si = it.next();
                List> ai = jt.next();
                //System.out.println("si = " + si);
                //System.out.println("ai = " + ai);
                if (si == null || ai == null) {
                    continue;
                }
                // pi has wrong type:
                List> pi = blas.scalarProduct(si, PolynomialList. castToList(ai));
                //System.out.println("pi = " + pi);
                rf = PolynomialList. castToSolvableList(blas.vectorAdd(PolynomialList. castToList(rf),
                                pi));
            }
            if (it.hasNext() || jt.hasNext()) {
                logger.error("leftZeroRelationsArbitrary wrong sizes");
            }
            //System.out.println("\nrf = " + rf + "\n");
            sf.add(rf);
        }
        if (!isLeftZeroRelation(sf, F)) {
            logger.error("is partial syz sf ? false");
        }

        List>> M;
        M = new ArrayList>>(lenf);
        for (List> r : F2G) {
            Iterator> it = r.iterator();
            Iterator>> jt = G2F.iterator();

            List> rf;
            rf = new ArrayList>(lenf);
            for (int m = 0; m < lenf; m++) {
                rf.add(ring.getZERO());
            }
            while (it.hasNext() && jt.hasNext()) {
                GenSolvablePolynomial si = it.next();
                List> ai = jt.next();
                //System.out.println("si = " + si);
                //System.out.println("ai = " + ai);
                if (si == null || ai == null) {
                    continue;
                }
                //pi has wrong type, should be: List>
                List> pi = blas.scalarProduct(si, PolynomialList. castToList(ai));
                //System.out.println("pi = " + pi);
                rf = PolynomialList. castToSolvableList(blas.vectorAdd(PolynomialList. castToList(rf),
                                pi));
            }
            if (it.hasNext() || jt.hasNext()) {
                logger.error("zeroRelationsArbitrary wrong sizes");
            }
            //System.out.println("\nMg Mf = " + rf + "\n");
            M.add(rf);
        }
        //ModuleList ML = new ModuleList( ring, M );
        //System.out.println("syz ML = " + ML);
        // debug only:
        //List> F2 = new ArrayList>( F.size() );
        /* not true in general
        List> Fp = PolynomialList.castToList(F);
        for ( List> rr: M ) {
            GenSolvablePolynomial rrg = PolynomialList.castToSolvableList(blas.scalarProduct(Fp,PolynomialList.castToList(rr)));
            F2.add( rrg );
        }
        PolynomialList pF = new PolynomialList( ring, F );
        PolynomialList pF2 = new PolynomialList( ring, F2 );
        if ( ! pF.equals( pF2 ) ) {
           logger.error("is FAB = F ? false");
           //System.out.println("pF  = " + pF.list.size());
           //System.out.println("pF2 = " + pF2.list.size());
        }
        */
        int sflen = sf.size();
        List>> M2;
        M2 = new ArrayList>>(lenf);
        int i = 0;
        for (List> ri : M) {
            List> r2i;
            r2i = new ArrayList>(ri.size());
            int j = 0;
            for (GenSolvablePolynomial rij : ri) {
                GenSolvablePolynomial p = null;
                if (i == j) {
                    p = (GenSolvablePolynomial) ring.getONE().subtract(rij);
                } else {
                    if (rij != null) {
                        p = (GenSolvablePolynomial) rij.negate();
                    }
                }
                r2i.add(p);
                j++;
            }
            M2.add(r2i);
            if (!blas.isZero(PolynomialList. castToList(r2i))) {
                sf.add(r2i);
            }
            i++;
        }
        ModuleList M2L = new ModuleList(ring, M2);
        if (debug) {
            logger.debug("syz M2L = " + M2L);
        }

        if (debug) {
            ModuleList SF = new ModuleList(ring, sf);
            logger.debug("syz sf = " + SF);
            logger.debug("#syz " + sflen + ", " + sf.size());
        }
        if (!isLeftZeroRelation(sf, F)) {
            logger.error("is syz sf ? false");
        }
        return sf;
    }


    /**
     * Left syzygy for arbitrary left module base.
     * @param M an arbitrary base.
     * @return leftSyz(M), a basis for the left module of syzygies for M.
     */
    @SuppressWarnings("unchecked")
    public ModuleList leftZeroRelationsArbitrary(ModuleList M) {
        ModuleList N = null;
        if (M == null || M.list == null) {
            return N;
        }
        if (M.rows == 0 || M.cols == 0) {
            return N;
        }
        GenSolvablePolynomial zero = (GenSolvablePolynomial) M.ring.getZERO();
        //logger.info("zero = " + zero);

        //ModuleList Np = null;
        PolynomialList F = M.getPolynomialList();
        int modv = M.cols; // > 0  
        logger.info("modv = " + modv);
        List>> G = leftZeroRelationsArbitrary(modv, F.castToSolvableList());
        if (G == null) {
            return N;
        }
        List>> Z = new ArrayList>>();
        for (int i = 0; i < G.size(); i++) {
            List> Gi = G.get(i);
            List> Zi = new ArrayList>();
            // System.out.println("\nG("+i+") = " + G.get(i));
            for (int j = 0; j < Gi.size(); j++) {
                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
                GenSolvablePolynomial p = Gi.get(j);
                if (p != null) {
                    Map> r = p.contract(M.ring);
                    //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() );
                    if (r.size() == 0) {
                        Zi.add(zero);
                    } else if (r.size() == 1) {
                        GenSolvablePolynomial vi = (GenSolvablePolynomial) (r.values().toArray())[0];
                        Zi.add(vi);
                    } else { // will not happen
                        throw new RuntimeException("Map.size() > 1 = " + r.size());
                    }
                }
            }
            //System.out.println("\nZ("+i+") = " + Zi);
            Z.add(Zi);
        }
        N = new ModuleList((GenSolvablePolynomialRing) M.ring, Z);
        //System.out.println("\n\nN = " + N);
        return N;
    }


    /**
     * Right syzygy module from arbitrary base.
     * @param F a solvable polynomial list.
     * @return syz(F), a basis for the module of right syzygies for F.
     */
    public List>> rightZeroRelationsArbitrary(List> F) {
        return rightZeroRelationsArbitrary(0, F);
    }


    /**
     * Right syzygy module from arbitrary base.
     * @param modv number of module variables.
     * @param F a solvable polynomial list.
     * @return syz(F), a basis for the module of right syzygies for F.
     */
    @SuppressWarnings("unchecked")
    public List>> rightZeroRelationsArbitrary(int modv,
                    List> F) {
        GenSolvablePolynomialRing ring = null;
        for (GenSolvablePolynomial p : F) {
            if (p != null) {
                ring = p.ring;
                break;
            }
        }
        List>> Z;
        if (ring == null) { // all null
            Z = new ArrayList>>(1);
            Z.add(F);
            return Z;
        }
        GenSolvablePolynomialRing rring = ring.reverse(true);
        GenSolvablePolynomial q;
        List> rF;
        rF = new ArrayList>(F.size());
        for (GenSolvablePolynomial p : F) {
            if (p != null) {
                q = (GenSolvablePolynomial) p.reverse(rring);
                rF.add(q);
            }
        }
        if (debug) {
            PolynomialList pl = new PolynomialList(rring, rF);
            logger.info("reversed problem = " + pl.toScript());
            //System.out.println("reversed problem = " + pl);
        }
        List>> rZ = leftZeroRelationsArbitrary(modv, rF);
        if (debug) {
            boolean isit = isLeftZeroRelation(rZ, rF);
            logger.debug("isLeftZeroRelation = " + isit);
        }
        GenSolvablePolynomialRing oring = rring.reverse(true);
        if (debug) {
            logger.debug("ring == oring: " + ring.equals(oring));
        }
        ring = oring;
        Z = new ArrayList>>(rZ.size());
        for (List> z : rZ) {
            if (z == null) {
                continue;
            }
            List> s;
            s = new ArrayList>(z.size());
            for (GenSolvablePolynomial p : z) {
                if (p != null) {
                    q = (GenSolvablePolynomial) p.reverse(ring);
                    s.add(q);
                }
            }
            Z.add(s);
        }
        return Z;
    }


    /**
     * Test left Ore condition. 
     * @param a solvable polynomial
     * @param b solvable polynomial
     * @param oc = [p,q] two solvable polynomials
     * @return true if p*a = q*b, else false
     */
    public boolean isLeftOreCond(GenSolvablePolynomial a, GenSolvablePolynomial b, 
                                 GenSolvablePolynomial[] oc) {
        GenSolvablePolynomial c = oc[0].multiply(a);
        GenSolvablePolynomial d = oc[1].multiply(b);
        return c.equals(d);
    }


    /**
     * Test right Ore condition. 
     * @param a solvable polynomial
     * @param b solvable polynomial
     * @param oc = [p,q] two solvable polynomials
     * @return true if a*p = b*q, else false
     */
    public boolean isRightOreCond(GenSolvablePolynomial a, GenSolvablePolynomial b, 
                                  GenSolvablePolynomial[] oc) {
        GenSolvablePolynomial c = a.multiply(oc[0]);
        GenSolvablePolynomial d = b.multiply(oc[1]);
        return c.equals(d);
    }


    /**
     * Left Ore condition. 
     * Generators for the left Ore condition of two solvable polynomials.
     * @param a solvable polynomial
     * @param b solvable polynomial
     * @return [p,q] with p*a = q*b
     */
    public GenSolvablePolynomial[] leftOreCond(GenSolvablePolynomial a, GenSolvablePolynomial b) {
        if (a == null || a.isZERO() || b == null || b.isZERO()) {
            throw new IllegalArgumentException("a and b must be non zero");
        }
        GenSolvablePolynomialRing pfac = a.ring;
        GenSolvablePolynomial[] oc = (GenSolvablePolynomial[]) new GenSolvablePolynomial[2];
        if ( a.equals(b) ) {
            oc[0] = pfac.getONE();
            oc[1] = pfac.getONE();
            return oc;
        }
        if ( a.isConstant() ) {
            if (pfac.coFac.isCommutative()) { // ??
                oc[0] = b;
                oc[1] = a;
                return oc;
            }
            oc[1] = pfac.getONE();
            C c = a.leadingBaseCoefficient().inverse();
            oc[0] = b.multiply(c);
            return oc;
        }
        if ( b.isConstant() ) {
            if (pfac.coFac.isCommutative()) { // ??
                oc[0] = b;
                oc[1] = a;
                return oc;
            }
            oc[0] = pfac.getONE();
            C c = b.leadingBaseCoefficient().inverse();
            oc[1] = a.multiply(c);
            return oc;
        }
        logger.info("computing left Ore condition: " + a + ", " + b);
        List> F = new ArrayList>(2);
        F.add(a); F.add(b);
        List>> Gz = leftZeroRelationsArbitrary(F);
        if ( Gz.size() < 0 ) { // always false
            //System.out.println("Gz = " + Gz);
            ModuleList M = new ModuleList(pfac,Gz);
            ModuleList GM = msbb.leftGB(M);
            //System.out.println("GM = " + GM);
            Gz = GM.castToSolvableList();
        }
        List> G1 = null;
        GenSolvablePolynomial g1 = null;
        for (List> Gi : Gz ) {
            //System.out.println("Gi = " + Gi);
            if ( Gi.get(0).isZERO() ) {
                continue;
            }
            if ( G1 == null ) {
                G1 = Gi;
            }
            if ( g1 == null ) {
                g1 = G1.get(0);
            } else if ( g1.compareTo(Gi.get(0)) > 0 ) { //g1.degree() > Gi.get(0).degree() 
                G1 = Gi;
                g1 = G1.get(0);
            }
        }
        oc[0] = g1; //G1.get(0);
        oc[1] = (GenSolvablePolynomial) G1.get(1).negate();
        //logger.info("Ore multiple: " + oc[0].multiply(a) + ", " + Arrays.toString(oc));
        return oc;
    }


    /**
     * Right Ore condition. 
     * Generators for the right Ore condition of two solvable polynomials.
     * @param a solvable polynomial
     * @param b solvable polynomial
     * @return [p,q] with a*p = b*q
     */
    public GenSolvablePolynomial[] rightOreCond(GenSolvablePolynomial a, GenSolvablePolynomial b) {
        if (a == null || a.isZERO() || b == null || b.isZERO()) {
            throw new IllegalArgumentException("a and b must be non zero");
        }
        GenSolvablePolynomialRing pfac = a.ring;
        GenSolvablePolynomial[] oc = (GenSolvablePolynomial[]) new GenSolvablePolynomial[2];
        if ( a.equals(b) ) {
            oc[0] = pfac.getONE();
            oc[1] = pfac.getONE();
            return oc;
        }
        if ( a.isConstant() ) {
            if (pfac.coFac.isCommutative()) { // ??
                oc[0] = b;
                oc[1] = a;
                return oc;
            }
            oc[1] = pfac.getONE();
            C c = a.leadingBaseCoefficient().inverse();
            oc[0] = b.multiply(c);
            return oc;
        }
        if ( b.isConstant() ) {
            if (pfac.coFac.isCommutative()) { // ??
                oc[0] = b;
                oc[1] = a;
                return oc;
            }
            oc[0] = pfac.getONE();
            C c = b.leadingBaseCoefficient().inverse();
            oc[1] = a.multiply(c);
            return oc;
        }
        logger.info("computing right Ore condition: " + a + ", " + b);
        List> F = new ArrayList>(2);
        F.add(a); F.add(b);
        List>> Gz = rightZeroRelationsArbitrary(F);
        List> G1 = null;
        GenSolvablePolynomial g1 = null;
        for (List> Gi : Gz ) {
            if ( Gi.get(0).isZERO() ) {
                continue;
            }
            if ( G1 == null ) {
                G1 = Gi;
            }
            if ( g1 == null ) {
                g1 = G1.get(0);
            } else if ( g1.compareTo(Gi.get(0)) > 0 ) {
                G1 = Gi;
                g1 = G1.get(0);
            }
        }
        oc[0] = G1.get(0);
        oc[1] = (GenSolvablePolynomial) G1.get(1).negate();
        //logger.info("Ore multiple: " + a.multiply(oc[0]) + ", " + Arrays.toString(oc));
        return oc;
    }


    /**
     * Left simplifier. 
     * Method of Apel & Lassner (1987).
     * @param a solvable polynomial
     * @param b solvable polynomial
     * @return [p,q] with a/b = p/q and q is minimal and monic
     */
    public GenSolvablePolynomial[] leftSimplifier(GenSolvablePolynomial a, GenSolvablePolynomial b) {
        if (a == null || a.isZERO() || b == null || b.isZERO()) {
            throw new IllegalArgumentException("a and b must be non zero");
        }
        GenSolvablePolynomial[] oc = null;
        if (a.totalDegree() > 3 || b.totalDegree() > 3) { // how avoid too long running GBs ?
        //if (a.totalDegree() + b.totalDegree() > 6) { // how avoid too long running GBs ?
            // && a.length() < 10 && b.length() < 10
            logger.warn("skipping GB computation: degs = " + a.totalDegree() + ", " + b.totalDegree());
            oc = new GenSolvablePolynomial[] { a, b };
            return oc;
        }
        GenSolvablePolynomialRing pfac = a.ring;
        oc = rightOreCond(a,b);
        logger.info("oc = " + Arrays.toString(oc)); // + ", a = " + a + ", b = " + b);
        List> F = new ArrayList>(oc.length);
        // opposite order and undo negation
        F.add( (GenSolvablePolynomial) oc[1].negate()); 
        F.add(                            oc[0] ); 
        //logger.info("F = " + F);
        List>> Gz = leftZeroRelationsArbitrary(F);
        //logger.info("Gz: " + Gz);
        List> G1 = new ArrayList>(Gz.size());
        List> G2 = new ArrayList>(Gz.size());
        for ( List> ll : Gz) {
            if ( !ll.get(0).isZERO() ) { // && !ll.get(1).isZERO()
                G1.add(ll.get(0)); // denominators
                G2.add(ll.get(1)); // numerators
            }
        }
        logger.info("G1(den): " + G1 + ", G2(num): " + G2);
        SolvableExtendedGB exgb = sbb.extLeftGB(G1);
        logger.info("exgb.F: " + exgb.F + ", exgb.G: " + exgb.G);
        List> G = exgb.G;
        int m = 0;
        GenSolvablePolynomial min = null;
        for ( int i = 0; i < G.size(); i++ ) {
            if ( min == null ) {
                min = G.get(i);  
                m = i;
            } else if (min.compareTo(G.get(i)) > 0 ) {
                min = G.get(i);  
                m = i;
            }
        }
        //wrong: blas.scalarProduct(G2,exgb.G2F.get(m));
        GenSolvablePolynomial min2 = (GenSolvablePolynomial) blas.scalarProduct(PolynomialList. castToList(exgb.G2F.get(m)), PolynomialList. castToList(G2));
        logger.info("min(den): " + min + ", min(num): " + min2 + ", m = " + m + ", " + exgb.G2F.get(m));
        // opposite order
        GenSolvablePolynomial n = min2; // nominator
        GenSolvablePolynomial d = min;  // denominator
        // normalize
        if (d.signum() < 0) {
            n = (GenSolvablePolynomial) n.negate();
            d = (GenSolvablePolynomial) d.negate();
        }
        C lc = d.leadingBaseCoefficient();
        if (!lc.isONE() && lc.isUnit()) {
            lc = lc.inverse();
            n = n.multiplyLeft(lc);
            d = d.multiplyLeft(lc);
        }
        if (debug) {
            int t = compare(a,b,n,d);
            if (t != 0) {
                oc[0] = a; // nominator
                oc[1] = b; // denominator
                throw new RuntimeException("simp wrong, giving up: t = " + t);
                //logger.error("simp wrong, giving up: t = " + t);
                //return oc;
            }
        }
        oc[0] = n; // nominator
        oc[1] = d; // denominator
        return oc;
    }


    /**
     * Comparison like SolvableLocal or SolvableQuotient.
     * @param num SolvablePolynomial.
     * @param den SolvablePolynomial.
     * @param n SolvablePolynomial.
     * @param d SolvablePolynomial.
     * @return sign((num/den)-(n/d)).
     */
    public int compare(GenSolvablePolynomial num, GenSolvablePolynomial den, 
                       GenSolvablePolynomial n, GenSolvablePolynomial d) {
        if (n == null || n.isZERO()) {
            return num.signum();
        }
        if (num.isZERO()) {
            return -n.signum();
        }
        // assume sign(den,b.den) > 0
        int s1 = num.signum();
        int s2 = n.signum();
        int t = (s1 - s2) / 2;
        if (t != 0) {
            System.out.println("compareTo: t = " + t);
            //return t;
        }
        if (den.compareTo(d) == 0) {
            return num.compareTo(n);
        }
        GenSolvablePolynomial r, s;
        // if (den.isONE()) { }
        // if (b.den.isONE()) { }
        GenSolvablePolynomial[] oc = leftOreCond(den, d);
        if (debug) {
            System.out.println("oc[0] den =<>= oc[1] d: (" + oc[0] + ") (" + den + ") = (" + oc[1]
                            + ") (" + d + ")");
        }
        //System.out.println("oc[0] = " + oc[0]);
        //System.out.println("oc[1] = " + oc[1]);
        r = oc[0].multiply(num);
        s = oc[1].multiply(n);
        logger.info("compare: r = " + r + ", s = " + s);
        return r.compareTo(s);
    }

}


/**
 * Container for module resolution components.
 * @param  coefficient type
 */
class SolvResPart> implements Serializable {


    public final ModuleList module;


    public final ModuleList GB;


    public final ModuleList syzygy;


    /**
     * SolvResPart.
     * @param m a module list.
     * @param g a module list GB.
     * @param z a syzygy module list.
     */
    public SolvResPart(ModuleList m, ModuleList g, ModuleList z) {
        module = m;
        GB = g;
        syzygy = z;
    }


    /**
     * toString.
     */
    @Override
    public String toString() {
        StringBuffer s = new StringBuffer("SolvResPart(\n");
        s.append("module = " + module);
        s.append("\n GB = " + GB);
        s.append("\n syzygy = " + syzygy);
        s.append(")");
        return s.toString();
    }
}


/**
 * Container for polynomial resolution components.
 * @param  coefficient type
 */
class SolvResPolPart> implements Serializable {


    public final PolynomialList ideal;


    public final PolynomialList GB;


    public final ModuleList syzygy;


    /**
     * SolvResPolPart.
     * @param m a polynomial list.
     * @param g a polynomial list GB.
     * @param z a syzygy module list.
     */
    public SolvResPolPart(PolynomialList m, PolynomialList g, ModuleList z) {
        ideal = m;
        GB = g;
        syzygy = z;
    }


    /**
     * toString.
     */
    @Override
    public String toString() {
        StringBuffer s = new StringBuffer("SolvResPolPart(\n");
        s.append("ideal = " + ideal);
        s.append("\n GB = " + GB);
        s.append("\n syzygy = " + syzygy);
        s.append(")");
        return s.toString();
    }

}