Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.fd;
006
007
008import java.io.Reader;
009import java.util.ArrayList;
010import java.util.List;
011import java.util.Random;
012
013import org.apache.logging.log4j.LogManager;
014import org.apache.logging.log4j.Logger;
015
016import edu.jas.gbufd.SolvableSyzygyAbstract;
017import edu.jas.gbufd.SolvableSyzygySeq;
018import edu.jas.kern.StringUtil;
019import edu.jas.poly.GenPolynomial;
020import edu.jas.poly.GenSolvablePolynomial;
021import edu.jas.poly.GenSolvablePolynomialRing;
022import edu.jas.poly.PolynomialList;
023import edu.jas.structure.GcdRingElem;
024import edu.jas.structure.QuotPairFactory;
025import edu.jas.structure.RingFactory;
026
027
028/**
029 * SolvableQuotient ring factory based on GenPolynomial with RingElem interface.
030 * Objects of this class are immutable.
031 * @author Heinz Kredel
032 */
033public class SolvableQuotientRing<C extends GcdRingElem<C>> implements RingFactory<SolvableQuotient<C>>,
034                QuotPairFactory<GenPolynomial<C>, SolvableQuotient<C>> {
035    // should be QuotPairFactory<GenSolvablePolynomial<C>
036
037
038    private static final Logger logger = LogManager.getLogger(SolvableQuotientRing.class);
039
040
041    //private static final boolean debug = logger.isDebugEnabled();
042
043
044    /**
045     * Solvable polynomial ring of the factory.
046     */
047    public final GenSolvablePolynomialRing<C> ring;
048
049
050    /**
051     * Syzygy engine of the factory.
052     */
053    public final SolvableSyzygyAbstract<C> engine;
054
055
056    /**
057     * FD engine of the factory.
058     */
059    public final GreatestCommonDivisorAbstract<C> fdengine;
060
061
062    /**
063     * The constructor creates a SolvableQuotientRing object from a
064     * GenSolvablePolynomialRing.
065     * @param r solvable polynomial ring.
066     */
067    public SolvableQuotientRing(GenSolvablePolynomialRing<C> r) {
068        ring = r;
069        engine = new SolvableSyzygySeq<C>(ring.coFac);
070        //fdengine = SGCDFactory.<C> getImplementation(ring.coFac);
071        fdengine = SGCDFactory.<C> getFakeImplementation(ring.coFac);
072        logger.debug("quotient ring constructed");
073        //System.out.println("  engine = " + engine);
074        //System.out.println("fdengine = " + fdengine);
075    }
076
077
078    /**
079     * Factory for base elements.
080     */
081    public GenSolvablePolynomialRing<C> pairFactory() {
082        return ring;
083    }
084
085
086    /**
087     * Create from numerator.
088     */
089    @SuppressWarnings("unchecked")
090    public SolvableQuotient<C> create(GenPolynomial<C> n) {
091        return new SolvableQuotient<C>(this, (GenSolvablePolynomial<C>) n);
092    }
093
094
095    /**
096     * Create from numerator, denominator pair.
097     */
098    @SuppressWarnings("unchecked")
099    public SolvableQuotient<C> create(GenPolynomial<C> n, GenPolynomial<C> d) {
100        return new SolvableQuotient<C>(this, (GenSolvablePolynomial<C>) n, (GenSolvablePolynomial<C>) d);
101    }
102
103
104    /**
105     * Is this structure finite or infinite.
106     * @return true if this structure is finite, else false.
107     */
108    public boolean isFinite() {
109        return ring.isFinite();
110    }
111
112
113    /**
114     * Copy SolvableQuotient element c.
115     * @param c
116     * @return a copy of c.
117     */
118    public SolvableQuotient<C> copy(SolvableQuotient<C> c) {
119        return new SolvableQuotient<C>(c.ring, c.num, c.den, true);
120    }
121
122
123    /**
124     * Get the zero element.
125     * @return 0 as SolvableQuotient.
126     */
127    public SolvableQuotient<C> getZERO() {
128        return new SolvableQuotient<C>(this, ring.getZERO());
129    }
130
131
132    /**
133     * Get the one element.
134     * @return 1 as SolvableQuotient.
135     */
136    public SolvableQuotient<C> getONE() {
137        return new SolvableQuotient<C>(this, ring.getONE());
138    }
139
140
141    /**
142     * Get a list of the generating elements.
143     * @return list of generators for the algebraic structure.
144     */
145    public List<SolvableQuotient<C>> generators() {
146        List<GenSolvablePolynomial<C>> pgens = PolynomialList.<C> castToSolvableList(ring.generators());
147        List<SolvableQuotient<C>> gens = new ArrayList<SolvableQuotient<C>>(pgens.size() * 2 - 1);
148        GenSolvablePolynomial<C> one = ring.getONE();
149        for (GenSolvablePolynomial<C> p : pgens) {
150            SolvableQuotient<C> q = new SolvableQuotient<C>(this, p);
151            gens.add(q);
152            if (!p.isONE()) {
153                q = new SolvableQuotient<C>(this, one, p);
154                gens.add(q);
155            }
156        }
157        return gens;
158    }
159
160
161    /**
162     * Query if this ring is commutative.
163     * @return true if this ring is commutative, else false.
164     */
165    public boolean isCommutative() {
166        return ring.isCommutative();
167    }
168
169
170    /**
171     * Query if this ring is associative.
172     * @return true if this ring is associative, else false.
173     */
174    public boolean isAssociative() {
175        if (!ring.isAssociative()) {
176            return false;
177        }
178        SolvableQuotient<C> Xi, Xj, Xk, p, q;
179        List<SolvableQuotient<C>> gens = generators();
180        int ngen = gens.size();
181        for (int i = 0; i < ngen; i++) {
182            Xi = gens.get(i);
183            for (int j = i + 1; j < ngen; j++) {
184                Xj = gens.get(j);
185                for (int k = j + 1; k < ngen; k++) {
186                    Xk = gens.get(k);
187                    p = Xk.multiply(Xj).multiply(Xi);
188                    q = Xk.multiply(Xj.multiply(Xi));
189                    if (!p.equals(q)) {
190                        logger.info("Xk = {}, Xj = {}, Xi = {}", Xk, Xj, Xi);
191                        logger.info("p = ( Xk * Xj ) * Xi = {}", p);
192                        logger.info("q = Xk * ( Xj * Xi ) = {}", q);
193                        return false;
194                    }
195                }
196            }
197        }
198        return true;
199    }
200
201
202    /**
203     * Query if this ring is a field.
204     * @return true.
205     */
206    public boolean isField() {
207        return true;
208    }
209
210
211    /**
212     * Characteristic of this ring.
213     * @return characteristic of this ring.
214     */
215    public java.math.BigInteger characteristic() {
216        return ring.characteristic();
217    }
218
219
220    /**
221     * Get a SolvableQuotient element from a BigInteger value.
222     * @param a BigInteger.
223     * @return a SolvableQuotient.
224     */
225    public SolvableQuotient<C> fromInteger(java.math.BigInteger a) {
226        return new SolvableQuotient<C>(this, ring.fromInteger(a));
227    }
228
229
230    /**
231     * Get a SolvableQuotient element from a long value.
232     * @param a long.
233     * @return a SolvableQuotient.
234     */
235    public SolvableQuotient<C> fromInteger(long a) {
236        return new SolvableQuotient<C>(this, ring.fromInteger(a));
237    }
238
239
240    /**
241     * Get the String representation as RingFactory.
242     */
243    @Override
244    public String toString() {
245        String s = null;
246        if (ring.coFac.characteristic().signum() == 0) {
247            s = "RatFunc";
248        } else {
249            s = "ModFunc";
250        }
251        return s + "( " + ring.toString() + " )";
252    }
253
254
255    /**
256     * Get a scripting compatible string representation.
257     * @return script compatible representation for this ElemFactory.
258     */
259    @Override
260    public String toScript() {
261        // Python case
262        return "SRF(" + ring.toScript() + ")";
263    }
264
265
266    /**
267     * Comparison with any other object.
268     */
269    @Override
270    @SuppressWarnings("unchecked")
271    public boolean equals(Object b) {
272        if (b == null) {
273            return false;
274        }
275        if (!(b instanceof SolvableQuotientRing)) {
276            return false;
277        }
278        SolvableQuotientRing<C> a = (SolvableQuotientRing<C>) b;
279        return ring.equals(a.ring);
280    }
281
282
283    /**
284     * Hash code for this quotient ring.
285     */
286    @Override
287    public int hashCode() {
288        int h;
289        h = ring.hashCode();
290        return h;
291    }
292
293
294    /**
295     * SolvableQuotient random.
296     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
297     * @return a random quotient element.
298     */
299    public SolvableQuotient<C> random(int n) {
300        GenSolvablePolynomial<C> r = ring.random(n).monic();
301        GenSolvablePolynomial<C> s;
302        int z = 0;
303        do {
304            s = ring.random(n).monic();
305        } while (s.isZERO() && z++ < 10);
306        if (s.isZERO()) {
307            s = ring.getONE();
308        }
309        return new SolvableQuotient<C>(this, r, s, false);
310    }
311
312
313    /**
314     * Generate a random quotient.
315     * @param k bitsize of random coefficients.
316     * @param l number of terms.
317     * @param d maximal degree in each variable.
318     * @param q density of nozero exponents.
319     * @return a random quotient.
320     */
321    public SolvableQuotient<C> random(int k, int l, int d, float q) {
322        GenSolvablePolynomial<C> r = ring.random(k, l, d, q).monic();
323        GenSolvablePolynomial<C> s;
324        int z = 0;
325        do {
326            s = ring.random(k, l, d, q).monic();
327        } while (s.isZERO() && z++ < 10);
328        if (s.isZERO()) {
329            s = ring.getONE();
330        }
331        return new SolvableQuotient<C>(this, r, s, false);
332    }
333
334
335    /**
336     * SolvableQuotient random.
337     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
338     * @param rnd is a source for random bits.
339     * @return a random quotient element.
340     */
341    public SolvableQuotient<C> random(int n, Random rnd) {
342        GenSolvablePolynomial<C> r = ring.random(n, rnd).monic();
343        GenSolvablePolynomial<C> s;
344        int z = 0;
345        do {
346            s = ring.random(n, rnd).monic();
347        } while (s.isZERO() && z++ < 10);
348        if (s.isZERO()) {
349            s = ring.getONE();
350        }
351        //System.out.println("r = " + r + ", s = " + s + ", z = " + z);
352        return new SolvableQuotient<C>(this, r, s, false);
353    }
354
355
356    /**
357     * Parse SolvableQuotient from String. Syntax: "{ polynomial | polynomial }"
358     * or "{ polynomial }" or " polynomial | polynomial " or " polynomial "
359     * @param s String.
360     * @return SolvableQuotient from s.
361     */
362    public SolvableQuotient<C> parse(String s) {
363        int i = s.indexOf("{");
364        if (i >= 0) {
365            s = s.substring(i + 1);
366        }
367        i = s.lastIndexOf("}");
368        if (i >= 0) {
369            s = s.substring(0, i);
370        }
371        i = s.indexOf("|");
372        if (i < 0) {
373            GenSolvablePolynomial<C> n = ring.parse(s);
374            return new SolvableQuotient<C>(this, n);
375        }
376        String s1 = s.substring(0, i);
377        String s2 = s.substring(i + 1);
378        GenSolvablePolynomial<C> n = ring.parse(s1);
379        GenSolvablePolynomial<C> d = ring.parse(s2);
380        return new SolvableQuotient<C>(this, n, d);
381    }
382
383
384    /**
385     * Parse SolvableQuotient from Reader.
386     * @param r Reader.
387     * @return next SolvableQuotient from r.
388     */
389    public SolvableQuotient<C> parse(Reader r) {
390        String s = StringUtil.nextPairedString(r, '{', '}');
391        return parse(s);
392    }
393
394}