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