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}