001/* 002 * $Id: CharacteristicSetSimple.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 the simple algorithm, where the 025 * leading coefficients are <strong>not</strong> rereduced. Implements methods 026 * for Characteristic Sets and tests. 027 * @param <C> coefficient type 028 * @author Heinz Kredel 029 */ 030public class CharacteristicSetSimple<C extends GcdRingElem<C>> implements CharacteristicSet<C> { 031 032 033 private static final Logger logger = Logger.getLogger(CharacteristicSetSimple.class); 034 035 036 private static boolean debug = logger.isDebugEnabled(); 037 038 039 /** 040 * Characteristic set. According to the simple algorithm. The leading 041 * coefficients are <strong>not</strong> rereduced. 042 * @param A list of generic polynomials. 043 * @return charSetWu(A). 044 */ 045 public List<GenPolynomial<C>> characteristicSet(List<GenPolynomial<C>> A) { 046 List<GenPolynomial<C>> S = new ArrayList<GenPolynomial<C>>(); 047 if (A == null || A.isEmpty()) { 048 return S; 049 } 050 GenPolynomialRing<C> pfac = A.get(0).ring; 051 if (pfac.nvar <= 1) { // take gcd 052 GreatestCommonDivisorAbstract<C> ufd = GCDFactory.<C> getImplementation(pfac.coFac); 053 GenPolynomial<C> g = ufd.gcd(A).monic(); 054 logger.info("charSet base gcd = " + g); 055 S.add(g); 056 return S; 057 } 058 // sort polynomials according to the main variable 059 GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 060 List<GenPolynomial<GenPolynomial<C>>> positiveDeg = new ArrayList<GenPolynomial<GenPolynomial<C>>>(); 061 List<GenPolynomial<C>> zeroDeg = new ArrayList<GenPolynomial<C>>(); 062 for (GenPolynomial<C> f : A) { 063 if (f.isZERO()) { 064 continue; 065 } 066 f = f.monic(); 067 if (f.isONE()) { 068 S.add(f); 069 return S; 070 } 071 GenPolynomial<GenPolynomial<C>> fr = PolyUtil.<C> recursive(rfac, f); 072 if (fr.degree(0) == 0) { 073 zeroDeg.add(fr.leadingBaseCoefficient()); 074 } else { 075 positiveDeg.add(fr); 076 } 077 } 078 if (positiveDeg.isEmpty() && zeroDeg.isEmpty()) { 079 return S; 080 } 081 // do pseudo division wrt. the main variable 082 OrderedPolynomialList<GenPolynomial<C>> opl = new OrderedPolynomialList<GenPolynomial<C>>(rfac, 083 positiveDeg); 084 List<GenPolynomial<GenPolynomial<C>>> pd = new ArrayList<GenPolynomial<GenPolynomial<C>>>(opl.list); 085 Collections.reverse(pd); // change OrderedPolynomialList to avoid 086 if (debug) { 087 logger.info("positive degrees: " + pd); 088 } 089 //System.out.println("positive degrees: " + pd); 090 //System.out.println("zero degrees: " + zeroDeg); 091 while (pd.size() > 1) { 092 GenPolynomial<GenPolynomial<C>> fr = pd.remove(0); 093 GenPolynomial<GenPolynomial<C>> qr = pd.get(0); // = get(1) 094 logger.info("pseudo remainder by deg = " + qr.degree() + " in variable " + rfac.getVars()[0]); 095 GenPolynomial<GenPolynomial<C>> rr = PolyUtil.<C> recursiveSparsePseudoRemainder(fr, qr); 096 if (rr.isZERO()) { 097 logger.warn("variety is reducible"); 098 // replace qr by gcd(qr,fr) ? 099 continue; 100 } 101 if (rr.degree(0) == 0) { 102 zeroDeg.add(rr.leadingBaseCoefficient().monic()); 103 } else { 104 pd.add(rr); 105 pd = OrderedPolynomialList.sort(rfac, pd); 106 Collections.reverse(pd); // avoid 107 } 108 } 109 // recursion for degree zero polynomials 110 List<GenPolynomial<C>> Sp = characteristicSet(zeroDeg); // recursion 111 for (GenPolynomial<C> f : Sp) { 112 GenPolynomial<C> fp = f.extend(pfac, 0, 0L); 113 S.add(fp); 114 } 115 //logger.info("charSet recursion, Sp = " + Sp); 116 if (pd.isEmpty()) { 117 return S; 118 } 119 GenPolynomial<GenPolynomial<C>> rr = pd.get(0); 120 GenPolynomial<C> sr = PolyUtil.<C> distribute(pfac, rr); 121 sr = sr.monic(); 122 // no rereduction of leading coefficient wrt. characteristic set. 123 S.add(0, sr); 124 return S; 125 } 126 127 128 /** 129 * Characteristic set test. 130 * @param A list of generic polynomials. 131 * @return true, if A is (at least a simple) characteristic set, else false. 132 */ 133 public boolean isCharacteristicSet(List<GenPolynomial<C>> A) { 134 if (A == null || A.isEmpty()) { 135 return true; // ? 136 } 137 GenPolynomialRing<C> pfac = A.get(0).ring; 138 if (pfac.nvar <= 1) { 139 return A.size() <= 1; 140 } 141 if (pfac.nvar < A.size()) { 142 return false; 143 } 144 // select polynomials according to the main variable 145 GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 146 List<GenPolynomial<C>> zeroDeg = new ArrayList<GenPolynomial<C>>(); 147 int positiveDeg = 0; 148 for (GenPolynomial<C> f : A) { 149 if (f.isZERO()) { 150 return false; 151 } 152 //f = f.monic(); 153 GenPolynomial<GenPolynomial<C>> fr = PolyUtil.<C> recursive(rfac, f); 154 if (fr.degree(0) == 0) { 155 zeroDeg.add(fr.leadingBaseCoefficient()); 156 } else { 157 positiveDeg++; 158 if (positiveDeg > 1) { 159 return false; 160 } 161 } 162 } 163 return isCharacteristicSet(zeroDeg); 164 } 165 166 167 /** 168 * Characteristic set reduction. Pseudo remainder wrt. the main variable. 169 * @param P generic polynomial. 170 * @param A list of generic polynomials as characteristic set. 171 * @return characteristicSetRemainder(A,P) 172 */ 173 public GenPolynomial<C> characteristicSetReduction(List<GenPolynomial<C>> A, GenPolynomial<C> P) { 174 if (A == null || A.isEmpty()) { 175 return P.monic(); 176 } 177 if (P.isZERO()) { 178 return P; 179 } 180 GenPolynomial<C> R = PolyGBUtil.<C> topPseudoRemainder(A, P); 181 R = R.monic(); 182 //System.out.println("remainder, R = " + R); 183 return R; 184 } 185 186}