001/*
002 * $Id: PseudoReductionPar.java 4291 2012-11-04 18:16:27Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.List;
009import java.util.ArrayList;
010import java.util.Map;
011
012import org.apache.log4j.Logger;
013
014import edu.jas.gb.ReductionAbstract;
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.structure.RingElem;
018
019
020/**
021 * Polynomial pseudo reduction sequential use algorithm. Coefficients of
022 * polynomials must not be from a field, i.e. the fraction free reduction is
023 * implemented. Implements normalform.
024 * @param <C> coefficient type
025 * @author Heinz Kredel
026 */
027
028public class PseudoReductionPar<C extends RingElem<C>> extends ReductionAbstract<C> implements
029                PseudoReduction<C> {
030
031
032    private static final Logger logger = Logger.getLogger(PseudoReductionPar.class);
033
034
035    /**
036     * Constructor.
037     */
038    public PseudoReductionPar() {
039    }
040
041
042    /**
043     * Normalform.
044     * @param Ap polynomial.
045     * @param Pp polynomial list.
046     * @return nf(Ap) with respect to Pp.
047     */
048    @SuppressWarnings("unchecked")
049    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
050        if (Pp == null || Pp.isEmpty()) {
051            return Ap;
052        }
053        if (Ap == null || Ap.isZERO()) {
054            return Ap;
055        }
056        GenPolynomial<C>[] P = new GenPolynomial[0];
057        List<GenPolynomial<C>> Ppp;
058        synchronized (Pp) { 
059           Ppp = new ArrayList<GenPolynomial<C>>(Pp); // sic
060        }
061        P = Ppp.toArray(P);
062        int ll = Ppp.size(); 
063        GenPolynomial<C> Rz = Ap.ring.getZERO();
064        GenPolynomial<C> R = Rz.copy();
065
066        GenPolynomial<C> S = Ap.copy();
067        while (S.length() > 0) {
068            if (Pp.size() != ll) {
069                //System.out.println("Pp.size() = " + Pp.size() + ", ll = " + ll);
070                //long t = System.currentTimeMillis();
071                synchronized (Pp) { 
072                    Ppp = new ArrayList<GenPolynomial<C>>(Pp); // sic
073                }
074                P = Ppp.toArray(P);
075                ll = Ppp.size(); 
076                //ll = P.length; // wrong
077                //t = System.currentTimeMillis()-t;
078                //logger.info("Pp.toArray(): size() = " + l + ", ll = " + ll);
079                S = Ap.copy(); // S.add(R)? // restart reduction ?
080                R = Rz.copy();
081            }
082            boolean mt = false;
083            Map.Entry<ExpVector, C> m = S.leadingMonomial();
084            ExpVector e = m.getKey();
085            C a = m.getValue();
086            ExpVector f = null;
087            int i;
088            for (i = 0; i < ll; i++) {
089                f = P[i].leadingExpVector();
090                mt = e.multipleOf(f);
091                if (mt)
092                    break;
093            }
094            if (!mt) {
095                //System.out.println("m = " + m);
096                //logger.debug("irred");
097                //R = R.sum(a, e);
098                //S = S.subtract(a, e);
099                R.doPutToMap(e, a);
100                S.doRemoveFromMap(e, a);
101                //System.out.println(" S = " + S);
102            } else {
103                e = e.subtract(f);
104                //logger.info("red div = " + e);
105                C c = P[i].leadingBaseCoefficient();
106                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
107                    a = a.divide(c);
108                    S = S.subtractMultiple(a, e, P[i]);
109                } else {
110                    R = R.multiply(c);
111                    //S = S.multiply(c);
112                    S = S.scaleSubtractMultiple(c, a, e, P[i]);
113                }
114                //Q = p[i].multiply(a, e);
115                //S = S.subtract(Q);
116            }
117        }
118        return R;
119    }
120
121
122    /**
123     * Normalform.
124     * @param Pp polynomial list.
125     * @param Ap polynomial.
126     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
127     *         for Ap.
128     */
129    @SuppressWarnings("unchecked")
130    public PseudoReductionEntry<C> normalformFactor(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
131        if (Ap == null) {
132            return null;
133        }
134        C mfac = Ap.ring.getONECoefficient();
135        PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac);
136        if (Pp == null || Pp.isEmpty()) {
137            return pf;
138        }
139        if (Ap.isZERO()) {
140            return pf;
141        }
142        GenPolynomial<C>[] P = new GenPolynomial[0];
143        List<GenPolynomial<C>> Ppp;
144        synchronized (Pp) { 
145             Ppp = new ArrayList<GenPolynomial<C>>(Pp); // sic
146        }
147        P = Ppp.toArray(P);
148        int l = Ppp.size(); 
149        boolean mt = false;
150        GenPolynomial<C> Rz = Ap.ring.getZERO();
151        GenPolynomial<C> R = Rz.copy();
152        //GenPolynomial<C> T = null;
153        GenPolynomial<C> Q = null;
154        GenPolynomial<C> S = Ap.copy();
155        while (S.length() > 0) {
156            if (Pp.size() != l) {
157                //long t = System.currentTimeMillis();
158                synchronized (Pp) {
159                    Ppp = new ArrayList<GenPolynomial<C>>(Pp);
160                }
161                P = Ppp.toArray(P);
162                l = Ppp.size();
163                //t = System.currentTimeMillis()-t;
164                //logger.info("Pp.toArray() = " + t + " ms, size() = " + l);
165                S = Ap.copy(); // S.add(R)? // restart reduction ?
166                R = Rz.copy();
167            }
168            Map.Entry<ExpVector, C> m = S.leadingMonomial();
169            ExpVector e = m.getKey();
170            C a = m.getValue();
171            ExpVector f = null;
172            int i;
173            for (i = 0; i < l; i++) {
174                f = P[i].leadingExpVector();
175                mt = e.multipleOf(f);
176                if (mt)
177                    break;
178            }
179            if (!mt) {
180                //logger.debug("irred");
181                //R = R.sum(a, e);
182                //S = S.subtract(a, e);
183                R.doPutToMap(e, a);
184                S.doRemoveFromMap(e, a);
185                //System.out.println(" S = " + S);
186            } else {
187                e = e.subtract(f);
188                //logger.info("red div = " + e);
189                C c = P[i].leadingBaseCoefficient();
190                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
191                    a = a.divide(c);
192                    S = S.subtractMultiple(a, e, P[i]);
193                } else {
194                    mfac = mfac.multiply(c);
195                    R = R.multiply(c);
196                    //S = S.multiply(c);
197                    S = S.scaleSubtractMultiple(c, a, e, P[i]);
198                }
199                //Q = p[i].multiply(a, e);
200                //S = S.subtract(Q);
201            }
202        }
203        if (logger.isInfoEnabled()) {
204            logger.info("multiplicative factor = " + mfac);
205        }
206        pf = new PseudoReductionEntry<C>(R, mfac);
207        return pf;
208    }
209
210
211    /**
212     * Normalform with recording. <b>Note:</b> Only meaningful if all divisions
213     * are exact. Compute first the multiplication factor <code>m</code> with
214     * <code>normalform(Pp,Ap,m)</code>, then call this method with
215     * <code>normalform(row,Pp,m*Ap)</code>.
216     * @param row recording matrix, is modified.
217     * @param Pp a polynomial list for reduction.
218     * @param Ap a polynomial.
219     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
220     */
221    @SuppressWarnings("unchecked")
222    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
223                    GenPolynomial<C> Ap) {
224        throw new RuntimeException("normalform with recording not implemented");
225    }
226
227}