001/*
002 * $Id$
003 */
004
005package edu.jas.gbufd;
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.gb.ReductionAbstract;
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.PolyUtil;
018import edu.jas.structure.RingElem;
019
020
021/**
022 * Polynomial pseudo reduction sequential use algorithm. Coefficients of
023 * polynomials must not be from a field, i.e. the fraction free reduction is
024 * implemented. Implements normalform.
025 * @param <C> coefficient type
026 * @author Heinz Kredel
027 */
028
029public class PseudoReductionSeq<C extends RingElem<C>> extends ReductionAbstract<C> implements
030                PseudoReduction<C> {
031
032
033    private static final Logger logger = LogManager.getLogger(PseudoReductionSeq.class);
034
035
036    private static final boolean debug = logger.isDebugEnabled();
037
038
039    /**
040     * Constructor.
041     */
042    public PseudoReductionSeq() {
043    }
044
045
046    /**
047     * Normalform.
048     * @param Ap polynomial.
049     * @param Pp polynomial list.
050     * @return nf(Ap) with respect to Pp.
051     */
052    @SuppressWarnings("unchecked")
053    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
054        if (Pp == null || Pp.isEmpty()) {
055            return Ap;
056        }
057        if (Ap == null || Ap.isZERO()) {
058            return Ap;
059        }
060        Map.Entry<ExpVector, C> m;
061        GenPolynomial<C>[] P = new GenPolynomial[0];
062        synchronized (Pp) {
063            P = Pp.toArray(P);
064        }
065        int l = P.length;
066        ExpVector[] htl = new ExpVector[l];
067        C[] lbc = (C[]) new RingElem[l];
068        GenPolynomial<C>[] p = new GenPolynomial[l];
069        int i;
070        int j = 0;
071        for (i = 0; i < l; i++) {
072            if (P[i] == null) {
073                continue;
074            }
075            p[i] = P[i];
076            m = p[i].leadingMonomial();
077            if (m != null) {
078                p[j] = p[i];
079                htl[j] = m.getKey();
080                lbc[j] = m.getValue();
081                j++;
082            }
083        }
084        l = j;
085        ExpVector e, f;
086        C a, b;
087        boolean mt = false;
088        GenPolynomial<C> R = Ap.ring.getZERO().copy();
089
090        GenPolynomial<C> S = Ap.copy();
091        while (S.length() > 0) {
092            m = S.leadingMonomial();
093            e = m.getKey();
094            a = m.getValue();
095            for (i = 0; i < l; i++) {
096                mt = e.multipleOf(htl[i]);
097                if (mt)
098                    break;
099            }
100            if (!mt) {
101                //logger.debug("irred");
102                //R = R.sum(a, e);
103                //S = S.subtract(a, e);
104                R.doPutToMap(e, a);
105                S.doRemoveFromMap(e, a);
106                //System.out.println(" S = " + S);
107            } else {
108                f = e.subtract(htl[i]);
109                //logger.info("red div = {}", e);
110                @SuppressWarnings("unchecked")
111                C c = (C) lbc[i];
112                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
113                    b = a.divide(c);
114                    GenPolynomial<C> Sp = S.subtractMultiple(b, f, p[i]);
115                    if (e.equals(Sp.leadingExpVector())) { // TODO: avoid if possible
116                        logger.info("degree not descending: S = {}, Sp = {}", S, Sp);
117                        R = R.multiply(c);
118                        //S = S.multiply(c);
119                        Sp = S.scaleSubtractMultiple(c, a, f, p[i]);
120                    }
121                    S = Sp;                    
122                } else {
123                    R = R.multiply(c);
124                    //S = S.multiply(c);
125                    S = S.scaleSubtractMultiple(c, a, f, p[i]);
126                }
127                //Q = p[i].multiply(a, e);
128                //S = S.subtract(Q);
129            }
130        }
131        return R;
132    }
133
134
135    /**
136     * Normalform recursive.
137     * @param Ap recursive polynomial.
138     * @param Pp recursive polynomial list.
139     * @return nf(Ap) with respect to Pp.
140     */
141    @SuppressWarnings("unchecked")
142    public GenPolynomial<GenPolynomial<C>> normalformRecursive(List<GenPolynomial<GenPolynomial<C>>> Pp,
143                    GenPolynomial<GenPolynomial<C>> Ap) {
144        if (Pp == null || Pp.isEmpty()) {
145            return Ap;
146        }
147        if (Ap == null || Ap.isZERO()) {
148            return Ap;
149        }
150        Map.Entry<ExpVector, GenPolynomial<C>> m;
151        GenPolynomial<GenPolynomial<C>>[] P = new GenPolynomial[0];
152        synchronized (Pp) {
153            P = Pp.toArray(P);
154        }
155        int l = P.length;
156        ExpVector[] htl = new ExpVector[l];
157        GenPolynomial<C>[] lbc = (GenPolynomial<C>[]) new GenPolynomial[l];
158        GenPolynomial<GenPolynomial<C>>[] p = new GenPolynomial[l];
159        int i;
160        int j = 0;
161        for (i = 0; i < l; i++) {
162            if (P[i] == null) {
163                continue;
164            }
165            p[i] = P[i];
166            m = p[i].leadingMonomial();
167            if (m != null) {
168                p[j] = p[i];
169                htl[j] = m.getKey();
170                lbc[j] = m.getValue();
171                j++;
172            }
173        }
174        l = j;
175        ExpVector e, f;
176        GenPolynomial<C> a, b;
177        boolean mt = false;
178        GenPolynomial<GenPolynomial<C>> R = Ap.ring.getZERO().copy();
179
180        GenPolynomial<GenPolynomial<C>> S = Ap.copy();
181        while (S.length() > 0) {
182            m = S.leadingMonomial();
183            e = m.getKey();
184            a = m.getValue();
185            for (i = 0; i < l; i++) {
186                mt = e.multipleOf(htl[i]);
187                if (mt)
188                    break;
189            }
190            if (!mt) {
191                //logger.debug("irred");
192                //R = R.sum(a, e);
193                //S = S.subtract(a, e);
194                R.doPutToMap(e, a);
195                S.doRemoveFromMap(e, a);
196                //System.out.println(" S = " + S);
197            } else {
198                f = e.subtract(htl[i]);
199                if (debug) {
200                    logger.info("red div = {}", f);
201                    //logger.info("red a = {}", a);
202                }
203                GenPolynomial<C> c = (GenPolynomial<C>) lbc[i];
204                //if (a.remainder(c).isZERO()) { //c.isUnit() ) {
205                if (PolyUtil.<C> baseSparsePseudoRemainder(a, c).isZERO()) { //c.isUnit() ) {
206                    if (debug) {
207                        logger.info("red c = {}", c);
208                    }
209                    //a = a.divide(c);
210                    b = PolyUtil.<C> basePseudoDivide(a, c);
211                    GenPolynomial<GenPolynomial<C>> Sp = S.subtractMultiple(b, f, p[i]);
212                    if (e.equals(Sp.leadingExpVector())) { // TODO: avoid if possible
213                        //throw new RuntimeException("degree not descending");
214                        logger.info("degree not descending: S = {}, Sp = {}", S, Sp);
215                        R = R.multiply(c);
216                        //S = S.multiply(c);
217                        Sp = S.scaleSubtractMultiple(c, a, f, p[i]);
218                    }
219                    S = Sp;
220                } else {
221                    R = R.multiply(c);
222                    //S = S.multiply(c);
223                    S = S.scaleSubtractMultiple(c, a, f, p[i]);
224                }
225                //Q = p[i].multiply(a, e);
226                //S = S.subtract(Q);
227            }
228        }
229        return R;
230    }
231
232
233    /**
234     * Normalform with recording. <b>Note:</b> Only meaningful if all divisions
235     * are exact. Compute first the multiplication factor <code>m</code> with
236     * <code>normalform(Pp,Ap,m)</code>, then call this method with
237     * <code>normalform(row,Pp,m*Ap)</code>.
238     * @param row recording matrix, is modified.
239     * @param Pp a polynomial list for reduction.
240     * @param Ap a polynomial.
241     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
242     */
243    @SuppressWarnings("unchecked")
244    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
245                    GenPolynomial<C> Ap) {
246        if (Pp == null || Pp.isEmpty()) {
247            return Ap;
248        }
249        if (Ap == null || Ap.isZERO()) {
250            return Ap;
251        }
252        GenPolynomial<C>[] P = new GenPolynomial[0];
253        synchronized (Pp) {
254            P = Pp.toArray(P);
255        }
256        int l = P.length;
257        ExpVector[] htl = new ExpVector[l];
258        Object[] lbc = new Object[l]; // want C 
259        GenPolynomial<C>[] p = new GenPolynomial[l];
260        Map.Entry<ExpVector, C> m;
261        int j = 0;
262        int i;
263        for (i = 0; i < l; i++) {
264            p[i] = P[i];
265            m = p[i].leadingMonomial();
266            if (m != null) {
267                p[j] = p[i];
268                htl[j] = m.getKey();
269                lbc[j] = m.getValue();
270                j++;
271            }
272        }
273        l = j;
274        ExpVector e;
275        C a;
276        boolean mt = false;
277        GenPolynomial<C> zero = Ap.ring.getZERO();
278        GenPolynomial<C> R = Ap.ring.getZERO().copy();
279        GenPolynomial<C> fac = null;
280        GenPolynomial<C> S = Ap.copy();
281        while (S.length() > 0) {
282            m = S.leadingMonomial();
283            e = m.getKey();
284            a = m.getValue();
285            for (i = 0; i < l; i++) {
286                mt = e.multipleOf(htl[i]);
287                if (mt)
288                    break;
289            }
290            if (!mt) {
291                //logger.debug("irred");
292                //R = R.sum(a, e);
293                //S = S.subtract(a, e);
294                R.doPutToMap(e, a);
295                S.doRemoveFromMap(e, a);
296                // System.out.println(" S = " + S);
297            } else {
298                e = e.subtract(htl[i]);
299                //logger.info("red div = {}", e);
300                C c = (C) lbc[i];
301                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
302                    a = a.divide(c);
303                    S = S.subtractMultiple(a, e, p[i]);
304                    //System.out.print("|");
305                } else {
306                    //System.out.print("*");
307                    R = R.multiply(c);
308                    //S = S.multiply(c);
309                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
310                }
311                //Q = p[i].multiply(a, e);
312                //S = S.subtract(Q);
313                fac = row.get(i);
314                if (fac == null) {
315                    fac = zero.sum(a, e);
316                } else {
317                    fac = fac.sum(a, e);
318                }
319                row.set(i, fac);
320            }
321        }
322        return R;
323    }
324
325
326    /**
327     * Normalform.
328     * @param Pp polynomial list.
329     * @param Ap polynomial.
330     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
331     *         for Ap.
332     */
333    @SuppressWarnings("unchecked")
334    public PseudoReductionEntry<C> normalformFactor(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
335        if (Ap == null) {
336            return null;
337        }
338        C mfac = Ap.ring.getONECoefficient();
339        PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac);
340        if (Pp == null || Pp.isEmpty()) {
341            return pf;
342        }
343        if (Ap.isZERO()) {
344            return pf;
345        }
346        Map.Entry<ExpVector, C> m;
347        GenPolynomial<C>[] P = new GenPolynomial[0];
348        synchronized (Pp) {
349            P = Pp.toArray(P);
350        }
351        int l = P.length;
352        ExpVector[] htl = new ExpVector[l];
353        C[] lbc = (C[]) new RingElem[l]; // want C[] 
354        GenPolynomial<C>[] p = new GenPolynomial[l];
355        int i;
356        int j = 0;
357        for (i = 0; i < l; i++) {
358            if (P[i] == null) {
359                continue;
360            }
361            p[i] = P[i];
362            m = p[i].leadingMonomial();
363            if (m != null) {
364                p[j] = p[i];
365                htl[j] = m.getKey();
366                lbc[j] = m.getValue();
367                j++;
368            }
369        }
370        l = j;
371        ExpVector e;
372        C a;
373        boolean mt = false;
374        GenPolynomial<C> R = Ap.ring.getZERO().copy();
375
376        GenPolynomial<C> S = Ap.copy();
377        while (S.length() > 0) {
378            m = S.leadingMonomial();
379            e = m.getKey();
380            a = m.getValue();
381            for (i = 0; i < l; i++) {
382                mt = e.multipleOf(htl[i]);
383                if (mt)
384                    break;
385            }
386            if (!mt) {
387                //logger.debug("irred");
388                //R = R.sum(a, e);
389                //S = S.subtract(a, e);
390                R.doPutToMap(e, a);
391                S.doRemoveFromMap(e, a);
392                //System.out.println(" S = " + S);
393            } else {
394                e = e.subtract(htl[i]);
395                //logger.info("red div = {}", e);
396                C c = lbc[i];
397                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
398                    a = a.divide(c);
399                    S = S.subtractMultiple(a, e, p[i]);
400                } else {
401                    mfac = mfac.multiply(c);
402                    R = R.multiply(c);
403                    //S = S.multiply(c);
404                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
405                }
406                //Q = p[i].multiply(a, e);
407                //S = S.subtract(Q);
408            }
409        }
410        logger.info("multiplicative factor = {}", mfac);
411        pf = new PseudoReductionEntry<C>(R, mfac);
412        return pf;
413    }
414
415}