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