Source code

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