001/*
002 * $Id: ReductionSeq.java 5243 2015-05-01 12:42:10Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.List;
009import java.util.Map;
010
011import edu.jas.poly.ExpVector;
012import edu.jas.poly.GenPolynomial;
013import edu.jas.structure.RingElem;
014
015
016/**
017 * Polynomial reduction sequential use algorithm. Implements normalform.
018 * @param <C> coefficient type
019 * @author Heinz Kredel
020 */
021
022public class ReductionSeq<C extends RingElem<C>> // should be FieldElem<C>>
023                extends ReductionAbstract<C> {
024
025
026    //private static final Logger logger = Logger.getLogger(ReductionSeq.class);
027
028
029    /**
030     * Constructor.
031     */
032    public ReductionSeq() {
033    }
034
035
036    /**
037     * Normalform.
038     * @param Ap polynomial.
039     * @param Pp polynomial list.
040     * @return nf(Ap) with respect to Pp.
041     */
042    @SuppressWarnings("unchecked")
043    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
044        if (Pp == null || Pp.isEmpty()) {
045            return Ap;
046        }
047        if (Ap == null || Ap.isZERO()) {
048            return Ap;
049        }
050        if (!Ap.ring.coFac.isField()) {
051            throw new IllegalArgumentException("coefficients not from a field");
052        }
053        Map.Entry<ExpVector, C> m;
054        int l;
055        GenPolynomial<C>[] P;
056        synchronized (Pp) {
057            l = Pp.size();
058            P = new GenPolynomial[l];
059            //P = Pp.toArray();
060            for (int i = 0; i < Pp.size(); i++) {
061                P[i] = Pp.get(i);
062            }
063        }
064        ExpVector[] htl = new ExpVector[l];
065        Object[] lbc = new Object[l]; // want C[]
066        GenPolynomial<C>[] p = new GenPolynomial[l];
067        int i;
068        int j = 0;
069        for (i = 0; i < l; i++) {
070            p[i] = P[i];
071            m = p[i].leadingMonomial();
072            if (m != null) {
073                p[j] = p[i];
074                htl[j] = m.getKey();
075                lbc[j] = m.getValue();
076                j++;
077            }
078        }
079        l = j;
080        ExpVector e;
081        C a;
082        boolean mt = false;
083        GenPolynomial<C> R = Ap.ring.getZERO().copy();
084
085        //GenPolynomial<C> T = null;
086        //GenPolynomial<C> Q = null;
087        GenPolynomial<C> S = Ap.copy();
088        while (S.length() > 0) {
089            m = S.leadingMonomial();
090            e = m.getKey();
091            a = m.getValue();
092            for (i = 0; i < l; i++) {
093                mt = e.multipleOf(htl[i]);
094                if (mt)
095                    break;
096            }
097            if (!mt) {
098                //logger.debug("irred");
099                //R = R.sum( a, e );
100                //S = S.subtract( a, e ); 
101                R.doPutToMap(e, a);
102                S.doRemoveFromMap(e, a);
103                // System.out.println(" S = " + S);
104            } else {
105                e = e.subtract(htl[i]);
106                //logger.info("red div = " + e);
107                a = a.divide((C) lbc[i]);
108                //Q = p[i].multiply( a, e );
109                //S = S.subtract( Q );
110                S = S.subtractMultiple(a, e, p[i]);
111            }
112        }
113        return R;
114    }
115
116
117    /**
118     * Normalform with recording.
119     * @param row recording matrix, is modified.
120     * @param Pp a polynomial list for reduction.
121     * @param Ap a polynomial.
122     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
123     */
124    @SuppressWarnings("unchecked")
125    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
126                    GenPolynomial<C> Ap) {
127        if (Pp == null || Pp.isEmpty()) {
128            return Ap;
129        }
130        if (Ap == null || Ap.isZERO()) {
131            return Ap;
132        }
133        if (!Ap.ring.coFac.isField()) {
134            throw new IllegalArgumentException("coefficients not from a field");
135        }
136        int l = Pp.size();
137        GenPolynomial<C>[] P = new GenPolynomial[l];
138        synchronized (Pp) {
139            //P = Pp.toArray();
140            for (int i = 0; i < Pp.size(); i++) {
141                P[i] = Pp.get(i);
142            }
143        }
144        ExpVector[] htl = new ExpVector[l];
145        Object[] lbc = new Object[l]; // want C[]
146        GenPolynomial<C>[] p = new GenPolynomial[l];
147        Map.Entry<ExpVector, C> m;
148        int j = 0;
149        int i;
150        for (i = 0; i < l; i++) {
151            p[i] = P[i];
152            m = p[i].leadingMonomial();
153            if (m != null) {
154                p[j] = p[i];
155                htl[j] = m.getKey();
156                lbc[j] = m.getValue();
157                j++;
158            }
159        }
160        l = j;
161        ExpVector e;
162        C a;
163        boolean mt = false;
164        GenPolynomial<C> zero = Ap.ring.getZERO();
165        GenPolynomial<C> R = Ap.ring.getZERO().copy();
166
167        GenPolynomial<C> fac = null;
168        // GenPolynomial<C> T = null;
169        //GenPolynomial<C> Q = null;
170        GenPolynomial<C> S = Ap.copy();
171        while (S.length() > 0) {
172            m = S.leadingMonomial();
173            e = m.getKey();
174            a = m.getValue();
175            for (i = 0; i < l; i++) {
176                mt = e.multipleOf(htl[i]);
177                if (mt)
178                    break;
179            }
180            if (!mt) {
181                //logger.debug("irred");
182                //R = R.sum( a, e );
183                //S = S.subtract( a, e ); 
184                R.doPutToMap(e, a);
185                S.doRemoveFromMap(e, a);
186                // System.out.println(" S = " + S);
187            } else {
188                e = e.subtract(htl[i]);
189                //logger.info("red div = " + e);
190                C c = (C) lbc[i];
191                a = a.divide(c);
192                //Q = p[i].multiply( a, e );
193                //S = S.subtract( Q );
194                S = S.subtractMultiple(a, e, p[i]);
195                fac = row.get(i);
196                if (fac == null) {
197                    fac = zero.sum(a, e);
198                } else {
199                    fac = fac.sum(a, e);
200                }
201                row.set(i, fac);
202            }
203        }
204        return R;
205    }
206
207}