001/*
002 * $Id: GreatestCommonDivisorSyzygy.java 5872 2018-07-20 16:01:46Z kredel $
003 */
004
005package edu.jas.fd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.logging.log4j.Logger;
012import org.apache.logging.log4j.LogManager; 
013
014import edu.jas.gb.SolvableGroebnerBaseAbstract;
015import edu.jas.gb.SolvableGroebnerBaseSeq;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenSolvablePolynomial;
018import edu.jas.structure.GcdRingElem;
019import edu.jas.structure.RingFactory;
020
021
022/**
023 * (Non-unique) factorization domain greatest common divisor common algorithms
024 * with syzygy computation. The implementation uses solvable syzygy gcd
025 * computation.
026 * @param <C> coefficient type
027 * @author Heinz Kredel
028 */
029
030public class GreatestCommonDivisorSyzygy<C extends GcdRingElem<C>> extends GreatestCommonDivisorAbstract<C> {
031
032
033    private static final Logger logger = LogManager.getLogger(GreatestCommonDivisorSyzygy.class);
034
035
036    private static final boolean debug = true; //logger.isDebugEnabled();
037
038
039    /**
040     * Constructor.
041     * @param cf coefficient ring.
042     */
043    public GreatestCommonDivisorSyzygy(RingFactory<C> cf) {
044        super(cf);
045    }
046
047
048    /**
049     * Left univariate GenSolvablePolynomial greatest common divisor.
050     * @param P univariate GenSolvablePolynomial.
051     * @param S univariate GenSolvablePolynomial.
052     * @return gcd(P,S) with P = P'*gcd(P,S) and S = S'*gcd(P,S).
053     */
054    @Override
055    public GenSolvablePolynomial<C> leftBaseGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
056        return leftGcd(P, S);
057    }
058
059
060    /**
061     * Right univariate GenSolvablePolynomial greatest common divisor.
062     * @param P univariate GenSolvablePolynomial.
063     * @param S univariate GenSolvablePolynomial.
064     * @return gcd(P,S) with P = P'*gcd(P,S) and S = S'*gcd(P,S).
065     */
066    @Override
067    public GenSolvablePolynomial<C> rightBaseGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
068        return rightGcd(P, S);
069    }
070
071
072    /**
073     * Left GenSolvablePolynomial greatest common divisor.
074     * @param P GenSolvablePolynomial.
075     * @param S GenSolvablePolynomial.
076     * @return gcd(P,S) with P = P'*gcd(P,S) and S = S'*gcd(P,S).
077     */
078    @Override
079    public GenSolvablePolynomial<C> leftGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
080        if (S == null || S.isZERO()) {
081            return P;
082        }
083        if (P == null || P.isZERO()) {
084            return S;
085        }
086        if (P.isConstant()) {
087            return P.ring.getONE();
088        }
089        if (S.isConstant()) {
090            return P.ring.getONE();
091        }
092        List<GenSolvablePolynomial<C>> A = new ArrayList<GenSolvablePolynomial<C>>(2);
093        A.add(P);
094        A.add(S);
095        SolvableGroebnerBaseAbstract<C> sbb = new SolvableGroebnerBaseSeq<C>();
096        logger.info("left syzGcd computing GB: " + A);
097        List<GenSolvablePolynomial<C>> G = sbb.rightGB(A); //not: leftGB, not: sbb.twosidedGB(A);
098        if (debug) {
099            logger.info("G = " + G);
100        }
101        if (G.size() == 1) {
102            return G.get(0);
103        }
104        logger.info("gcd not determined, set to 1: " + G); // + ", A = " + A);
105        return P.ring.getONE();
106    }
107
108
109    /**
110     * Right GenSolvablePolynomial right greatest common divisor.
111     * @param P GenSolvablePolynomial.
112     * @param S GenSolvablePolynomial.
113     * @return gcd(P,S) with P = gcd(P,S)*P' and S = gcd(P,S)*S'.
114     */
115    @Override
116    public GenSolvablePolynomial<C> rightGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
117        if (S == null || S.isZERO()) {
118            return P;
119        }
120        if (P == null || P.isZERO()) {
121            return S;
122        }
123        if (P.isConstant()) {
124            return P.ring.getONE();
125        }
126        if (S.isConstant()) {
127            return P.ring.getONE();
128        }
129        List<GenSolvablePolynomial<C>> A = new ArrayList<GenSolvablePolynomial<C>>(2);
130        A.add(P);
131        A.add(S);
132        SolvableGroebnerBaseAbstract<C> sbb = new SolvableGroebnerBaseSeq<C>();
133        logger.info("left syzGcd computing GB: " + A);
134        List<GenSolvablePolynomial<C>> G = sbb.leftGB(A); //not: sbb.twosidedGB(A);
135        if (debug) {
136            logger.info("G = " + G);
137        }
138        if (G.size() == 1) {
139            return G.get(0);
140        }
141        logger.info("gcd not determined, set to 1: " + G); // + ", A = " + A);
142        return P.ring.getONE();
143    }
144
145
146    /**
147     * Univariate GenSolvablePolynomial left recursive greatest common divisor.
148     * @param P univariate recursive GenSolvablePolynomial.
149     * @param S univariate recursive GenSolvablePolynomial.
150     * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where
151     *         deg_main(p) = deg_main(s) == 0.
152     */
153    @Override
154    public GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveUnivariateGcd(
155                    GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) {
156        if (S == null || S.isZERO()) {
157            return P;
158        }
159        if (P == null || P.isZERO()) {
160            return S;
161        }
162        if (P.ring.nvar > 1) {
163            throw new IllegalArgumentException("no univariate polynomial");
164        }
165        if (P.isConstant()) {
166            return P.ring.getONE();
167        }
168        if (S.isConstant()) {
169            return P.ring.getONE();
170        }
171        List<GenSolvablePolynomial<GenPolynomial<C>>> A = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>(
172                        2);
173        A.add(P);
174        A.add(S);
175        SolvableGroebnerBaseAbstract<GenPolynomial<C>> sbb = new SolvableGroebnerBaseSeq<GenPolynomial<C>>();
176        logger.info("left syzGcd computing GB: " + A);
177        // will not work, not field
178        List<GenSolvablePolynomial<GenPolynomial<C>>> G = sbb.rightGB(A); //not: leftGB, not: sbb.twosidedGB(A);
179        if (debug) {
180            logger.info("G = " + G);
181        }
182        if (G.size() == 1) {
183            return G.get(0);
184        }
185        logger.info("gcd not determined, set to 1: " + G); // + ", A = " + A);
186        return P.ring.getONE();
187    }
188
189
190    /**
191     * Univariate GenSolvablePolynomial right recursive greatest common divisor.
192     * @param P univariate recursive GenSolvablePolynomial.
193     * @param S univariate recursive GenSolvablePolynomial.
194     * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where
195     *         deg_main(p) = deg_main(s) == 0.
196     */
197    @Override
198    public GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveUnivariateGcd(
199                    GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) {
200        if (S == null || S.isZERO()) {
201            return P;
202        }
203        if (P == null || P.isZERO()) {
204            return S;
205        }
206        if (P.ring.nvar > 1) {
207            throw new IllegalArgumentException("no univariate polynomial");
208        }
209        if (P.isConstant()) {
210            return P.ring.getONE();
211        }
212        if (S.isConstant()) {
213            return P.ring.getONE();
214        }
215        List<GenSolvablePolynomial<GenPolynomial<C>>> A = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>(
216                        2);
217        A.add(P);
218        A.add(S);
219        SolvableGroebnerBaseAbstract<GenPolynomial<C>> sbb = new SolvableGroebnerBaseSeq<GenPolynomial<C>>();
220        logger.info("right syzGcd computing GB: " + A);
221        // will not work, not field
222        List<GenSolvablePolynomial<GenPolynomial<C>>> G = sbb.leftGB(A); //not: sbb.twosidedGB(A);
223        if (debug) {
224            logger.info("G = " + G);
225        }
226        if (G.size() == 1) {
227            return G.get(0);
228        }
229        logger.info("gcd not determined, set to 1: " + G); // + ", A = " + A);
230        return P.ring.getONE();
231    }
232
233}