Source code

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