001/* 002 * $Id: CharacteristicSetWu.java 4061 2012-07-27 12:03:20Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.Collections; 010import java.util.List; 011 012import org.apache.log4j.Logger; 013 014import edu.jas.poly.GenPolynomial; 015import edu.jas.poly.GenPolynomialRing; 016import edu.jas.poly.OrderedPolynomialList; 017import edu.jas.poly.PolyUtil; 018import edu.jas.structure.GcdRingElem; 019import edu.jas.ufd.GCDFactory; 020import edu.jas.ufd.GreatestCommonDivisorAbstract; 021 022 023/** 024 * Characteristic Set class acccording to Wu. Implements methods for 025 * Characteristic Sets and tests. 026 * @param <C> coefficient type 027 * @author Heinz Kredel 028 */ 029public class CharacteristicSetWu<C extends GcdRingElem<C>> implements CharacteristicSet<C> { 030 031 032 private static final Logger logger = Logger.getLogger(CharacteristicSetWu.class); 033 034 035 private static boolean debug = logger.isDebugEnabled(); 036 037 038 /** 039 * Characteristic set. According to Wu's algorithm with rereduction of 040 * leading coefficients. 041 * @param A list of generic polynomials. 042 * @return charSetWu(A). 043 */ 044 public List<GenPolynomial<C>> characteristicSet(List<GenPolynomial<C>> A) { 045 List<GenPolynomial<C>> S = new ArrayList<GenPolynomial<C>>(); 046 if (A == null || A.isEmpty()) { 047 return S; 048 } 049 GenPolynomialRing<C> pfac = A.get(0).ring; 050 if (pfac.nvar <= 1) { // take gcd 051 GreatestCommonDivisorAbstract<C> ufd = GCDFactory.<C> getImplementation(pfac.coFac); 052 GenPolynomial<C> g = ufd.gcd(A).monic(); 053 logger.info("charSet base gcd = " + g); 054 S.add(g); 055 return S; 056 } 057 // sort polynomials according to the main variable 058 GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 059 List<GenPolynomial<GenPolynomial<C>>> positiveDeg = new ArrayList<GenPolynomial<GenPolynomial<C>>>(); 060 List<GenPolynomial<C>> zeroDeg = new ArrayList<GenPolynomial<C>>(); 061 for (GenPolynomial<C> f : A) { 062 if (f.isZERO()) { 063 continue; 064 } 065 f = f.monic(); 066 if (f.isONE()) { 067 S.add(f); 068 return S; 069 } 070 GenPolynomial<GenPolynomial<C>> fr = PolyUtil.<C> recursive(rfac, f); 071 if (fr.degree(0) == 0) { 072 zeroDeg.add(fr.leadingBaseCoefficient()); 073 } else { 074 positiveDeg.add(fr); 075 } 076 } 077 if (positiveDeg.isEmpty() && zeroDeg.isEmpty()) { 078 return S; 079 } 080 // do pseudo division wrt. the main variable 081 OrderedPolynomialList<GenPolynomial<C>> opl = new OrderedPolynomialList<GenPolynomial<C>>(rfac, 082 positiveDeg); 083 List<GenPolynomial<GenPolynomial<C>>> pd = new ArrayList<GenPolynomial<GenPolynomial<C>>>(opl.list); 084 Collections.reverse(pd); // change OrderedPolynomialList to avoid 085 if (debug) { 086 logger.info("positive degrees: " + pd); 087 } 088 //System.out.println("positive degrees: " + pd); 089 //System.out.println("zero degrees: " + zeroDeg); 090 while (pd.size() > 1) { 091 GenPolynomial<GenPolynomial<C>> fr = pd.remove(0); 092 GenPolynomial<GenPolynomial<C>> qr = pd.get(0); // = get(1) 093 logger.info("pseudo remainder by deg = " + qr.degree() + " in variable " + rfac.getVars()[0]); 094 GenPolynomial<GenPolynomial<C>> rr = PolyUtil.<C> recursiveSparsePseudoRemainder(fr, qr); 095 if (rr.isZERO()) { 096 logger.warn("variety is reducible " + fr + " reduces to zero mod " + pd); 097 // replace qr by gcd(qr,fr) ? 098 continue; 099 } 100 if (rr.degree(0) == 0) { 101 zeroDeg.add(rr.leadingBaseCoefficient().monic()); 102 } else { 103 pd.add(rr); 104 pd = OrderedPolynomialList.sort(rfac, pd); 105 Collections.reverse(pd); // avoid 106 } 107 } 108 // recursion for degree zero polynomials 109 List<GenPolynomial<C>> Sp = characteristicSet(zeroDeg); // recursion 110 for (GenPolynomial<C> f : Sp) { 111 GenPolynomial<C> fp = f.extend(pfac, 0, 0L); 112 S.add(fp); 113 } 114 //logger.info("charSet recursion, Sp = " + Sp); 115 if (pd.isEmpty()) { 116 return S; 117 } 118 // rereduction of leading coefficient wrt. characteristic set according to Wu 119 GenPolynomial<GenPolynomial<C>> rr = pd.get(0); 120 GenPolynomial<C> sr = PolyUtil.<C> distribute(pfac, rr); 121 sr = PolyGBUtil.<C> topCoefficientPseudoRemainder(Sp, sr); 122 logger.info("charSet rereduced sr = " + sr); 123 if (sr.isZERO()) { 124 return S; 125 } 126 long d = sr.degree(pfac.nvar - 1); 127 //System.out.println("deg(sr): " + d + ", degv(sr): " + sr.leadingExpVector()); 128 if (d == 0) { // deg zero, invalid characteristic set, restart 129 S.add(0, sr); 130 logger.warn("reducible characteristic set, restarting with S = " + S); 131 return characteristicSet(S); 132 } 133 sr = sr.monic(); 134 S.add(0, sr); 135 return S; 136 } 137 138 139 /** 140 * Characteristic set test. 141 * @param A list of generic polynomials. 142 * @return true, if A is (at least a simple) characteristic set, else false. 143 */ 144 public boolean isCharacteristicSet(List<GenPolynomial<C>> A) { 145 if (A == null || A.isEmpty()) { 146 return true; // ? 147 } 148 GenPolynomialRing<C> pfac = A.get(0).ring; 149 if (pfac.nvar <= 1) { 150 //System.out.println("CS: pfac = " + pfac + ", A = " + A + ", A.size() = " + A.size()); 151 return A.size() <= 1; 152 } 153 if (pfac.nvar < A.size()) { 154 logger.info("not CS: pfac = " + pfac + ", A = " + A); 155 return false; 156 } 157 // select polynomials according to the main variable 158 GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 159 List<GenPolynomial<C>> zeroDeg = new ArrayList<GenPolynomial<C>>(); 160 int positiveDeg = 0; 161 for (GenPolynomial<C> f : A) { 162 if (f.isZERO()) { 163 logger.info("not CS: f = " + f); 164 return false; 165 } 166 //f = f.monic(); 167 GenPolynomial<GenPolynomial<C>> fr = PolyUtil.<C> recursive(rfac, f); 168 if (fr.degree(0) == 0) { 169 zeroDeg.add(fr.leadingBaseCoefficient()); 170 } else { 171 positiveDeg++; 172 if (positiveDeg > 1) { 173 logger.info("not CS: f = " + f + ", positiveDeg = " + positiveDeg); 174 return false; 175 } 176 } 177 } 178 return isCharacteristicSet(zeroDeg); 179 } 180 181 182 /** 183 * Characteristic set reduction. Pseudo remainder wrt. the main variable 184 * with further pseudo reduction of the leading coefficient. 185 * @param P generic polynomial. 186 * @param A list of generic polynomials as characteristic set. 187 * @return 188 * characteristicSetReductionCoeff(A,characteristicSetRemainder(A,P)) 189 */ 190 public GenPolynomial<C> characteristicSetReduction(List<GenPolynomial<C>> A, GenPolynomial<C> P) { 191 if (A == null || A.isEmpty()) { 192 return P.monic(); 193 } 194 if (P.isZERO()) { 195 return P; 196 } 197 GenPolynomial<C> R = PolyGBUtil.<C> topPseudoRemainder(A, P); 198 //System.out.println("remainder, R = " + R); 199 if (R.isZERO()) { 200 return R; 201 } 202 List<GenPolynomial<C>> Ap = PolyGBUtil.<C> zeroDegrees(A); 203 //System.out.println("Ap = " + Ap); 204 R = PolyGBUtil.<C> topCoefficientPseudoRemainder(Ap, R); 205 //System.out.println("R = " + R); 206 return R; 207 } 208 209}