001/*
002 * $Id: CharacteristicSetWu.java 5870 2018-07-20 15:56:23Z 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.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.GenPolynomialRing;
017import edu.jas.poly.OrderedPolynomialList;
018import edu.jas.poly.PolyUtil;
019import edu.jas.structure.GcdRingElem;
020import edu.jas.ufd.GCDFactory;
021import edu.jas.ufd.GreatestCommonDivisorAbstract;
022
023
024/**
025 * Characteristic Set class acccording to Wu. Implements methods for
026 * Characteristic Sets and tests.
027 * @param <C> coefficient type
028 * @author Heinz Kredel
029 */
030public class CharacteristicSetWu<C extends GcdRingElem<C>> implements CharacteristicSet<C> {
031
032
033    private static final Logger logger = LogManager.getLogger(CharacteristicSetWu.class);
034
035
036    private static final boolean debug = logger.isDebugEnabled();
037
038
039    /**
040     * Characteristic set. According to Wu's algorithm with rereduction of
041     * leading coefficients.
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 " + fr + " reduces to zero mod " + pd);
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        // rereduction of leading coefficient wrt. characteristic set according to Wu
120        GenPolynomial<GenPolynomial<C>> rr = pd.get(0);
121        GenPolynomial<C> sr = PolyUtil.<C> distribute(pfac, rr);
122        sr = PolyGBUtil.<C> topCoefficientPseudoRemainder(Sp, sr);
123        logger.info("charSet rereduced sr = " + sr);
124        if (sr.isZERO()) {
125            return S;
126        }
127        long d = sr.degree(pfac.nvar - 1);
128        //System.out.println("deg(sr): " + d + ", degv(sr): " + sr.leadingExpVector());
129        if (d == 0) { // deg zero, invalid characteristic set, restart
130            S.add(0, sr);
131            logger.warn("reducible characteristic set, restarting with S = " + S);
132            return characteristicSet(S);
133        }
134        sr = sr.monic();
135        S.add(0, sr);
136        return S;
137    }
138
139
140    /**
141     * Characteristic set test.
142     * @param A list of generic polynomials.
143     * @return true, if A is (at least a simple) characteristic set, else false.
144     */
145    public boolean isCharacteristicSet(List<GenPolynomial<C>> A) {
146        if (A == null || A.isEmpty()) {
147            return true; // ?
148        }
149        GenPolynomialRing<C> pfac = A.get(0).ring;
150        if (pfac.nvar <= 1) {
151            //System.out.println("CS: pfac = " + pfac + ", A = " + A + ", A.size() = " + A.size());
152            return A.size() <= 1;
153        }
154        if (pfac.nvar < A.size()) {
155            logger.info("not CS: pfac = " + pfac + ", A = " + A);
156            return false;
157        }
158        // select polynomials according to the main variable
159        GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1);
160        List<GenPolynomial<C>> zeroDeg = new ArrayList<GenPolynomial<C>>();
161        int positiveDeg = 0;
162        for (GenPolynomial<C> f : A) {
163            if (f.isZERO()) {
164                logger.info("not CS: f = " + f);
165                return false;
166            }
167            //f = f.monic();
168            GenPolynomial<GenPolynomial<C>> fr = PolyUtil.<C> recursive(rfac, f);
169            if (fr.degree(0) == 0) {
170                zeroDeg.add(fr.leadingBaseCoefficient());
171            } else {
172                positiveDeg++;
173                if (positiveDeg > 1) {
174                    logger.info("not CS: f = " + f + ", positiveDeg = " + positiveDeg);
175                    return false;
176                }
177            }
178        }
179        return isCharacteristicSet(zeroDeg);
180    }
181
182
183    /**
184     * Characteristic set reduction. Pseudo remainder wrt. the main variable
185     * with further pseudo reduction of the leading coefficient.
186     * @param P generic polynomial.
187     * @param A list of generic polynomials as characteristic set.
188     * @return 
189     *         characteristicSetReductionCoeff(A,characteristicSetRemainder(A,P))
190     */
191    public GenPolynomial<C> characteristicSetReduction(List<GenPolynomial<C>> A, GenPolynomial<C> P) {
192        if (A == null || A.isEmpty()) {
193            return P.monic();
194        }
195        if (P.isZERO()) {
196            return P;
197        }
198        GenPolynomial<C> R = PolyGBUtil.<C> topPseudoRemainder(A, P);
199        //System.out.println("remainder, R = " + R);
200        if (R.isZERO()) {
201            return R;
202        }
203        List<GenPolynomial<C>> Ap = PolyGBUtil.<C> zeroDegrees(A);
204        //System.out.println("Ap = " + Ap);
205        R = PolyGBUtil.<C> topCoefficientPseudoRemainder(Ap, R);
206        //System.out.println("R = " + R);
207        return R;
208    }
209
210}