Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.logging.log4j.LogManager;
012import org.apache.logging.log4j.Logger;
013
014import edu.jas.gb.SolvableGroebnerBaseAbstract;
015import edu.jas.gb.SolvableGroebnerBaseSeq;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.GenSolvablePolynomial;
019import edu.jas.poly.GenSolvablePolynomialRing;
020import edu.jas.poly.PolyUtil;
021import edu.jas.structure.GcdRingElem;
022
023
024/**
025 * Package gb and gbufd utilities.
026 * @author Heinz Kredel
027 */
028
029public class PolyModUtil {
030
031
032    private static final Logger logger = LogManager.getLogger(PolyModUtil.class);
033
034
035    private static final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Least common multiple via ideal intersection.
040     * @param r solvable polynomial ring.
041     * @param n first solvable polynomial.
042     * @param d second solvable polynomial.
043     * @return lcm(n,d)
044     */
045    public static <C extends GcdRingElem<C>> GenSolvablePolynomial<C> syzLcm(GenSolvablePolynomialRing<C> r,
046                    GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) {
047        if (n.isZERO()) {
048            return n;
049        }
050        if (d.isZERO()) {
051            return d;
052        }
053        if (n.isONE()) {
054            return d;
055        }
056        if (d.isONE()) {
057            return n;
058        }
059        List<GenSolvablePolynomial<C>> A = new ArrayList<GenSolvablePolynomial<C>>(1);
060        A.add(n);
061        List<GenSolvablePolynomial<C>> B = new ArrayList<GenSolvablePolynomial<C>>(1);
062        B.add(d);
063        List<GenSolvablePolynomial<C>> c = PolyGBUtil.<C> intersect(r, A, B);
064        //if (c.size() != 1) {
065        // SolvableSyzygyAbstract<C> sz = new SolvableSyzygyAbstract<C>();
066        // GenSolvablePolynomial<C>[] oc = sz.leftOreCond(n,d);
067        // GenSolvablePolynomial<C> nc = oc[0].multiply(n);
068        // System.out.println("nc = " + nc);
069        // return nc;
070        //}
071        GenSolvablePolynomial<C> lcm = null;
072        for (GenSolvablePolynomial<C> p : c) {
073            if (p == null || p.isZERO()) {
074                continue;
075            }
076            //System.out.println("p = " + p);
077            if (lcm == null) {
078                lcm = p;
079                continue;
080            }
081            if (lcm.compareTo(p) > 0) {
082                lcm = p;
083            }
084        }
085        if (lcm == null) {
086            throw new RuntimeException("this cannot happen: lcm == null: " + c);
087        }
088        return lcm;
089    }
090
091
092    /**
093     * Greatest common divisor via least common multiple.
094     * @param r solvable polynomial ring.
095     * @param n first solvable polynomial.
096     * @param d second solvable polynomial.
097     * @return gcd(n,d)
098     */
099    public static <C extends GcdRingElem<C>> GenSolvablePolynomial<C> syzGcd(GenSolvablePolynomialRing<C> r,
100                    GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) {
101        return syzLeftGcd(r, n, d);
102    }
103
104
105    /**
106     * Left greatest common divisor via least common multiple.
107     * @param r solvable polynomial ring.
108     * @param n first solvable polynomial.
109     * @param d second solvable polynomial.
110     * @return gcd(n,d)
111     */
112    public static <C extends GcdRingElem<C>> GenSolvablePolynomial<C> syzLeftGcd(
113                    GenSolvablePolynomialRing<C> r, GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) {
114
115        if (n.isZERO()) {
116            return d;
117        }
118        if (d.isZERO()) {
119            return n;
120        }
121        if (n.isConstant()) {
122            return r.getONE();
123        }
124        if (d.isConstant()) {
125            return r.getONE();
126        }
127        if (n.totalDegree() > 3 || d.totalDegree() > 3) { // how avoid too long running GBs ?
128            //if (n.totalDegree() + d.totalDegree() > 6) { // how avoid too long running GBs ?
129            // && n.length() < 10 && d.length() < 10
130            logger.warn("skipping GB computation: degs = {}, {}", n.totalDegree(), d.totalDegree());
131            return r.getONE();
132        }
133        List<GenSolvablePolynomial<C>> A = new ArrayList<GenSolvablePolynomial<C>>(2);
134        A.add(n);
135        A.add(d);
136        SolvableGroebnerBaseAbstract<C> sbb = new SolvableGroebnerBaseSeq<C>();
137        logger.warn("left syzGcd computing GB: {}", A);
138        List<GenSolvablePolynomial<C>> G = sbb.rightGB(A); //not: leftGB, not: sbb.twosidedGB(A);
139        if (debug) {
140            logger.info("G = {}", G);
141        }
142        if (G.size() == 1) {
143            return G.get(0);
144        }
145        logger.warn("gcd not determined, set to 1: {}", G); // + ", A = {}", A);
146        return r.getONE();
147    }
148
149
150    /**
151     * Right greatest common divisor via least common multiple.
152     * @param r solvable polynomial ring.
153     * @param n first solvable polynomial.
154     * @param d second solvable polynomial.
155     * @return gcd(n,d)
156     */
157    public static <C extends GcdRingElem<C>> GenSolvablePolynomial<C> syzRightGcd(
158                    GenSolvablePolynomialRing<C> r, GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) {
159
160        if (n.isZERO()) {
161            return d;
162        }
163        if (d.isZERO()) {
164            return n;
165        }
166        if (n.isConstant()) {
167            return r.getONE();
168        }
169        if (d.isConstant()) {
170            return r.getONE();
171        }
172        if (n.totalDegree() > 3 || d.totalDegree() > 3) { // how avoid too long running GBs ?
173            //if (n.totalDegree() + d.totalDegree() > 6) { // how avoid too long running GBs ?
174            // && n.length() < 10 && d.length() < 10
175            logger.warn("skipping GB computation: degs = {}, {}", n.totalDegree(), d.totalDegree());
176            return r.getONE();
177        }
178        List<GenSolvablePolynomial<C>> A = new ArrayList<GenSolvablePolynomial<C>>(2);
179        A.add(n);
180        A.add(d);
181        SolvableGroebnerBaseAbstract<C> sbb = new SolvableGroebnerBaseSeq<C>();
182        logger.warn("right syzGcd computing GB: {}", A);
183        List<GenSolvablePolynomial<C>> G = sbb.leftGB(A); // not: sbb.twosidedGB(A);
184        if (debug) {
185            logger.info("G = {}", G);
186        }
187        if (G.size() == 1) {
188            return G.get(0);
189        }
190        logger.warn("gcd not determined, set to 1: {}", G); // + ", A = {}", A);
191        return r.getONE();
192    }
193
194
195    /**
196     * Greatest common divisor and cofactors via least common multiple and
197     * reduction.
198     * @param r solvable polynomial ring.
199     * @param n first solvable polynomial.
200     * @param d second solvable polynomial.
201     * @return [ g=gcd(n,d), n/g, d/g ]
202     */
203    @SuppressWarnings({ "unchecked", "cast" })
204    public static <C extends GcdRingElem<C>> GenSolvablePolynomial<C>[] syzGcdCofactors(
205                    GenSolvablePolynomialRing<C> r, GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) {
206        GenSolvablePolynomial<C>[] res = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[3];
207        res[0] = PolyModUtil.<C> syzGcd(r, n, d);
208        res[1] = n;
209        res[2] = d;
210        if (res[0].isONE()) {
211            return res;
212        }
213        GenSolvablePolynomial<C>[] nqr = PolyGBUtil.<C> quotientRemainder(n, res[0]);
214        if (!nqr[1].isZERO()) {
215            res[0] = r.getONE();
216            return res;
217        }
218        GenSolvablePolynomial<C>[] dqr = PolyGBUtil.<C> quotientRemainder(d, res[0]);
219        if (!dqr[1].isZERO()) {
220            res[0] = r.getONE();
221            return res;
222        }
223        res[1] = nqr[0];
224        res[2] = dqr[0];
225        return res;
226    }
227
228
229    /**
230     * Least common multiple. Just for fun, is not efficient.
231     * @param r polynomial ring.
232     * @param n first polynomial.
233     * @param d second polynomial.
234     * @return lcm(n,d)
235     */
236    public static <C extends GcdRingElem<C>> GenPolynomial<C> syzLcm(GenPolynomialRing<C> r,
237                    GenPolynomial<C> n, GenPolynomial<C> d) {
238        List<GenPolynomial<C>> A = new ArrayList<GenPolynomial<C>>(1);
239        A.add(n);
240        List<GenPolynomial<C>> B = new ArrayList<GenPolynomial<C>>(1);
241        B.add(d);
242        List<GenPolynomial<C>> c = PolyGBUtil.<C> intersect(r, A, B);
243        if (c.size() != 1) {
244            logger.warn("lcm not unique: {}", c);
245            //throw new RuntimeException("lcm not unique: " + c);
246        }
247        GenPolynomial<C> lcm = c.get(0);
248        return lcm;
249    }
250
251
252    /**
253     * Greatest common divisor. Just for fun, is not efficient.
254     * @param r polynomial ring.
255     * @param n first polynomial.
256     * @param d second polynomial.
257     * @return gcd(n,d)
258     */
259    public static <C extends GcdRingElem<C>> GenPolynomial<C> syzGcd(GenPolynomialRing<C> r,
260                    GenPolynomial<C> n, GenPolynomial<C> d) {
261        if (n.isZERO()) {
262            return d;
263        }
264        if (d.isZERO()) {
265            return n;
266        }
267        if (n.isONE()) {
268            return n;
269        }
270        if (d.isONE()) {
271            return d;
272        }
273        GenPolynomial<C> p = n.multiply(d);
274        GenPolynomial<C> lcm = syzLcm(r, n, d);
275        GenPolynomial<C> gcd = PolyUtil.<C> basePseudoDivide(p, lcm);
276        return gcd;
277    }
278
279
280}