Source code

001/*
002 * $Id: ReductionSeq.java 5869 2018-07-20 15:53:10Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.List;
009import java.util.Map;
010
011import org.apache.logging.log4j.Logger;
012import org.apache.logging.log4j.LogManager; 
013
014import edu.jas.poly.ExpVector;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.Monomial;
017import edu.jas.structure.RingElem;
018
019
020/**
021 * Polynomial reduction sequential use algorithm. Implements normalform.
022 * @param <C> coefficient type
023 * @author Heinz Kredel
024 */
025
026public class ReductionSeq<C extends RingElem<C>> // should be FieldElem<C>>
027                extends ReductionAbstract<C> {
028
029
030    private static final Logger logger = LogManager.getLogger(ReductionSeq.class);
031
032
033    /**
034     * Constructor.
035     */
036    public ReductionSeq() {
037    }
038
039
040    /**
041     * Normalform.
042     * @param Ap polynomial.
043     * @param Pp polynomial list.
044     * @return nf(Ap) with respect to Pp.
045     */
046    @SuppressWarnings("unchecked")
047    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
048        if (Pp == null || Pp.isEmpty()) {
049            return Ap;
050        }
051        if (Ap == null || Ap.isZERO()) {
052            return Ap;
053        }
054        if (!Ap.ring.coFac.isField()) {
055            throw new IllegalArgumentException("coefficients not from a field");
056        }
057        Map.Entry<ExpVector, C> m;
058        int l;
059        GenPolynomial<C>[] P;
060        synchronized (Pp) {
061            l = Pp.size();
062            P = new GenPolynomial[l];
063            //P = Pp.toArray();
064            for (int i = 0; i < Pp.size(); i++) {
065                P[i] = Pp.get(i);
066            }
067        }
068        ExpVector[] htl = new ExpVector[l];
069        Object[] lbc = new Object[l]; // want C[]
070        GenPolynomial<C>[] p = new GenPolynomial[l];
071        int i;
072        int j = 0;
073        for (i = 0; i < l; i++) {
074            p[i] = P[i];
075            m = p[i].leadingMonomial();
076            if (m != null) {
077                p[j] = p[i];
078                htl[j] = m.getKey();
079                lbc[j] = m.getValue();
080                j++;
081            }
082        }
083        l = j;
084        ExpVector e;
085        C a;
086        boolean mt = false;
087        GenPolynomial<C> R = Ap.ring.getZERO().copy();
088
089        //GenPolynomial<C> T = null;
090        //GenPolynomial<C> Q = null;
091        GenPolynomial<C> S = Ap.copy();
092        while (S.length() > 0) {
093            m = S.leadingMonomial();
094            e = m.getKey();
095            a = m.getValue();
096            for (i = 0; i < l; i++) {
097                mt = e.multipleOf(htl[i]);
098                if (mt)
099                    break;
100            }
101            if (!mt) {
102                logger.debug("irred");
103                //R = R.sum( a, e );
104                //S = S.subtract( a, e ); 
105                R.doPutToMap(e, a);
106                S.doRemoveFromMap(e, a);
107                // System.out.println(" S = " + S);
108            } else {
109                e = e.subtract(htl[i]);
110                a = a.divide((C) lbc[i]);
111                //logger.info("red div: e = " + e + ", a = " + a);
112                //Q = p[i].multiply( a, e );
113                //S = S.subtract( Q );
114                S = S.subtractMultiple(a, e, p[i]);
115            }
116        }
117        return R;
118    }
119
120
121    /**
122     * Normalform with respect to marked head terms.
123     * @param Mp leading monomial list.
124     * @param Pp polynomial list.
125     * @param Ap polynomial.
126     * @return nf(Ap) with respect to Mp+Pp.
127     */
128    @Override
129    @SuppressWarnings("unchecked")
130    public GenPolynomial<C> normalformMarked(List<Monomial<C>> Mp, List<GenPolynomial<C>> Pp,
131                    GenPolynomial<C> Ap) {
132        if (Pp == null || Pp.isEmpty()) {
133            return Ap;
134        }
135        if (Mp == null || Mp.isEmpty()) {
136            return Ap;
137        }
138        if (Ap == null || Ap.isZERO()) {
139            return Ap;
140        }
141        if (!Ap.ring.coFac.isField()) {
142            throw new IllegalArgumentException("coefficients not from a field");
143        }
144        Map.Entry<ExpVector, C> m;
145        int l;
146        GenPolynomial<C>[] P;
147        Monomial<C>[] M;
148        synchronized (Pp) {
149            l = Pp.size();
150            if (Mp.size() != l) {
151                throw new IllegalArgumentException("#Mp != #Pp: " + l + ", " + Mp.size());
152            }
153            P = new GenPolynomial[l];
154            M = new Monomial[l];
155            //P = Pp.toArray();
156            for (int i = 0; i < Pp.size(); i++) {
157                P[i] = Pp.get(i);
158                M[i] = Mp.get(i);
159            }
160        }
161        ExpVector[] htl = new ExpVector[l];
162        RingElem[] lbc = new RingElem[l];
163        GenPolynomial<C>[] p = new GenPolynomial[l];
164        int i;
165        int j = 0;
166        for (i = 0; i < l; i++) {
167            p[i] = P[i];
168            if (M[i] != null) {
169                p[j] = p[i];
170                htl[j] = M[i].exponent();
171                lbc[j] = M[i].coefficient();
172                j++;
173            }
174        }
175        l = j;
176        ExpVector e, f;
177        C a, b;
178        boolean mt = false;
179        GenPolynomial<C> R = Ap.ring.getZERO().copy();
180        GenPolynomial<C> S = Ap.copy();
181        while (S.length() > 0) {
182            m = S.leadingMonomial();
183            e = m.getKey();
184            a = m.getValue();
185            //System.out.println("NF a = " + a + ", e = " + e);
186            for (i = 0; i < l; i++) {
187                mt = e.multipleOf(htl[i]);
188                if (mt)
189                    break;
190            }
191            if (!mt) {
192                logger.debug("irred");
193                R.doAddTo(a, e); // needed, or sum
194                //R.doPutToMap(e, a); // not here
195                //S = S.subtract( a, e ); 
196                S.doRemoveFromMap(e, a);
197                // System.out.println(" S = " + S);
198            } else {
199                //System.out.println("i = "+i+", htl[i] = " + Ap.ring.toScript(htl[i]) + ", lbc[i] = " + lbc[i]  + ", p[i] = " + p[i].ring.toScript(p[i].leadingExpVector()));
200                f = e.subtract(htl[i]);
201                b = a.divide((C) lbc[i]);
202                //logger.info("red div: e = " + e + ", a = " + a + ", f = " + f + ", b = " + b);
203                //Q = p[i].multiply( a, e );
204                //S = S.subtract( Q );
205                S.doRemoveFromMap(e, a);
206                //S.doAddTo(a.negate(), e);
207                S = S.subtractMultiple(b, f, p[i]);
208                if (e.equals(S.leadingExpVector())) {
209                    throw new RuntimeException(
210                                    "something is wrong: ht not descending e = " + e + ", S = " + S);
211                }
212                //System.out.println("NF R = " + R.leadingExpVector() + ", S = " + S.leadingExpVector() + ", e = " + e + ", f = " + f + ", #S = " + S.length());
213            }
214            //System.out.println("NF R = " + R + ", S = " + S);
215        }
216        //System.out.println("NF Ap = " + Ap + " ==> " + R);
217        return R;
218    }
219
220
221    /**
222     * Normalform with recording.
223     * @param row recording matrix, is modified.
224     * @param Pp a polynomial list for reduction.
225     * @param Ap a polynomial.
226     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
227     */
228    @SuppressWarnings("unchecked")
229    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
230                    GenPolynomial<C> Ap) {
231        if (Pp == null || Pp.isEmpty()) {
232            return Ap;
233        }
234        if (Ap == null || Ap.isZERO()) {
235            return Ap;
236        }
237        if (!Ap.ring.coFac.isField()) {
238            throw new IllegalArgumentException("coefficients not from a field");
239        }
240        int l = Pp.size();
241        GenPolynomial<C>[] P = new GenPolynomial[l];
242        synchronized (Pp) {
243            //P = Pp.toArray();
244            for (int i = 0; i < Pp.size(); i++) {
245                P[i] = Pp.get(i);
246            }
247        }
248        ExpVector[] htl = new ExpVector[l];
249        Object[] lbc = new Object[l]; // want C[]
250        GenPolynomial<C>[] p = new GenPolynomial[l];
251        Map.Entry<ExpVector, C> m;
252        int j = 0;
253        int i;
254        for (i = 0; i < l; i++) {
255            p[i] = P[i];
256            m = p[i].leadingMonomial();
257            if (m != null) {
258                p[j] = p[i];
259                htl[j] = m.getKey();
260                lbc[j] = m.getValue();
261                j++;
262            }
263        }
264        l = j;
265        ExpVector e;
266        C a;
267        boolean mt = false;
268        GenPolynomial<C> zero = Ap.ring.getZERO();
269        GenPolynomial<C> R = Ap.ring.getZERO().copy();
270
271        GenPolynomial<C> fac = null;
272        // GenPolynomial<C> T = null;
273        //GenPolynomial<C> Q = null;
274        GenPolynomial<C> S = Ap.copy();
275        while (S.length() > 0) {
276            m = S.leadingMonomial();
277            e = m.getKey();
278            a = m.getValue();
279            for (i = 0; i < l; i++) {
280                mt = e.multipleOf(htl[i]);
281                if (mt)
282                    break;
283            }
284            if (!mt) {
285                //logger.debug("irred");
286                //R = R.sum( a, e );
287                //S = S.subtract( a, e ); 
288                R.doPutToMap(e, a);
289                S.doRemoveFromMap(e, a);
290                // System.out.println(" S = " + S);
291            } else {
292                e = e.subtract(htl[i]);
293                //logger.info("red div = " + e);
294                C c = (C) lbc[i];
295                a = a.divide(c);
296                //Q = p[i].multiply( a, e );
297                //S = S.subtract( Q );
298                S = S.subtractMultiple(a, e, p[i]);
299                fac = row.get(i);
300                if (fac == null) {
301                    fac = zero.sum(a, e);
302                } else {
303                    fac = fac.sum(a, e);
304                }
305                row.set(i, fac);
306            }
307        }
308        return R;
309    }
310
311}