source: git/factory/libfac/charset/reorder.cc @ 16055bd

jengelh-datetimespielwiese
Last change on this file since 16055bd was 16055bd, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: move libfac into factory
  • Property mode set to 100644
File size: 12.5 KB
Line 
1////////////////////////////////////////////////////////////
2// This is really experimental. What is the best order of the variables for
3// an ideal? Clearly, if a variable only occures in one and only one polynomial
4// this variable should be assigned the highest level.
5// But what for the others?
6//
7// The strategy used here is o.k. for *most* of the examples. But there are
8// examples where this strategy doesn't give the best possible answer.
9// So, use this at your own risk! The order given may increase or decrease
10// computing time for your example!
11/////////////////////////////////////////////////////////////
12// emacs edit mode for this file is -*- C++ -*-
13////////////////////////////////////////////////////////////
14// FACTORY - Includes
15#include <factory.h>
16// Factor - Includes
17#include <tmpl_inst.h>
18#include "homogfactor.h"
19// Charset - Includes
20
21// some CC's need this:
22#include "reorder.h"
23
24#ifdef REORDERDEBUG
25#  define DEBUGOUTPUT
26#else
27#  undef DEBUGOUTPUT
28#endif
29
30#include <libfac/factor/debug.h>
31#include "timing.h"
32TIMING_DEFINE_PRINT(neworder_time)
33
34#define __ARRAY_INIT__ -1
35
36// the maximal degree of polys in PS wrt. variable x
37static int
38degpsmax( const CFList & PS, const Variable & x, 
39          Intarray & A, Intarray & C){
40  int varlevel = level(x);
41  if ( A[varlevel] != __ARRAY_INIT__ ) return A[varlevel];
42  int max=0,temp, count=0;
43 
44  for ( CFListIterator i=PS; i.hasItem();i++){
45    temp = degree(i.getItem(),x);
46    if ( temp > max ) {max = temp; count = 0; }
47    if ( temp == max) { count += max; } // we count the number of polys
48  }
49  A[varlevel] = max; C[varlevel] = count;
50  return max;
51}
52
53// the minimal non-zero degree of polys in PS wrt. x
54// returns 0 if variable x doesn't occure in any of the polys
55static int
56degpsmin( const CFList & PS, const Variable & x, Intarray & A, Intarray & B,
57          Intarray & C, Intarray & D){
58  int varlevel = level(x);
59  if ( B[varlevel] != __ARRAY_INIT__ ) return B[varlevel];
60  int min=degpsmax(PS,x,A,C), temp, count=0;
61
62  if (min==0) {
63    B[varlevel] = min; D[varlevel] = min;
64    return min;
65  }
66  else
67    for ( CFListIterator i=PS; i.hasItem();i++){
68      temp = degree(i.getItem(),x);
69      if ( temp < min && temp != 0 ){ min = temp; count = 0; }
70      if ( temp == min) { count += min;} // we count the number of polys
71    }
72  B[varlevel] = min; D[varlevel] = count;
73  return min;
74}
75
76// the minimal total degree of lcoeffs of polys in PS wrt. x
77// for those polys having degree degpsmin in x.
78// F will be assigned the minimal number of terms of those lcoeffs
79static int
80Tdeg( const CFList & PS, const Variable & x, Intarray & A, Intarray & B,
81      Intarray & C, Intarray & D, Intarray & E, Intarray & F){
82  int k= degpsmin(PS,x,A,B,C,D), 
83    varlevel= level(x), min=0;
84
85  if ( E[varlevel] != __ARRAY_INIT__ ) return E[varlevel];
86  if (k == 0){
87    E[varlevel]= 0; F[varlevel]= 0;
88  }
89  else{
90    int nopslc=0;
91    CFList LCdegList;
92    CanonicalForm elem;
93    CFListIterator i;
94
95    for ( i=PS; i.hasItem(); i++ ){
96      elem = i.getItem();
97      if ( degree(elem,x) == k ) LCdegList.append(LC(elem,x));
98    }
99   
100    if ( LCdegList.length() > 0 ){
101      CFList TermList;
102      int newmin, newnopslc;
103
104      min= totaldegree(LCdegList.getFirst());
105      TermList= get_Terms(LCdegList.getFirst()); 
106      nopslc= TermList.length();
107      for ( i=LCdegList; i.hasItem(); i++){
108        elem= i.getItem();
109        newmin= totaldegree(elem);
110        TermList= get_Terms(elem);
111        newnopslc= TermList.length();
112        if ( newmin < min ) min= newmin; 
113        if ( newnopslc < nopslc ) nopslc= newnopslc;
114      }
115     
116    }
117    E[varlevel]= min;
118    F[varlevel]= nopslc;
119  }
120  return min;
121}
122
123// The number of the poly in which Variable x first occures
124static int
125nr_of_poly( const CFList & PS, const Variable & x, Intarray & G){
126  int min=0, varlevel=level(x);
127  if ( G[varlevel] != __ARRAY_INIT__ ) return G[varlevel];
128  for ( CFListIterator i=PS; i.hasItem(); i++ ){
129    min += 1;
130    if ( degree(i.getItem(),x) > 0 ) break;
131  }
132  G[varlevel]= min;
133  return min;
134}
135
136static int
137degord( const Variable & x, const Variable & y, const CFList & PS,
138        Intarray & A, Intarray & B, Intarray & C, Intarray & D,
139        Intarray & E, Intarray & F, Intarray & G){
140  int xlevel= level(x), ylevel= level(y);
141
142  if      (degpsmax(PS,y,A,C) < degpsmax(PS,x,A,C))         return 1;
143  else if (degpsmax(PS,x,A,C) < degpsmax(PS,y,A,C) )        return 0;
144  else if (C[ylevel] < C[xlevel])                           return 1;
145  else if (C[xlevel] < C[ylevel])                           return 0;
146  else if (degpsmin(PS,x,A,B,C,D) < degpsmin(PS,y,A,B,C,D)) return 1;
147  else if (degpsmin(PS,y,A,B,C,D) < degpsmin(PS,x,A,B,C,D)) return 0;
148  else if (D[ylevel] < D[xlevel])                           return 1;
149  else if (D[xlevel] < D[ylevel])                           return 0;
150  else if (Tdeg(PS,y,A,B,C,D,E,F) < Tdeg(PS,x,A,B,C,D,E,F)) return 1;
151  else if (Tdeg(PS,x,A,B,C,D,E,F) < Tdeg(PS,y,A,B,C,D,E,F)) return 0;
152  else if (F[ylevel] < F[xlevel])                           return 1;
153  else if (F[xlevel] < F[ylevel])                           return 0;
154  else if (nr_of_poly(PS,x,G) <= nr_of_poly(PS,y,G))        return 1;
155  else return 0;
156
157}
158
159// determine the highest variable of all involved Variables in PS
160// NOTE:
161//    this doesn't give always the correct answer:
162//    If a variable is assigned the highest level in the definition of the
163//    original ring, but doesn't occure in any of the
164//    polynomials, get_max_var returns the variable with a level lower than
165//    the highest level.
166//    Is there a workaround?
167// But for the redefinition of the ring this doesn't matter due to the
168// implementation of neworder().
169
170static Variable
171get_max_var(const CFList & PS){
172  Variable x=PS.getFirst().mvar(), y;
173  for (CFListIterator i=PS; i.hasItem(); i++){
174    y = i.getItem().mvar();
175    if ( y > x ) x=y;
176  }
177  return x;
178}
179
180
181// determine if variable x is in one and only one of the polynomials in PS
182// first criterion for neworder
183static CFList
184only_in_one( const CFList & PS , const Variable & x){
185  CFList output;
186
187  for ( CFListIterator i=PS; i.hasItem(); i++ ){
188    if ( degree(i.getItem(),x) >= 1 ) output.insert(i.getItem());
189    if ( output.length() >= 2 ) break;
190  }
191  return output;
192}
193
194// initialize all Arrays (of same range) with __ARRAY_INIT__
195static void
196initArray(const int highest_level, Intarray & A, Intarray & B, Intarray & C, 
197          Intarray & D, Intarray & E, Intarray & F, Intarray & G){ 
198
199  for ( int i=1 ; i <= highest_level; i ++){
200    A[i] = __ARRAY_INIT__; B[i] = __ARRAY_INIT__; 
201    C[i] = __ARRAY_INIT__; D[i] = __ARRAY_INIT__;
202    E[i] = __ARRAY_INIT__; F[i] = __ARRAY_INIT__;
203    G[i] = __ARRAY_INIT__;
204  }
205}
206
207// now for the second criterion; a little more complex
208//
209// idea: set up seven arrays of lenth highest_level
210//       (of which some entries may be empty, because of only_in_one!)
211//   A saves maxdegree of Variable x in A(level(x))
212//   B saves mindegree of Variable x in B(level(x))
213//   C saves the number of polys in PS which have degree A(level(x)) in
214//     D(level(x))
215//   D saves the number of polys in PS which have degree B(level(x)) in
216//     D(level(x))
217//   E saves the minimal total degree of lcoeffs of polys wrt x in E(level(x))
218//   F saves the minimal number of terms of lcoeffs of E(level(x)) in F(~)
219//   G saves nr of poly Variable x has first deg <> 0
220
221#define __INIT_GAP__ 3
222static Varlist
223reorderb(const Varlist & difference, const CFList & PS, 
224         const int highest_level){
225  Intarray A(1, highest_level), B(1, highest_level), C(1, highest_level), 
226    D(1, highest_level), E(1, highest_level), F(1, highest_level),
227    G(1, highest_level);
228  initArray(highest_level,A,B,C,D,E,F,G);
229  int i=0, j, n=difference.length(), gap=1+__INIT_GAP__;
230  Variable temp;
231  Array<Variable> v(0,n);
232  VarlistIterator J;
233
234  for (J= difference; J.hasItem(); J++ ){ 
235    v[i]= J.getItem(); 
236    i++ ; 
237  }
238 
239  while ( gap <= n) gap = __INIT_GAP__ * gap+1;
240  gap /= __INIT_GAP__;
241  DEBOUTLN(CERR, "gap is ", gap);
242 
243  while ( gap > 0 ){
244    for ( i=gap; i<= n-1; i++){
245      temp = v[i];
246      for ( j= i-gap; j >=0 ; j-=gap){
247        if (degord(v[j],temp, PS, A,B,C,D,E,F,G))  break;
248        v[j+gap] = v[j];
249        //CERR << "v[" << j+gap << "]= " << v[j+gap] << "\n";
250      }
251      v[j+gap] = temp;
252      //CERR << "v[" << j+gap << "]= " << v[j+gap] << "\n";
253    }
254    gap /= __INIT_GAP__;
255  }
256  Varlist output;
257  for (i=0; i<= n-1; i++)
258    output.append(v[i]);
259  DEBOUTLN(CERR, "A= ", A);  DEBOUTLN(CERR, "B= ", B); 
260  DEBOUTLN(CERR, "C= ", C);  DEBOUTLN(CERR, "D= ", D);
261  DEBOUTLN(CERR, "E= ", E);  DEBOUTLN(CERR, "F= ", F);
262  DEBOUTLN(CERR, "G= ", G);
263  return output;
264}
265
266// set up a new orderd list of Variables.
267// we try to reorder the variables heuristically optimal.
268Varlist
269neworder( const CFList & PolyList ){
270  CFList PS= PolyList, PS1=PolyList;
271  Varlist oldorder, reorder, difference;
272
273  DEBINCLEVEL(CERR, "neworder");
274  TIMING_START(neworder_time);
275
276  int highest_level= level(get_max_var(PS));
277  DEBOUTLN(CERR, "neworder: highest_level=   ", highest_level);
278  DEBOUTLN(CERR, "neworder: that is variable ", Variable(highest_level));
279
280  // set up oldorder and first criterion: only_in_one
281  for (int i=highest_level; i>=1; i--){
282    oldorder.insert(Variable(i));
283    CFList is_one= only_in_one(PS1, Variable(i)); 
284    if ( is_one.length() == 1 ){
285      DEBOUTLN(CERR, "Found a variable which is in only one Polynomial: ", 
286               Variable(i));
287      DEBOUTLN(CERR, ".... in the Polynomial: ", is_one.getFirst());
288      reorder.insert(Variable(i));
289      PS1 = Difference(PS1, is_one);
290      DEBOUTLN(CERR, "New cutted list is: ", PS1);
291    }
292    else if ( is_one.length() == 0 ){
293      DEBOUTLN(CERR, "Found a variable which is in no polynomial: ", 
294               Variable(i));
295      DEBOUTMSG(CERR, "... assigning it the highest level.");
296      reorder.append(Variable(i)); // assigne it the highest level
297      PS1 = Difference(PS1, is_one); 
298    }
299  }
300  difference = Difference(oldorder,reorder);
301  DEBOUTLN(CERR, "Missing variables are: ", difference);
302  // rearrange the ordering of the variables!
303  difference = reorderb(difference, PS, highest_level);
304  DEBOUTLN(CERR, "second criterion gives: ", difference);
305  reorder = Union(reorder, difference);
306  DEBOUTLN(CERR, "old order was:     ", oldorder);
307  DEBOUTLN(CERR, "New order will be: ", Union(reorder, Difference(oldorder,reorder)));
308  DEBDECLEVEL(CERR, "neworder");
309  TIMING_END(neworder_time);
310
311  TIMING_PRINT(neworder_time, "\ntime used for neworder   : ");
312
313
314  return Union(reorder,Difference(oldorder,reorder));
315}
316
317// the same as above, only returning a list of CanonicalForms
318CFList
319newordercf(const CFList & PolyList ){
320  Varlist reorder= neworder(PolyList);
321  CFList output;
322
323  for (VarlistIterator i=reorder; i.hasItem(); i++)
324    output.append(CanonicalForm(i.getItem()));
325
326  return output;
327}
328
329// the same as above, only returning a list of ints
330IntList
331neworderint(const CFList & PolyList ){
332  Varlist reorder= neworder(PolyList);
333  IntList output;
334
335  for (VarlistIterator i=reorder; i.hasItem(); i++)
336    output.append(level(i.getItem()));
337
338  return output;
339}
340
341// swapvar a whole list of CanonicalForms
342static CFList
343swapvar( const CFList & PS, const Variable & x, const Variable & y){
344  CFList ps;
345
346  for (CFListIterator i= PS; i.hasItem(); i++)
347    ps.append(swapvar(i.getItem(),x,y));
348  return ps;
349}
350
351static CFFList
352swapvar( const CFFList & PS, const Variable & x, const Variable & y){
353  CFFList ps;
354
355  for (CFFListIterator i= PS; i.hasItem(); i++)
356    ps.append(CFFactor(swapvar(i.getItem().factor(),x,y),i.getItem().exp()));
357  return ps;
358}
359
360// a library function: we reorganize the global variable ordering
361CFList
362reorder( const Varlist & betterorder, const CFList & PS){
363  int i=1, n = betterorder.length();
364  Intarray v(1,n);
365  CFList ps=PS;
366
367  //initalize:
368  for (VarlistIterator j = betterorder; j.hasItem(); j++){
369    v[i]= level(j.getItem()); i++;
370  }
371  DEBOUTLN(CERR, "reorder: Original ps=  ", ps);
372  // reorder:
373  for (i=1; i <= n; i++)
374    ps=swapvar(ps,Variable(v[i]),Variable(n+i));
375  DEBOUTLN(CERR, "reorder: Reorganized ps= ", ps); 
376  return ps;
377}
378
379CFFList
380reorder( const Varlist & betterorder, const CFFList & PS){
381  int i=1, n = betterorder.length();
382  Intarray v(1,n);
383  CFFList ps=PS;
384
385  //initalize:
386  for (VarlistIterator j = betterorder; j.hasItem(); j++){
387    v[i]= level(j.getItem()); i++;
388  }
389  DEBOUTLN(CERR, "reorder: Original ps=  ", ps);
390  // reorder:
391  for (i=1; i <= n; i++)
392    ps=swapvar(ps,Variable(v[i]),Variable(n+i));
393  DEBOUTLN(CERR, "reorder: Reorganized ps= ", ps); 
394  return ps;
395}
396
397ListCFList
398reorder(const Varlist & betterorder, const ListCFList & Q){
399  ListCFList Q1;
400
401  for ( ListCFListIterator i=Q; i.hasItem(); i++)
402    Q1.append(reorder(betterorder, i.getItem()));
403  return Q1;
404}
405
Note: See TracBrowser for help on using the repository browser.