Source code

001/*
002 * $Id: SolvableReductionSeq.java 4104 2012-08-18 10:00:59Z 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.GenSolvablePolynomial;
013import edu.jas.structure.RingElem;
014
015
016/**
017 * Solvable polynomial Reduction algorithm. Implements left, right normalform.
018 * @param <C> coefficient type
019 * @author Heinz Kredel
020 */
021
022public class SolvableReductionSeq<C extends RingElem<C>> extends SolvableReductionAbstract<C> {
023
024
025    //private static final Logger logger = Logger.getLogger(SolvableReductionSeq.class);
026
027
028    /**
029     * Constructor.
030     */
031    public SolvableReductionSeq() {
032    }
033
034
035    /**
036     * Left Normalform.
037     * @param Ap solvable polynomial.
038     * @param Pp solvable polynomial list.
039     * @return left-nf(Ap) with respect to Pp.
040     */
041    @SuppressWarnings("unchecked")
042    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> Pp,
043            GenSolvablePolynomial<C> Ap) {
044        if (Pp == null || Pp.isEmpty()) {
045            return Ap;
046        }
047        if (Ap == null || Ap.isZERO()) {
048            return Ap;
049        }
050        int l;
051        Map.Entry<ExpVector, C> m;
052        GenSolvablePolynomial<C>[] P;
053        synchronized (Pp) {
054            l = Pp.size();
055            P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
056            //P = Pp.toArray();
057            for (int j = 0; j < Pp.size(); j++) {
058                P[j] = Pp.get(j);
059            }
060        }
061        int i;
062        ExpVector[] htl = new ExpVector[l];
063        Object[] lbc = new Object[l]; // want <C>
064        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
065        int j = 0;
066        for (i = 0; i < l; i++) {
067            p[i] = P[i];
068            m = p[i].leadingMonomial();
069            if (m != null) {
070                p[j] = p[i];
071                htl[j] = m.getKey();
072                lbc[j] = m.getValue();
073                j++;
074            }
075        }
076        l = j;
077        ExpVector e;
078        C a;
079        boolean mt = false;
080        GenSolvablePolynomial<C> R = Ap.ring.getZERO();
081
082        //GenSolvablePolynomial<C> T = null;
083        GenSolvablePolynomial<C> Q = null;
084        GenSolvablePolynomial<C> S = Ap;
085        while (S.length() > 0) {
086            m = S.leadingMonomial();
087            e = m.getKey();
088            //logger.info("red = " + e);
089            a = m.getValue();
090            for (i = 0; i < l; i++) {
091                mt = e.multipleOf(htl[i]);
092                if (mt)
093                    break;
094            }
095            if (!mt) {
096                //logger.debug("irred");
097                //T = new OrderedMapPolynomial( a, e );
098                R = (GenSolvablePolynomial<C>) R.sum(a, e);
099                S = (GenSolvablePolynomial<C>) S.subtract(a, e);
100                // System.out.println(" S = " + S);
101            } else {
102                //logger.debug("red");
103                e = e.subtract(htl[i]);
104                //a = a.divide( (C)lbc[i] );
105                Q = p[i].multiplyLeft(e);
106                a = a.divide(Q.leadingBaseCoefficient());
107                Q = Q.multiplyLeft(a);
108                S = (GenSolvablePolynomial<C>) S.subtract(Q);
109            }
110        }
111        return R;
112    }
113
114
115    /**
116     * LeftNormalform with recording.
117     * @param row recording matrix, is modified.
118     * @param Pp a polynomial list for reduction.
119     * @param Ap a polynomial.
120     * @return nf(Pp,Ap), the left normal form of Ap wrt. Pp.
121     */
122    @SuppressWarnings("unchecked")
123    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> row,
124            List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
125        if (Pp == null || Pp.isEmpty()) {
126            return Ap;
127        }
128        if (Ap == null || Ap.isZERO()) {
129            return Ap;
130        }
131        int l = Pp.size();
132        GenSolvablePolynomial<C>[] P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
133        synchronized (Pp) {
134            //P = Pp.toArray();
135            for (int i = 0; i < Pp.size(); i++) {
136                P[i] = Pp.get(i);
137            }
138        }
139        ExpVector[] htl = new ExpVector[l];
140        Object[] lbc = new Object[l]; // want <C>
141        GenSolvablePolynomial<C>[] p = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
142        Map.Entry<ExpVector, C> m;
143        int j = 0;
144        int i;
145        for (i = 0; i < l; i++) {
146            p[i] = P[i];
147            m = p[i].leadingMonomial();
148            if (m != null) {
149                p[j] = p[i];
150                htl[j] = m.getKey();
151                lbc[j] = m.getValue();
152                j++;
153            }
154        }
155        l = j;
156        ExpVector e;
157        C a;
158        boolean mt = false;
159        GenSolvablePolynomial<C> zero = Ap.ring.getZERO();
160        GenSolvablePolynomial<C> R = Ap.ring.getZERO();
161
162        GenSolvablePolynomial<C> fac = null;
163        // GenSolvablePolynomial<C> T = null;
164        GenSolvablePolynomial<C> Q = null;
165        GenSolvablePolynomial<C> S = Ap;
166        while (S.length() > 0) {
167            m = S.leadingMonomial();
168            e = m.getKey();
169            a = m.getValue();
170            for (i = 0; i < l; i++) {
171                mt = e.multipleOf(htl[i]);
172                if (mt)
173                    break;
174            }
175            if (!mt) {
176                //logger.debug("irred");
177                R = (GenSolvablePolynomial<C>) R.sum(a, e);
178                S = (GenSolvablePolynomial<C>) S.subtract(a, e);
179                // System.out.println(" S = " + S);
180                // throw new RuntimeException("Syzygy no leftGB");
181            } else {
182                e = e.subtract(htl[i]);
183                //logger.info("red div = " + e);
184                //a = a.divide( (C)lbc[i] );
185                //Q = p[i].multiplyLeft( a, e );
186                Q = p[i].multiplyLeft(e);
187                a = a.divide(Q.leadingBaseCoefficient());
188                Q = Q.multiply(a);
189                S = (GenSolvablePolynomial<C>) S.subtract(Q);
190                fac = row.get(i);
191                if (fac == null) {
192                    fac = (GenSolvablePolynomial<C>) zero.sum(a, e);
193                } else {
194                    fac = (GenSolvablePolynomial<C>) fac.sum(a, e);
195                }
196                row.set(i, fac);
197            }
198        }
199        return R;
200    }
201
202
203    /**
204     * Right Normalform.
205     * @param Ap solvable polynomial.
206     * @param Pp solvable polynomial list.
207     * @return right-nf(Ap) with respect to Pp.
208     */
209    @SuppressWarnings("unchecked")
210    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> Pp,
211            GenSolvablePolynomial<C> Ap) {
212        if (Pp == null || Pp.isEmpty()) {
213            return Ap;
214        }
215        if (Ap == null || Ap.isZERO()) {
216            return Ap;
217        }
218        int l;
219        Map.Entry<ExpVector, C> m;
220        GenSolvablePolynomial<C>[] P;
221        synchronized (Pp) {
222            l = Pp.size();
223            P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
224            //P = Pp.toArray();
225            for (int j = 0; j < Pp.size(); j++) {
226                P[j] = Pp.get(j);
227            }
228        }
229        int i;
230        ExpVector[] htl = new ExpVector[l];
231        Object[] lbc = new Object[l]; // want <C>
232        GenSolvablePolynomial<C>[] p = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
233        int j = 0;
234        for (i = 0; i < l; i++) {
235            p[i] = P[i];
236            m = p[i].leadingMonomial();
237            if (m != null) {
238                p[j] = p[i];
239                htl[j] = m.getKey();
240                lbc[j] = m.getValue();
241                j++;
242            }
243        }
244        l = j;
245        ExpVector e;
246        C a;
247        boolean mt = false;
248        GenSolvablePolynomial<C> R = Ap.ring.getZERO();
249
250        //GenSolvablePolynomial<C> T = null;
251        GenSolvablePolynomial<C> Q = null;
252        GenSolvablePolynomial<C> S = Ap;
253        while (S.length() > 0) {
254            m = S.leadingMonomial();
255            e = m.getKey();
256            //logger.info("red = " + e);
257            a = m.getValue();
258            for (i = 0; i < l; i++) {
259                mt = e.multipleOf(htl[i]);
260                if (mt)
261                    break;
262            }
263            if (!mt) {
264                //logger.debug("irred");
265                //T = new OrderedMapPolynomial( a, e );
266                R = (GenSolvablePolynomial<C>) R.sum(a, e);
267                S = (GenSolvablePolynomial<C>) S.subtract(a, e);
268                // System.out.println(" S = " + S);
269            } else {
270                //logger.debug("red");
271                e = e.subtract(htl[i]);
272                //a = a.divide( (C)lbc[i] );
273                Q = p[i].multiply(e);
274                a = a.divide(Q.leadingBaseCoefficient());
275                Q = Q.multiply(a);
276                S = (GenSolvablePolynomial<C>) S.subtract(Q);
277            }
278        }
279        return R;
280    }
281
282}