001/*
002 * $Id: GroebnerBaseRational.java 4291 2012-11-04 18:16:27Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.log4j.Logger;
012
013import edu.jas.arith.BigInteger;
014import edu.jas.arith.BigRational;
015import edu.jas.gb.GroebnerBaseAbstract;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.PolyUtil;
019
020
021/**
022 * Groebner Base sequential algorithm for rational coefficients, fraction free
023 * computation. Implements Groebner bases.
024 * @param <C> BigRational coefficient type
025 * @author Heinz Kredel
026 */
027
028public class GroebnerBaseRational<C extends BigRational> extends GroebnerBaseAbstract<BigRational> {
029
030
031    private static final Logger logger = Logger.getLogger(GroebnerBaseRational.class);
032
033
034    private final boolean debug = logger.isDebugEnabled();
035
036
037    public final GroebnerBaseAbstract<BigInteger> bba;
038
039
040    /**
041     * Constructor.
042     */
043    public GroebnerBaseRational() {
044        super();
045        bba = new GroebnerBasePseudoSeq<BigInteger>(new BigInteger());
046    }
047
048
049    /**
050     * Constructor.
051     */
052    public GroebnerBaseRational(int threads) {
053        super();
054        bba = new GroebnerBasePseudoParallel<BigInteger>(threads,new BigInteger());
055    }
056
057
058    /**
059     * Get the String representation with GB engines.
060     * @see java.lang.Object#toString()
061     */
062    @Override
063    public String toString() {
064        return this.getClass().getSimpleName() + "(" + bba.toString() + ")";
065    }
066
067
068    /**
069     * Groebner base using fraction free computation.
070     * @param modv module variable number.
071     * @param F polynomial list.
072     * @return GB(F) a Groebner base of F.
073     */
074    @Override
075    public List<GenPolynomial<BigRational>> GB(int modv, List<GenPolynomial<BigRational>> F) {
076        List<GenPolynomial<BigRational>> G = F;
077        if (F == null || F.isEmpty()) {
078            return G;
079        }
080        GenPolynomialRing<BigRational> rring = F.get(0).ring;
081        BigInteger cf = new BigInteger();
082        GenPolynomialRing<BigInteger> iring = new GenPolynomialRing<BigInteger>(cf, rring);
083        List<GenPolynomial<BigInteger>> Fi = PolyUtil.integerFromRationalCoefficients(iring, F);
084        //System.out.println("Fi = " + Fi);
085        logger.info("#Fi = " + Fi.size());
086
087        List<GenPolynomial<BigInteger>> Gi = bba.GB(modv, Fi);
088        //System.out.println("Gi = " + Gi);
089        logger.info("#Gi = " + Gi.size());
090
091        G = PolyUtil.<BigRational> fromIntegerCoefficients(rring, Gi);
092        G = PolyUtil.<BigRational> monic(G);
093        return G;
094    }
095
096
097    /**
098     * Minimal ordered Groebner basis.
099     * @param Gp a Groebner base.
100     * @return a reduced Groebner base of Gp.
101     */
102    @Override
103    public List<GenPolynomial<BigRational>> minimalGB(List<GenPolynomial<BigRational>> Gp) {
104        if (Gp == null || Gp.size() <= 1) {
105            return Gp;
106        }
107        // remove zero polynomials
108        List<GenPolynomial<BigRational>> G = new ArrayList<GenPolynomial<BigRational>>(Gp.size());
109        for (GenPolynomial<BigRational> a : Gp) {
110            if (a != null && !a.isZERO()) { // always true in GB()
111                // already positive a = a.abs();
112                G.add(a);
113            }
114        }
115        if (G.size() <= 1) {
116            return G;
117        }
118        // remove top reducible polynomials
119        GenPolynomial<BigRational> a;
120        List<GenPolynomial<BigRational>> F;
121        F = new ArrayList<GenPolynomial<BigRational>>(G.size());
122        while (G.size() > 0) {
123            a = G.remove(0);
124            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
125                // drop polynomial 
126                if (debug) {
127                    System.out.println("dropped " + a);
128                    List<GenPolynomial<BigRational>> ff;
129                    ff = new ArrayList<GenPolynomial<BigRational>>(G);
130                    ff.addAll(F);
131                    a = red.normalform(ff, a);
132                    if (!a.isZERO()) {
133                        System.out.println("error, nf(a) " + a);
134                    }
135                }
136            } else {
137                F.add(a);
138            }
139        }
140        G = F;
141        if (G.size() <= 1) {
142            return G;
143        }
144
145        // reduce remaining polynomials
146        GenPolynomialRing<BigRational> rring = G.get(0).ring;
147        BigInteger cf = new BigInteger();
148        GenPolynomialRing<BigInteger> iring = new GenPolynomialRing<BigInteger>(cf, rring);
149        List<GenPolynomial<BigInteger>> Fi = PolyUtil.integerFromRationalCoefficients(iring, F);
150        logger.info("#Fi = " + Fi.size());
151
152        List<GenPolynomial<BigInteger>> Gi = bba.minimalGB(Fi);
153        logger.info("#Gi = " + Gi.size());
154
155        G = PolyUtil.<BigRational> fromIntegerCoefficients(rring, Gi);
156        G = PolyUtil.<BigRational> monic(G);
157        return G;
158    }
159
160
161    /**
162     * Cleanup and terminate ThreadPool.
163     */
164    @Override
165    public void terminate() {
166        bba.terminate();
167    }
168
169
170    /**
171     * Cancel ThreadPool.
172     */
173    @Override
174    public int cancel() {
175        return bba.cancel();
176    }
177
178}