Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.util.List;
009
010import org.apache.logging.log4j.LogManager;
011import org.apache.logging.log4j.Logger;
012
013
014/**
015 * Term order names for ordered polynomials. Defines names for the most used
016 * term orders: graded and lexicographical orders. For the definitions see for
017 * example the articles <a href="http://doi.acm.org/10.1145/43882.43887">Kredel,
018 * Admissible term orderings used in computer algebra systems</a> and
019 *  <a href="http://doi.acm.org/10.1145/70936.70941">Sit, Some comments on
020 * term-ordering in Gr&ouml;bner basis computations</a>. Not all algorithms may
021 * work with all term orders since not all are well-founded, so watch your step.
022 * 
023 * <b>Note:</b> Variables in printed JAS polynomial <b>(low, ..., medium, ...,
024 * high)</b> Variables in other CAS polynomial <b>(high, ..., medium, ...,
025 * low)</b> with <b>low</b> &lt; <b>medium</b> &lt; <b>high</b>. Example: for
026 * variables x<sub>1</sub>, ..., x<sub>r</sub> it is assumed in JAS that
027 * x<sub>1</sub> &lt; ... &lt; x<sub>r</sub> in other CAS it means x<sub>1</sub>
028 * &gt; ... &gt; x<sub>r</sub>.
029 * 
030 * @author Heinz Kredel
031 */
032
033public class TermOrderByName {
034
035
036    private static final Logger logger = LogManager.getLogger(TermOrderByName.class);
037
038
039    /**
040     * TermOrder named LEX.
041     */
042    public static final TermOrder LEX = new TermOrder(TermOrder.LEX);
043
044
045    /**
046     * TermOrder named INVLEX.
047     */
048    public static final TermOrder INVLEX = new TermOrder(TermOrder.INVLEX);
049
050
051    /**
052     * TermOrder named GRLEX.
053     */
054    public static final TermOrder GRLEX = new TermOrder(TermOrder.GRLEX);
055
056
057    /**
058     * TermOrder named IGRLEX.
059     */
060    public static final TermOrder IGRLEX = new TermOrder(TermOrder.IGRLEX);
061
062
063    /**
064     * TermOrder named REVLEX.
065     */
066    public static final TermOrder REVLEX = new TermOrder(TermOrder.REVLEX);
067
068
069    /**
070     * TermOrder named REVILEX.
071     */
072    public static final TermOrder REVILEX = new TermOrder(TermOrder.REVILEX);
073
074
075    /**
076     * TermOrder named REVTDEG.
077     */
078    public static final TermOrder REVTDEG = new TermOrder(TermOrder.REVTDEG);
079
080
081    /**
082     * TermOrder named REVITDG.
083     */
084    public static final TermOrder REVITDG = new TermOrder(TermOrder.REVITDG);
085
086
087    /**
088     * TermOrder named ITDEGLEX.
089     */
090    public static final TermOrder ITDEGLEX = new TermOrder(TermOrder.ITDEGLEX);
091
092
093    /**
094     * TermOrder named REVITDEG.
095     */
096    public static final TermOrder REVITDEG = new TermOrder(TermOrder.REVITDEG);
097
098
099    /**
100     * Default TermOrder.
101     */
102    public final static TermOrder DEFAULT = new TermOrder(TermOrder.DEFAULT_EVORD);
103
104
105    // Math like term orders:
106
107    /**
108     * TermOrder name Lexicographic of Math like CAS.
109     */
110    public final static TermOrder Lexicographic = REVILEX;
111
112
113    /**
114     * TermOrder name NegativeLexicographic of Math like CAS.
115     */
116    public final static TermOrder NegativeLexicographic = REVLEX;
117
118
119    /**
120     * TermOrder name DegreeLexicographic of Math like CAS.
121     */
122    public final static TermOrder DegreeLexicographic = REVITDG;
123
124
125    /**
126     * TermOrder name NegativeDegreeLexicographic of Math like CAS.
127     */
128    public final static TermOrder NegativeDegreeLexicographic = REVITDEG; // was REVTDEG;
129
130
131    /**
132     * TermOrder name ReverseLexicographic of Math like CAS.
133     */
134    public final static TermOrder ReverseLexicographic = INVLEX;
135
136
137    /**
138     * TermOrder name DegreeReverseLexicographic of Math like CAS.
139     */
140    public final static TermOrder DegreeReverseLexicographic = ITDEGLEX; // was IGRLEX;
141
142
143    /**
144     * TermOrder name NegativeReverseLexicographic of Math like CAS.
145     */
146    public final static TermOrder NegativeReverseLexicographic = LEX;
147
148
149    /**
150     * TermOrder name NegativeDegreeReverseLexicographic of Math like CAS.
151     */
152    public final static TermOrder NegativeDegreeReverseLexicographic = GRLEX;
153
154
155    // Sage term orders:
156
157    /**
158     * TermOrder name lex of Sage.
159     */
160    public final static TermOrder lex = Lexicographic; // = REVILEX; 
161
162
163    /**
164     * TermOrder name degrevlex of Sage.
165     */
166    public final static TermOrder degrevlex = DegreeReverseLexicographic; // = IGRLEX; 
167
168
169    /**
170     * TermOrder name deglex of Sage.
171     */
172    public final static TermOrder deglex = DegreeLexicographic; // = REVITDG; 
173
174
175    /**
176     * TermOrder name invlex of Sage.
177     */
178    public final static TermOrder invlex = INVLEX; //ReverseLexicographic  
179
180
181    /**
182     * TermOrder name neglex of Sage.
183     */
184    public final static TermOrder neglex = NegativeLexicographic; // = REVLEX; 
185
186
187    /**
188     * TermOrder name negdegrevlex of Sage.
189     */
190    public final static TermOrder negdegrevlex = NegativeDegreeReverseLexicographic; // = GRLEX;
191
192
193    /**
194     * TermOrder name negdeglex of Sage.
195     */
196    public final static TermOrder negdeglex = NegativeDegreeLexicographic; // = REVTDEG; 
197
198
199    /**
200     * TermOrder name negrevlex of Sage.
201     */
202    public final static TermOrder negrevlex = NegativeReverseLexicographic; // = LEX; 
203
204
205    // Singular term orders:
206
207    /**
208     * TermOrder name lp of Singular.
209     */
210    public final static TermOrder lp = lex; // = REVILEX; 
211
212
213    /**
214     * TermOrder name dp of Singular.
215     */
216    public final static TermOrder dp = degrevlex; // = IGRLEX; 
217
218
219    /**
220     * TermOrder name Dp of Singular.
221     */
222    public final static TermOrder Dp = deglex; // = REVITDG; 
223
224
225    /**
226     * TermOrder name rp of Singular.
227     */
228    public final static TermOrder rp = invlex; // = INVLEX;  
229
230
231    /**
232     * TermOrder name ls of Singular.
233     */
234    public final static TermOrder ls = neglex; // = REVLEX; 
235
236
237    /**
238     * TermOrder name ds of Singular.
239     */
240    public final static TermOrder ds = negdegrevlex; // = GRLEX;
241
242
243    /**
244     * TermOrder name Ds of Singular.
245     */
246    public final static TermOrder Ds = negdeglex; // = REVTDEG; 
247
248
249    // missing: public final static TermOrder negrevlex; // = LEX; 
250
251
252    /**
253     * Construct elimination block TermOrder. Variables {x<sub>1</sub>, ..., x
254     * <sub>s-1</sub>} &lt; {x<sub>s</sub>, ..., x<sub>r</sub>}
255     * 
256     * @param t1 term order for both blocks
257     * @param s split index
258     * @return constructed term order
259     */
260    public final static TermOrder blockOrder(TermOrder t1, int s) {
261        return t1.blockOrder(s);
262    }
263
264
265    /**
266     * Construct elimination block TermOrder. Variables {x<sub>1</sub>, ..., x
267     * <sub>s-1</sub>} &lt; {x<sub>s</sub>, ..., x<sub>r</sub>}
268     * 
269     * @param t1 term order for both blocks
270     * @param e exponent vector of desired length, r = length(e)
271     * @param s split index
272     * @return constructed term order
273     */
274    public final static TermOrder blockOrder(TermOrder t1, ExpVector e, int s) {
275        return t1.blockOrder(s, e.length());
276    }
277
278
279    /**
280     * Construct elimination block TermOrder. Variables {x<sub>1</sub>, ..., x
281     * <sub>s-1</sub>} &lt; {x<sub>s</sub>, ..., x<sub>r</sub>}
282     * 
283     * @param t1 term order for lower valiables
284     * @param t2 term order for higher variables
285     * @param s split index
286     * @return constructed term order
287     */
288    public final static TermOrder blockOrder(TermOrder t1, TermOrder t2, int s) {
289        return new TermOrder(t1.getEvord(), t2.getEvord(), Integer.MAX_VALUE, s);
290    }
291
292
293    /**
294     * Construct elimination block TermOrder. Variables {x<sub>1</sub>, ..., x
295     * <sub>s-1</sub>} &lt; {x<sub>s</sub>, ..., x<sub>r</sub>}
296     * 
297     * @param t1 term order for lower valiables
298     * @param t2 term order for higher variables
299     * @param e exponent vector of desired length, r = length(e)
300     * @param s split index
301     * @return constructed term order
302     */
303    public final static TermOrder blockOrder(TermOrder t1, TermOrder t2, ExpVector e, int s) {
304        return new TermOrder(t1.getEvord(), t2.getEvord(), e.length(), s);
305    }
306
307
308    /**
309     * Construct weight TermOrder.
310     * 
311     * @param v weight vector
312     * @return constructed term order
313     */
314    public final static TermOrder weightOrder(long[] v) {
315        return TermOrder.reverseWeight(new long[][] { v });
316    }
317
318
319    /**
320     * Construct weight TermOrder.
321     * 
322     * @param w weight matrix
323     * @return constructed term order
324     */
325    public final static TermOrder weightOrder(long[][] w) {
326        return TermOrder.reverseWeight(w);
327    }
328
329
330    /**
331     * Construct weight TermOrder.
332     * 
333     * @param wa weight matrix as List
334     * @return constructed term order
335     */
336    public final static TermOrder weightOrder(List<List<Long>> wa) {
337        int n = wa.size();
338        long[][] w = new long[n][];
339        for (int i = 0; i < n; i++) {
340            List<Long> row = wa.get(i);
341            int m = row.size();
342            long[] wi = new long[m];
343            for (int j = 0; j < m; j++) {
344                wi[j] = row.get(j);
345            }
346            w[i] = wi;
347        }
348        //return TermOrder.reverseWeight(w);
349        return weightOrder(w);
350    }
351
352
353    /**
354     * Construct weight for term order.
355     * @param to term order
356     * @param n exponent vector size
357     * @return weight matrix
358     */
359    public final static long[][] weightForOrder(TermOrder to, int n) {
360        if (to.isSplit()) {
361            return weightForSplitOrder(to.getEvord(), to.getEvord2(), n, to.getSplit());
362        }
363        return weightForOrder(to.getEvord(), n);
364    }
365
366
367    /**
368     * Construct weight for term order.
369     * @param to term order indicator
370     * @param n exponent vector size
371     * @return weight matrix
372     */
373    /*public*/ final static long[][] weightForOrder(int to, int n) {
374        int k = 0;
375        switch (to) {
376        case TermOrder.IGRLEX:
377            k = n + 1;
378            break;
379        case TermOrder.REVILEX:
380            // no break
381        case TermOrder.INVLEX:
382            k = n;
383            break;
384        default:
385        }
386        logger.info("to = {}, k = {}", to, k);
387        long[][] w = new long[k][];
388        long[] wi;
389        switch (to) {
390        case TermOrder.INVLEX:
391            for (int i = 0; i < n; i++) {
392                w[i] = new long[n];
393                wi = w[i];
394                for (int j = 0; j < n; j++) {
395                    if (i == j) { //n - 1 -
396                        wi[j] = 1L;
397                    } else {
398                        wi[j] = 0L;
399                    }
400                }
401            }
402            break;
403        case TermOrder.IGRLEX:
404            w[0] = new long[n];
405            wi = w[0];
406            for (int j = 0; j < n; j++) {
407                wi[j] = 1L;
408            }
409            for (int i = 0; i < n; i++) {
410                w[i + 1] = new long[n];
411                wi = w[i + 1];
412                for (int j = 0; j < n; j++) {
413                    if (i == j) { //n - 1 -
414                        wi[j] = 1L;
415                    } else {
416                        wi[j] = 0L;
417                    }
418                }
419            }
420            break;
421        case TermOrder.REVILEX:
422            for (int i = 0; i < n; i++) {
423                w[i] = new long[n];
424                wi = w[i];
425                for (int j = 0; j < n; j++) {
426                    if ((n - 1 - i) == j) {
427                        wi[j] = 1L;
428                    } else {
429                        wi[j] = 0L;
430                    }
431                }
432            }
433            break;
434        default:
435            throw new UnsupportedOperationException("case " + to + " not implemented for weightForOrder");
436        }
437        return w;
438    }
439
440
441    /**
442     * Construct weight for split term order.
443     * @param to first term order indicator
444     * @param to2 second term order indicator
445     * @param n exponent vector size
446     * @param s slpit index
447     * @return weight matrix
448     */
449    /*public*/ final static long[][] weightForSplitOrder(int to, int to2, int n, int s) {
450        int k = 0;
451        switch (to) {
452        case TermOrder.IGRLEX:
453            k += 1;
454            break;
455        case TermOrder.INVLEX:
456            k += s;
457            break;
458        default:
459        }
460        //System.out.println("to = " + to + ", k = " + k);
461        switch (to2) {
462        case TermOrder.IGRLEX:
463            k += 1;
464            break;
465        case TermOrder.INVLEX:
466            k += n - s;
467            break;
468        default:
469        }
470        logger.info("to = {}, k = {}", to, k);
471        long[][] w = new long[k + n][];
472        boolean done = true;
473        switch (to) {
474        case TermOrder.IGRLEX:
475            w[0] = new long[n];
476            long[] wi = w[0];
477            int j;
478            for (j = 0; j < s; j++) {
479                wi[j] = 1L;
480            }
481            for (; j < n; j++) {
482                wi[j] = 0L;
483            }
484            break;
485        case TermOrder.INVLEX:
486            for (int i = 0; i < s; i++) {
487                w[i] = new long[n];
488                wi = w[i]; // long[]
489                for (j = 0; j < n; j++) {
490                    if ((n - 1 - i) == j) {
491                        wi[j] = 1L;
492                    } else {
493                        wi[j] = 0L;
494                    }
495                }
496            }
497            break;
498        default:
499            done = false;
500            // compiler/run time error:
501            //throw new UnsupportedOperationException("case " + to + "/" + to2 + " not implemented for weightForOrder");
502            break;
503        }
504        switch (to2) {
505        case TermOrder.IGRLEX:
506            w[k - 1] = new long[n];
507            long[] wi = w[k - 1];
508            int j;
509            for (j = 0; j < s; j++) {
510                wi[j] = 0L;
511            }
512            for (; j < n; j++) {
513                wi[j] = 1L;
514            }
515            break;
516        case TermOrder.INVLEX:
517            for (int i = 0; i < s; i++) {
518                w[s + i] = new long[n];
519                wi = w[s + i]; // long[]
520                for (j = 0; j < n; j++) {
521                    if ((n - 1 - i) == (s + j)) {
522                        wi[j] = 1L;
523                    } else {
524                        wi[j] = 0L;
525                    }
526                }
527            }
528            break;
529        default:
530            done = false;
531            break;
532        }
533        if (!done) {
534            //System.out.println("weightForSplitOrder case " + to + "/" + to2);
535            throw new UnsupportedOperationException(
536                            "case " + to + "/" + to2 + " not implemented for weightForOrder");
537        }
538        //System.out.println("weight: " + Arrays.toString(w));
539        // break ties by inv lex term order
540        for (int i = 0; i < n; i++) {
541            w[k + i] = new long[n];
542            long[] wi = w[k + i];
543            for (int j = 0; j < n; j++) {
544                if ((i) == j) { //n - 1 - 
545                    wi[j] = 1L;
546                } else {
547                    wi[j] = 0L;
548                }
549            }
550        }
551        return w;
552    }
553
554}