Source code

001/*
002 * $Id: SolvableGroebnerBaseAbstract.java 4184 2012-09-10 19:33:52Z kredel $
003 */
004
005package edu.jas.gb;
006
007import java.util.ArrayList;
008import java.util.List;
009import java.util.ListIterator;
010
011import org.apache.log4j.Logger;
012
013import edu.jas.poly.ExpVector;
014import edu.jas.poly.GenPolynomial;
015import edu.jas.poly.GenSolvablePolynomial;
016import edu.jas.poly.GenSolvablePolynomialRing;
017import edu.jas.poly.PolynomialList;
018
019import edu.jas.structure.RingElem;
020
021import edu.jas.vector.BasicLinAlg;
022
023
024/**
025 * Solvable Groebner Bases abstract class.
026 * Implements common left, right and twosided Groebner bases 
027 * and left, right and twosided GB tests.
028 * @param <C> coefficient type
029 * @author Heinz Kredel.
030 */
031
032public abstract class SolvableGroebnerBaseAbstract<C extends RingElem<C>> 
033       implements SolvableGroebnerBase<C> {
034
035    private static final Logger logger = Logger.getLogger(SolvableGroebnerBaseAbstract.class);
036    private final boolean debug = logger.isDebugEnabled();
037
038
039    /**
040     * Solvable reduction engine.
041     */
042    protected SolvableReduction<C> sred;
043
044
045    /**
046     * Reduction engine.
047     */
048    protected final Reduction<C> red;
049
050
051    /**
052     * Strategy for pair selection.
053     */
054    public final PairList<C> strategy;
055
056
057    /**
058     * Linear algebra engine.
059     */
060    protected final BasicLinAlg<GenPolynomial<C>> blas;
061
062
063    /**
064     * Constructor.
065     */
066    public SolvableGroebnerBaseAbstract() {
067        this( new SolvableReductionSeq<C>() );
068    }
069
070
071    /**
072     * Constructor.
073     * @param sred Solvable reduction engine
074     */
075    public SolvableGroebnerBaseAbstract(SolvableReduction<C> sred) {
076        this(sred,new OrderedPairlist<C>());
077    }
078
079
080    /**
081     * Constructor.
082     * @param sred Solvable reduction engine
083     * @param pl pair selection strategy
084     */
085    public SolvableGroebnerBaseAbstract(SolvableReduction<C> sred, PairList<C> pl) {
086        this.red = new ReductionSeq<C>();
087        this.sred = sred;
088        this.strategy = pl;
089        blas = new BasicLinAlg<GenPolynomial<C>>();
090    }
091
092
093    /**
094     * Left Groebner base test.
095     * @param F solvable polynomial list.
096     * @return true, if F is a left Groebner base, else false.
097     */
098    public boolean isLeftGB(List<GenSolvablePolynomial<C>> F) {  
099        return isLeftGB(0,F);
100    }
101
102
103    /**
104     * Left Groebner base test.
105     * @param modv number of module variables.
106     * @param F solvable polynomial list.
107     * @return true, if F is a left Groebner base, else false.
108     */
109    public boolean isLeftGB(int modv, 
110                            List<GenSolvablePolynomial<C>> F) {  
111        GenSolvablePolynomial<C> pi, pj, s, h;
112        for ( int i = 0; i < F.size(); i++ ) {
113            pi = F.get(i);
114            for ( int j = i+1; j < F.size(); j++ ) {
115                pj = F.get(j);
116                if ( ! red.moduleCriterion( modv, pi, pj ) ) {
117                   continue;
118                }
119                // if ( ! red.criterion4( pi, pj ) ) { continue; }
120                s = sred.leftSPolynomial( pi, pj );
121                if ( s.isZERO() ) {
122                   continue;
123                }
124                h = sred.leftNormalform( F, s );
125                if ( ! h.isZERO() ) {
126                   return false;
127                }
128            }
129        }
130        return true;
131    }
132
133
134    /**
135     * Twosided Groebner base test.
136     * @param Fp solvable polynomial list.
137     * @return true, if Fp is a two-sided Groebner base, else false.
138     */
139    public boolean isTwosidedGB(List<GenSolvablePolynomial<C>> Fp) {  
140        return isTwosidedGB(0,Fp);
141    }
142
143
144    /**
145     * Twosided Groebner base test.
146     * @param modv number of module variables.
147     * @param Fp solvable polynomial list.
148     * @return true, if Fp is a two-sided Groebner base, else false.
149     */
150    public boolean isTwosidedGB(int modv, 
151                                List<GenSolvablePolynomial<C>> Fp) {
152        if ( Fp == null || Fp.size() == 0 ) { // 0 not 1
153            return true;
154        }
155        GenSolvablePolynomialRing<C> fac = Fp.get(0).ring; // assert != null
156        //List<GenSolvablePolynomial<C>> X = generateUnivar( modv, Fp );
157        List<GenSolvablePolynomial<C>> X = fac.univariateList( modv );
158        List<GenSolvablePolynomial<C>> F 
159            = new ArrayList<GenSolvablePolynomial<C>>( Fp.size() * (1+X.size()) );
160        F.addAll( Fp );
161        GenSolvablePolynomial<C> p, x, pi, pj, s, h;
162        for ( int i = 0; i < Fp.size(); i++ ) {
163            p = Fp.get(i);
164            for ( int j = 0; j < X.size(); j++ ) {
165                x = X.get(j);
166                p = p.multiply( x );
167                p = sred.leftNormalform(F, p);
168                if (!p.isZERO()) {
169                    F.add(p);
170                }
171            }
172        }
173        //System.out.println("F to check = " + F);
174        for ( int i = 0; i < F.size(); i++ ) {
175            pi = F.get(i);
176            for ( int j = i+1; j < F.size(); j++ ) {
177                pj = F.get(j);
178                if ( ! red.moduleCriterion( modv, pi, pj ) ) {
179                   continue;
180                }
181                // if ( ! red.criterion4( pi, pj ) ) { continue; }
182                s = sred.leftSPolynomial( pi, pj );
183                if ( s.isZERO() ) {
184                   continue;
185                }
186                h = sred.leftNormalform( F, s );
187                if ( ! h.isZERO() ) {
188                   logger.info("is not TwosidedGB: " + h);
189                   return false;
190                }
191            }
192        }
193        return true;
194    }
195
196
197    /**
198     * Right Groebner base test.
199     * @param F solvable polynomial list.
200     * @return true, if F is a right Groebner base, else false.
201     */
202    public boolean isRightGB(List<GenSolvablePolynomial<C>> F) {
203        return isRightGB(0,F);
204    }
205
206
207    /**
208     * Right Groebner base test.
209     * @param modv number of module variables.
210     * @param F solvable polynomial list.
211     * @return true, if F is a right Groebner base, else false.
212     */
213    public boolean isRightGB(int modv, List<GenSolvablePolynomial<C>> F) {
214        GenSolvablePolynomial<C> pi, pj, s, h;
215        for ( int i = 0; i < F.size(); i++ ) {
216            pi = F.get(i);
217            //System.out.println("pi right = " + pi);
218            for ( int j = i+1; j < F.size(); j++ ) {
219                pj = F.get(j);
220                //System.out.println("pj right = " + pj);
221                if ( ! red.moduleCriterion( modv, pi, pj ) ) {
222                   continue;
223                }
224                // if ( ! red.criterion4( pi, pj ) ) { continue; }
225                s = sred.rightSPolynomial( pi, pj );
226                if ( s.isZERO() ) {
227                   continue;
228                }
229                //System.out.println("s right = " + s);
230                h = sred.rightNormalform( F, s );
231                if ( ! h.isZERO() ) {
232                   logger.info("isRightGB non zero h = " + h + " :: " + h.ring);
233                   logger.info("p"+i+" = " + pi + ", p"+j+" = " + pj );
234                   return false;
235                } else {
236                    //logger.info("isRightGB zero h = " + h);
237                }
238            }
239        }
240        return true;
241    }
242
243
244    /**
245     * Left Groebner base using pairlist class.
246     * @param F solvable polynomial list.
247     * @return leftGB(F) a left Groebner base of F.
248     */
249    public List<GenSolvablePolynomial<C>> 
250           leftGB(List<GenSolvablePolynomial<C>> F) {  
251        return leftGB(0,F);
252    }
253
254
255    /** 
256     * Solvable Extended Groebner base using critical pair class.
257     * @param F solvable polynomial list.
258     * @return a container for an extended left Groebner base of F.
259     */
260    public SolvableExtendedGB<C>  
261           extLeftGB( List<GenSolvablePolynomial<C>> F ) {
262        return extLeftGB(0,F); 
263    }
264
265
266    /**
267     * Left minimal ordered groebner basis.
268     * @param Gp a left Groebner base.
269     * @return leftGBmi(F) a minimal left Groebner base of Gp.
270     */
271    public List<GenSolvablePolynomial<C>> 
272               leftMinimalGB(List<GenSolvablePolynomial<C>> Gp) {  
273        ArrayList<GenSolvablePolynomial<C>> G 
274           = new ArrayList<GenSolvablePolynomial<C>>();
275        ListIterator<GenSolvablePolynomial<C>> it = Gp.listIterator();
276        for ( GenSolvablePolynomial<C> a: Gp ) { 
277            // a = (SolvablePolynomial) it.next();
278            if ( a.length() != 0 ) { // always true
279               // already monic a = a.monic();
280               G.add( a );
281            }
282        }
283        if ( G.size() <= 1 ) {
284           return G;
285        }
286
287        ExpVector e;        
288        ExpVector f;        
289        GenSolvablePolynomial<C> a, p;
290        ArrayList<GenSolvablePolynomial<C>> F 
291           = new ArrayList<GenSolvablePolynomial<C>>();
292        boolean mt;
293
294        while ( G.size() > 0 ) {
295            a = G.remove(0);
296            e = a.leadingExpVector();
297
298            it = G.listIterator();
299            mt = false;
300            while ( it.hasNext() && ! mt ) {
301               p = it.next();
302               f = p.leadingExpVector();
303               mt =  e.multipleOf( f );
304            }
305            it = F.listIterator();
306            while ( it.hasNext() && ! mt ) {
307               p = it.next();
308               f = p.leadingExpVector();
309               mt =  e.multipleOf( f );
310            }
311            if ( ! mt ) {
312                F.add( a );
313            } else {
314                // System.out.println("dropped " + a.length());
315            }
316        }
317        G = F;
318        if ( G.size() <= 1 ) {
319           return G;
320        }
321
322        F = new ArrayList<GenSolvablePolynomial<C>>();
323        while ( G.size() > 0 ) {
324            a = G.remove(0);
325            // System.out.println("doing " + a.length());
326            a = sred.leftNormalform( G, a );
327            a = sred.leftNormalform( F, a );
328            F.add( a );
329        }
330        return F;
331    }
332
333
334    /**
335     * Twosided Groebner base using pairlist class.
336     * @param Fp solvable polynomial list.
337     * @return tsGB(Fp) a twosided Groebner base of Fp.
338     */
339    public List<GenSolvablePolynomial<C>> 
340               twosidedGB(List<GenSolvablePolynomial<C>> Fp) {  
341        return twosidedGB(0,Fp);
342    }
343
344
345    /**
346     * Right Groebner base using opposite ring left GB.
347     * @param F solvable polynomial list.
348     * @return rightGB(F) a right Groebner base of F.
349     */
350    public List<GenSolvablePolynomial<C>> 
351           rightGB(List<GenSolvablePolynomial<C>> F) {  
352        return rightGB(0,F);
353    }
354
355
356    /**
357     * Right Groebner base using opposite ring left GB.
358     * @param modv number of module variables.
359     * @param F solvable polynomial list.
360     * @return rightGB(F) a right Groebner base of F.
361     */
362    @SuppressWarnings("unchecked")
363    public List<GenSolvablePolynomial<C>> 
364           rightGB(int modv, 
365                   List<GenSolvablePolynomial<C>> F) {
366        GenSolvablePolynomialRing<C> ring = null;
367        for ( GenSolvablePolynomial<C> p : F ) {
368            if ( p != null ) {
369                ring = p.ring;
370                break;
371            }
372        }
373        if ( ring == null ) {
374            return F;
375        }
376        GenSolvablePolynomialRing<C> rring = ring.reverse(true); //true
377        //System.out.println("reversed ring = " + rring);
378        //ring = rring.reverse(true); // true
379        GenSolvablePolynomial<C> q;
380        List<GenSolvablePolynomial<C>> rF;
381           rF = new ArrayList<GenSolvablePolynomial<C>>( F.size() );
382        for ( GenSolvablePolynomial<C> p : F ) {
383            if ( p != null ) {
384               q = (GenSolvablePolynomial<C>)p.reverse(rring);
385               rF.add( q );
386            }
387        }
388        if ( true || debug ) {
389           PolynomialList<C> pl = new PolynomialList<C>(rring,rF);
390           logger.info("reversed problem = " + pl);
391        }
392        //System.out.println("reversed problem = " + rF);
393        List<GenSolvablePolynomial<C>> rG = leftGB( modv, rF );
394        if ( true || debug ) {
395            //PolynomialList<C> pl = new PolynomialList<C>(rring,rG);
396            //logger.info("reversed GB = " + pl);
397            long t = System.currentTimeMillis();
398            boolean isit = isLeftGB( rG );
399            t = System.currentTimeMillis() - t;
400            logger.info("is left GB = " + isit + ", in " + t + " milliseconds");
401        }
402        //System.out.println("reversed left GB = " + rG);
403        ring = rring.reverse(true); // true
404        List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(rG.size());
405        for ( GenSolvablePolynomial<C> p : rG ) {
406            if ( p != null ) {
407               q = (GenSolvablePolynomial<C>)p.reverse(ring);
408               G.add( q );
409            }
410        }
411        if ( true || debug ) {
412            //PolynomialList<C> pl = new PolynomialList<C>(ring,G);
413            //logger.info("GB = " + pl);
414            long t = System.currentTimeMillis();
415            boolean isit = isRightGB( G );
416            t = System.currentTimeMillis() - t;
417            logger.info("is right GB = " + isit + ", in " + t + " milliseconds");
418        }
419        return G;
420    }
421
422
423    /**
424     * Test if left reduction matrix.
425     * @param exgb an SolvableExtendedGB container.
426     * @return true, if exgb contains a left reduction matrix, else false.
427     */
428    public boolean
429           isLeftReductionMatrix(SolvableExtendedGB<C> exgb) {  
430        if ( exgb == null ) {
431            return true;
432        }
433        return isLeftReductionMatrix(exgb.F,exgb.G,exgb.F2G,exgb.G2F);
434    }
435
436
437    /**
438     * Test if left reduction matrix.
439     * @param F a solvable polynomial list.
440     * @param G a left Groebner base.
441     * @param Mf a possible left reduction matrix.
442     * @param Mg a possible left reduction matrix.
443     * @return true, if Mg and Mf are left reduction matrices, else false.
444     */
445    public boolean
446           isLeftReductionMatrix(List<GenSolvablePolynomial<C>> F, 
447                                 List<GenSolvablePolynomial<C>> G,
448                                 List<List<GenSolvablePolynomial<C>>> Mf,  
449                                 List<List<GenSolvablePolynomial<C>>> Mg) {  
450        // no more check G and Mg: G * Mg[i] == 0
451        // check F and Mg: F * Mg[i] == G[i]
452        int k = 0;
453        for ( List<GenSolvablePolynomial<C>> row : Mg ) {
454            boolean t = sred.isLeftReductionNF( row, F, G.get( k ), null );  
455            if ( ! t ) {
456                System.out.println("row = " + row);
457                System.out.println("F   = " + F);
458                System.out.println("Gk  = " + G.get(k));
459                logger.info("F isLeftReductionMatrix s, k = " + F.size() + ", " + k);
460                return false;
461            }
462            k++;
463        }
464        // check G and Mf: G * Mf[i] == F[i]
465        k = 0;
466        for ( List<GenSolvablePolynomial<C>> row : Mf ) {
467            boolean t = sred.isLeftReductionNF( row, G, F.get( k ), null );  
468            if ( ! t ) {
469               logger.error("G isLeftReductionMatrix s, k = " + G.size() + ", " + k);
470               return false;
471            }
472            k++;
473        }
474        return true;
475    }
476
477}