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}