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