001    /*
002     * $Id: GroebnerBasePseudoRecSeq.java 3626 2011-05-08 09:51:57Z kredel $
003     */
004    
005    package edu.jas.gbufd;
006    
007    
008    import java.util.ArrayList;
009    import java.util.List;
010    import java.util.ListIterator;
011    import java.util.Collections;
012    
013    import org.apache.log4j.Logger;
014    
015    import edu.jas.gb.GroebnerBaseAbstract;
016    import edu.jas.gb.OrderedPairlist;
017    import edu.jas.gb.Pair;
018    import edu.jas.poly.GenPolynomial;
019    import edu.jas.poly.GenPolynomialRing;
020    import edu.jas.structure.GcdRingElem;
021    import edu.jas.structure.RingFactory;
022    import edu.jas.ufd.GCDFactory;
023    import edu.jas.ufd.GreatestCommonDivisorAbstract;
024    
025    
026    /**
027     * Groebner Base with pseudo reduction sequential algorithm for integral
028     * function coeffcients. Implements Groebner bases and GB test.
029     * @param <C> base coefficient type
030     * @author Heinz Kredel
031     */
032    
033    public class GroebnerBasePseudoRecSeq<C extends GcdRingElem<C>> extends
034            GroebnerBaseAbstract<GenPolynomial<C>> {
035    
036    
037        private static final Logger logger = Logger.getLogger(GroebnerBasePseudoRecSeq.class);
038    
039    
040        private final boolean debug = logger.isDebugEnabled();
041    
042    
043        /**
044         * Greatest common divisor engine for coefficient content and primitive
045         * parts.
046         */
047        protected final GreatestCommonDivisorAbstract<C> engine;
048    
049    
050        /**
051         * Pseudo reduction engine.
052         */
053        protected final PseudoReduction<GenPolynomial<C>> red;
054    
055    
056        /**
057         * Coefficient ring factory.
058         */
059        protected final RingFactory<GenPolynomial<C>> cofac;
060    
061    
062        /**
063         * Base coefficient ring factory.
064         */
065        protected final RingFactory<C> baseCofac;
066    
067    
068        /**
069         * Constructor.
070         * @param rf coefficient ring factory.
071         */
072        public GroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf) {
073            this(new PseudoReductionSeq<GenPolynomial<C>>(), rf);
074        }
075    
076    
077        /**
078         * Constructor.
079         * @param red pseudo reduction engine.
080         * @param rf coefficient ring factory. <b>Note:</b> red must be an instance
081         *            of PseudoReductionSeq.
082         */
083        public GroebnerBasePseudoRecSeq(PseudoReduction<GenPolynomial<C>> red, RingFactory<GenPolynomial<C>> rf) {
084            super(red);
085            this.red = red;
086            cofac = rf;
087            GenPolynomialRing<C> rp = (GenPolynomialRing<C>) cofac;
088            baseCofac = rp.coFac;
089            //engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getImplementation( baseCofac );
090            //not used: 
091            engine = GCDFactory.<C> getProxy(baseCofac);
092        }
093    
094    
095        /**
096         * Groebner base using pairlist class.
097         * @param modv module variable number.
098         * @param F polynomial list.
099         * @return GB(F) a Groebner base of F.
100         */
101        //@Override
102        public List<GenPolynomial<GenPolynomial<C>>> GB(int modv, List<GenPolynomial<GenPolynomial<C>>> F) {
103            GenPolynomial<GenPolynomial<C>> p;
104            List<GenPolynomial<GenPolynomial<C>>> G = new ArrayList<GenPolynomial<GenPolynomial<C>>>();
105            OrderedPairlist<GenPolynomial<C>> pairlist = null;
106            int l = F.size();
107            ListIterator<GenPolynomial<GenPolynomial<C>>> it = F.listIterator();
108            while (it.hasNext()) {
109                p = it.next();
110                if (p.length() > 0) {
111                    p = engine.recursivePrimitivePart(p); //p.monic();
112                    p = p.abs();
113                    if (p.isConstant()) {
114                        G.clear();
115                        G.add(p);
116                        return G; // since no threads are activated
117                    }
118                    G.add(p);
119                    if (pairlist == null) {
120                        pairlist = new OrderedPairlist<GenPolynomial<C>>(modv, p.ring);
121                    }
122                    // putOne not required
123                    pairlist.put(p);
124                } else {
125                    l--;
126                }
127            }
128            if (l <= 1) {
129                return G; // since no threads are activated
130            }
131    
132            Pair<GenPolynomial<C>> pair;
133            GenPolynomial<GenPolynomial<C>> pi;
134            GenPolynomial<GenPolynomial<C>> pj;
135            GenPolynomial<GenPolynomial<C>> S;
136            GenPolynomial<GenPolynomial<C>> H;
137            while (pairlist.hasNext()) {
138                pair = pairlist.removeNext();
139                if (pair == null)
140                    continue;
141    
142                pi = pair.pi;
143                pj = pair.pj;
144                if (false && logger.isDebugEnabled()) {
145                    logger.debug("pi    = " + pi);
146                    logger.debug("pj    = " + pj);
147                }
148    
149                S = red.SPolynomial(pi, pj);
150                if (S.isZERO()) {
151                    pair.setZero();
152                    continue;
153                }
154                if (logger.isDebugEnabled()) {
155                    logger.debug("ht(S) = " + S.leadingExpVector());
156                }
157    
158                H = red.normalform(G, S);
159                if (H.isZERO()) {
160                    pair.setZero();
161                    continue;
162                }
163                if (logger.isDebugEnabled()) {
164                    logger.debug("ht(H) = " + H.leadingExpVector());
165                }
166                H = engine.recursivePrimitivePart(H); //H.monic();
167                H = H.abs();
168                if (H.isConstant()) {
169                    G.clear();
170                    G.add(H);
171                    return G; // since no threads are activated
172                }
173                if (logger.isDebugEnabled()) {
174                    logger.debug("H = " + H);
175                }
176                if (H.length() > 0) {
177                    l++;
178                    G.add(H);
179                    pairlist.put(H);
180                }
181            }
182            logger.debug("#sequential list = " + G.size());
183            G = minimalGB(G);
184            logger.info("" + pairlist); 
185            return G;
186        }
187    
188    
189        /**
190         * Minimal ordered Groebner basis.
191         * @param Gp a Groebner base.
192         * @return a reduced Groebner base of Gp.
193         */
194        @Override
195        public List<GenPolynomial<GenPolynomial<C>>> minimalGB(List<GenPolynomial<GenPolynomial<C>>> Gp) {
196            if (Gp == null || Gp.size() <= 1) {
197                return Gp;
198            }
199            // remove zero polynomials
200            List<GenPolynomial<GenPolynomial<C>>> G = new ArrayList<GenPolynomial<GenPolynomial<C>>>(Gp.size());
201            for (GenPolynomial<GenPolynomial<C>> a : Gp) {
202                if (a != null && !a.isZERO()) { // always true in GB()
203                    // already positive a = a.abs();
204                    G.add(a);
205                }
206            }
207            if (G.size() <= 1) {
208                return G;
209            }
210            // remove top reducible polynomials
211            GenPolynomial<GenPolynomial<C>> a;
212            List<GenPolynomial<GenPolynomial<C>>> F;
213            F = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G.size());
214            while (G.size() > 0) {
215                a = G.remove(0);
216                if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
217                    // drop polynomial 
218                    if (debug) {
219                        System.out.println("dropped " + a);
220                        List<GenPolynomial<GenPolynomial<C>>> ff;
221                        ff = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G);
222                        ff.addAll(F);
223                        a = red.normalform(ff, a);
224                        if (!a.isZERO()) {
225                            System.out.println("error, nf(a) " + a);
226                        }
227                    }
228                } else {
229                    F.add(a);
230                }
231            }
232            G = F;
233            if (G.size() <= 1) {
234                return G;
235            }
236            Collections.reverse(G); // important for lex GB
237            // reduce remaining polynomials
238            int len = G.size();
239            int i = 0;
240            while (i < len) {
241                a = G.remove(0);
242                //System.out.println("doing " + a.length());
243                a = red.normalform(G, a);
244                a = engine.recursivePrimitivePart(a); //a.monic(); was not required
245                a = a.abs();
246                //a = red.normalform( F, a );
247                G.add(a); // adds as last
248                i++;
249            }
250            return G;
251        }
252    
253    }