Source code

001/*
002 * $Id: WordResidueRing.java 5303 2015-08-16 17:11:07Z kredel $
003 */
004
005package edu.jas.application;
006
007
008import java.io.Reader;
009import java.util.ArrayList;
010import java.util.List;
011import java.util.Random;
012import java.util.SortedSet;
013import java.util.TreeSet;
014
015import org.apache.log4j.Logger;
016
017import edu.jas.gb.WordGroebnerBaseAbstract;
018import edu.jas.gb.WordGroebnerBaseSeq;
019import edu.jas.poly.GenWordPolynomial;
020import edu.jas.poly.GenWordPolynomialRing;
021import edu.jas.structure.GcdRingElem;
022import edu.jas.structure.QuotPairFactory;
023import edu.jas.structure.RingFactory;
024import edu.jas.structure.ValueFactory;
025
026
027/**
028 * WordResidue ring factory based on GenWordPolynomialRing with GcdRingFactory
029 * interface. Objects of this class are immutable.
030 * @author Heinz Kredel
031 */
032public class WordResidueRing<C extends GcdRingElem<C>> implements RingFactory<WordResidue<C>>,
033                QuotPairFactory<GenWordPolynomial<C>, WordResidue<C>>,
034                ValueFactory<GenWordPolynomial<C>, WordResidue<C>> {
035
036
037    private static final Logger logger = Logger.getLogger(WordResidueRing.class);
038
039
040    //private boolean debug = logger.isDebugEnabled();
041
042
043    /**
044     * Groebner base engine.
045     */
046    protected final WordGroebnerBaseAbstract<C> bb;
047
048
049    /**
050     * Word polynomial ideal for the reduction.
051     */
052    public final WordIdeal<C> ideal;
053
054
055    /**
056     * Polynomial ring of the factory. Shortcut to ideal.list.ring.
057     */
058    public final GenWordPolynomialRing<C> ring;
059
060
061    /**
062     * Indicator if this ring is a field.
063     */
064    protected int isField = -1; // initially unknown
065
066
067    /**
068     * The constructor creates a WordResidueRing object from an Ideal.
069     * @param i polynomial ideal.
070     */
071    public WordResidueRing(WordIdeal<C> i) {
072        this(i, false);
073    }
074
075
076    /**
077     * The constructor creates a WordResidueRing object from an WordIdeal.
078     * @param i solvable polynomial ideal.
079     * @param isMaximal true, if ideal is maxmal.
080     */
081    public WordResidueRing(WordIdeal<C> i, boolean isMaximal) {
082        ideal = i.GB(); // cheap if isGB
083        ring = ideal.getRing();
084        bb = new WordGroebnerBaseSeq<C>();
085        if (isMaximal) {
086            isField = 1;
087            return;
088        }
089        if (ideal.isONE()) {
090            logger.warn("ideal is one, so all residues are 0");
091        }
092        //System.out.println("rr ring   = " + ring.getClass().getName());
093        //System.out.println("rr cofac  = " + ring.coFac.getClass().getName());
094    }
095
096
097    /**
098     * Factory for base elements.
099     */
100    public GenWordPolynomialRing<C> pairFactory() {
101        return ring;
102    }
103
104
105    /**
106     * Factory for base elements.
107     */
108    public GenWordPolynomialRing<C> valueFactory() {
109        return ring;
110    }
111
112
113    /**
114     * Create from numerator.
115     */
116    public WordResidue<C> create(GenWordPolynomial<C> n) {
117        return new WordResidue<C>(this, n);
118    }
119
120
121    /**
122     * Create from numerator, denominator pair.
123     */
124    public WordResidue<C> create(GenWordPolynomial<C> n, GenWordPolynomial<C> d) {
125        if (d != null && !d.isONE()) {
126            throw new UnsupportedOperationException("d must be 1, but d = " + d);
127        }
128        return new WordResidue<C>(this, n);
129    }
130
131
132    /**
133     * Is this structure finite or infinite.
134     * @return true if this structure is finite, else false.
135     * @see edu.jas.structure.ElemFactory#isFinite()
136     */
137    public boolean isFinite() {
138        return ideal.commonZeroTest() <= 0 && ring.coFac.isFinite();
139    }
140
141
142    /**
143     * Copy WordResidue element c.
144     * @param c
145     * @return a copy of c.
146     */
147    public WordResidue<C> copy(WordResidue<C> c) {
148        //System.out.println("rr copy in    = " + c.val);
149        if (c == null) { // where does this happen?
150            return getZERO(); // or null?
151        }
152        WordResidue<C> r = new WordResidue<C>(this, c.val);
153        //System.out.println("rr copy out   = " + r.val);
154        //System.out.println("rr copy ideal = " + ideal.list.list);
155        return r; //new WordResidue<C>( c.ring, c.val );
156    }
157
158
159    /**
160     * Get the zero element.
161     * @return 0 as WordResidue.
162     */
163    public WordResidue<C> getZERO() {
164        return new WordResidue<C>(this, ring.getZERO());
165    }
166
167
168    /**
169     * Get the one element.
170     * @return 1 as WordResidue.
171     */
172    public WordResidue<C> getONE() {
173        WordResidue<C> one = new WordResidue<C>(this, ring.getONE());
174        if (one.isZERO()) {
175            logger.warn("ideal is one, so all residues are 0");
176        }
177        return one;
178    }
179
180
181    /**
182     * Get a list of the generating elements.
183     * @return list of generators for the algebraic structure.
184     * @see edu.jas.structure.ElemFactory#generators()
185     */
186    public List<WordResidue<C>> generators() {
187        List<GenWordPolynomial<C>> pgens = ring.generators();
188        List<WordResidue<C>> gens = new ArrayList<WordResidue<C>>(pgens.size());
189        SortedSet<WordResidue<C>> sgens = new TreeSet<WordResidue<C>>();
190        List<GenWordPolynomial<C>> rgens = new ArrayList<GenWordPolynomial<C>>(pgens.size());
191        WordIdeal<C> gi = new WordIdeal<C>(ring, rgens);
192        WordResidueRing<C> gr = new WordResidueRing<C>(gi);
193        for (GenWordPolynomial<C> s : pgens) {
194            WordResidue<C> r = new WordResidue<C>(this, s);
195            if (r.isZERO()) {
196                continue;
197            }
198            if (!r.isONE() && r.val.isConstant()) {
199                continue;
200            }
201            // avoid duplicate generators
202            WordResidue<C> x = new WordResidue<C>(gr, r.val);
203            if (x.isZERO()) {
204                continue;
205            }
206            if (!x.isONE() && x.val.isConstant()) {
207                continue;
208            }
209            r = new WordResidue<C>(this, x.val);
210            if (r.isZERO()) {
211                continue;
212            }
213            r = r.monic();
214            if (!r.isONE() && !r.val.isConstant()) {
215                rgens.add(r.val);
216                //System.out.println("rgens = " + rgens);
217                gi = new WordIdeal<C>(ring, rgens);
218                gr = new WordResidueRing<C>(gi);
219            }
220            //gens.add(r);
221            sgens.add(r);
222        }
223        gens.addAll(sgens);
224        return gens;
225    }
226
227
228    /**
229     * Query if this ring is commutative.
230     * @return true if this ring is commutative, else false.
231     */
232    public boolean isCommutative() {
233        return ring.isCommutative(); // check also vector space structure
234    }
235
236
237    /**
238     * Query if this ring is associative.
239     * @return true if this ring is associative, else false.
240     */
241    public boolean isAssociative() {
242        return ring.isAssociative(); // sufficient ??
243    }
244
245
246    /**
247     * Query if this ring is a field.
248     * @return false.
249     */
250    public boolean isField() {
251        if (isField > 0) {
252            return true;
253        }
254        if (isField == 0) {
255            return false;
256        }
257        if (ideal.isMaximal()) {
258            isField = 1;
259            return true;
260        }
261        return false;
262    }
263
264
265    /**
266     * Characteristic of this ring.
267     * @return characteristic of this ring.
268     */
269    public java.math.BigInteger characteristic() {
270        return ring.characteristic();
271    }
272
273
274    /**
275     * Get a WordResidue element from a BigInteger value.
276     * @param a BigInteger.
277     * @return a WordResidue.
278     */
279    public WordResidue<C> fromInteger(java.math.BigInteger a) {
280        return new WordResidue<C>(this, ring.fromInteger(a));
281    }
282
283
284    /**
285     * Get a WordResidue element from a long value.
286     * @param a long.
287     * @return a WordResidue.
288     */
289    public WordResidue<C> fromInteger(long a) {
290        return new WordResidue<C>(this, ring.fromInteger(a));
291    }
292
293
294    /**
295     * Get the String representation as RingFactory.
296     * @see java.lang.Object#toString()
297     */
298    @Override
299    public String toString() {
300        return "WordResidueRing[ " + ideal.toString() + " ]";
301    }
302
303
304    /**
305     * Get a scripting compatible string representation.
306     * @return script compatible representation for this ElemFactory.
307     * @see edu.jas.structure.ElemFactory#toScript()
308     */
309    @Override
310    public String toScript() {
311        // Python case
312        return "WRC(" + ideal.toScript() + ")";
313        //return "WRC(" + ideal.toScript() + "," + ring.toScript()  + ")";
314    }
315
316
317    /**
318     * Comparison with any other object.
319     * @see java.lang.Object#equals(java.lang.Object)
320     */
321    @Override
322    @SuppressWarnings("unchecked")
323    public boolean equals(Object b) {
324        if (!(b instanceof WordResidueRing)) {
325            return false;
326        }
327        WordResidueRing<C> a = null;
328        try {
329            a = (WordResidueRing<C>) b;
330        } catch (ClassCastException e) {
331        }
332        if (a == null) {
333            return false;
334        }
335        if (!ring.equals(a.ring)) {
336            return false;
337        }
338        return ideal.equals(a.ideal);
339    }
340
341
342    /**
343     * Hash code for this residue ring.
344     * @see java.lang.Object#hashCode()
345     */
346    @Override
347    public int hashCode() {
348        int h;
349        h = ideal.hashCode();
350        return h;
351    }
352
353
354    /**
355     * WordResidue random.
356     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
357     * @return a random residue element.
358     */
359    public WordResidue<C> random(int n) {
360        GenWordPolynomial<C> x = ring.random(n).monic();
361        return new WordResidue<C>(this, x);
362    }
363
364
365    /**
366     * Generate a random residum polynomial.
367     * @param k bitsize of random coefficients.
368     * @param l number of terms.
369     * @param d maximal degree in each variable.
370     * @return a random residue polynomial.
371     */
372    public WordResidue<C> random(int k, int l, int d) {
373        GenWordPolynomial<C> x = ring.random(k, l, d).monic();
374        return new WordResidue<C>(this, x);
375    }
376
377
378    /**
379     * WordResidue random.
380     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
381     * @param rnd is a source for random bits.
382     * @return a random residue element.
383     */
384    public WordResidue<C> random(int n, Random rnd) {
385        GenWordPolynomial<C> x = ring.random(n, rnd).monic();
386        return new WordResidue<C>(this, x);
387    }
388
389
390    /**
391     * Parse WordResidue from String.
392     * @param s String.
393     * @return WordResidue from s.
394     */
395    public WordResidue<C> parse(String s) {
396        GenWordPolynomial<C> x = ring.parse(s);
397        return new WordResidue<C>(this, x);
398    }
399
400
401    /**
402     * Parse WordResidue from Reader.
403     * @param r Reader.
404     * @return next WordResidue from r.
405     */
406    public WordResidue<C> parse(Reader r) {
407        GenWordPolynomial<C> x = ring.parse(r);
408        return new WordResidue<C>(this, x);
409    }
410
411}