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