source: git/IntegerProgramming/ideal.cc @ e8c9869

spielwiese
Last change on this file since e8c9869 was e8c9869, checked in by jgmbenoit <quatermaster@…>, 8 years ago
correct spelling error as detected by Lintian
  • Property mode set to 100644
File size: 29.2 KB
Line 
1// ideal.cc
2
3// implementation of some general ideal functions
4
5#ifndef IDEAL_CC
6#define IDEAL_CC
7
8#include <climits>
9#include "ideal.h"
10
11/////////////////////////////////////////////////////////////////////////////
12////////////////// private member functions /////////////////////////////////
13/////////////////////////////////////////////////////////////////////////////
14
15///////////// subset_tree data structure ////////////////////////////////////
16
17#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
18
19void ideal::create_subset_tree()
20{
21  for(int i=0;i<Number_of_Lists;i++)
22  {
23
24// First determine the number of binary vectors whose support is a subset
25// of the support of i (i read as binary vector).
26// The support of i is a set of cardinality s, where s is the number of
27// bits in i that are 1. Hence the desired number is 2^s.
28
29    int s=0;
30
31    for(int k=0;k<List_Support_Variables;k++)
32      if( (i&(1<<k)) == (1<<k) )
33        // bit k of i is 1
34        s++;
35
36    S.number_of_subsets[i]=(1<<s);
37    // (1<<s) == 2^s
38
39// Now determine the concrete binary vectors whose support is a subset
40// of that of i. This is done in a very simple manner by comparing
41// the support of each number between 0 and i (read as binary vector)
42// with that of i. (Efficiency considerations are absolutely unimportant
43// in this function.)
44
45    S.subsets_of_support[i]=new int[S.number_of_subsets[i]];
46    // memory allocation for subsets_of_support[i]
47
48    int index=0;
49    for(int j=0;j<Number_of_Lists;j++)
50      if((i&j)==j)
51        // If the support of j as a bit vector is contained in the support of
52        // i as a bit vector, j is saved in the list subsets_of_support[i].
53          {
54            S.subsets_of_support[i][index]=j;
55            index++;
56          }
57  }
58}
59
60void ideal::destroy_subset_tree()
61{
62  for(int i=0;i<Number_of_Lists;i++)
63    delete[] S.subsets_of_support[i];
64  // The arrays number_of_subsets and subsets_of_support (the (int*)-array)
65  // are not dynamically allocated and do not have to be deleted.
66}
67#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
68
69/////////// subroutines for BuchbergerŽs algorithm //////////////////////////
70
71ideal& ideal::add_new_generator(binomial& bin)
72{
73#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
74
75  new_generators[(bin.head_support)%Number_of_Lists].insert(bin);
76  // insert the bin according to its support,
77  // considering only the first List_Support_Variables variables.
78
79#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
80
81#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
82
83  new_generators.insert(bin);
84
85#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
86
87  return(*this);
88}
89
90ideal& ideal::add_generator(binomial& bin)
91{
92// Beside its function as a auxiliary routine for a shorter code, this routine
93// offers a good way to hide if SUPPORT_DRIVEN_METHODS_EXTENDED are used or
94// not. So the constructors do not have to care about this.
95
96#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
97
98  generators[(bin.head_support)%Number_of_Lists].insert(bin);
99  // insert the bin according to its support,
100  // considering only the first List_Support_Variables variables.
101
102#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
103
104#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
105
106  generators.insert(bin);
107
108#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
109
110  size++;
111  number_of_new_binomials++;
112
113  return(*this);
114}
115
116//////////////////// constructor subroutines ////////////////////////////////
117
118ideal& ideal::Conti_Traverso_ideal(matrix& A,const term_ordering& _w)
119{
120
121  // A may have negative entries; to model this with binomials, we need an
122  // inversion variable.
123
124  w=_w;
125  // The argument term ordering should be given by the objective function.
126
127  w.convert_to_elimination_ordering(A.rows+1,LEX);
128  // extend term ordering into an elimination ordering of the appropriate
129  // size
130
131  Integer *generator=new Integer[A.columns+A.rows+1];
132  // A.columns + A.rows +1 is the number of variables for the Conti-Traverso
133  // algorithm with "inversion variable".
134
135  // build initial ideal generators
136  for(int j=0;j<A.columns;j++)
137  {
138    for(int k=0;k<A.columns;k++)
139      // original variables
140      if(j==k)
141        generator[k]=-1;
142      else
143        generator[k]=0;
144
145    for(int i=0;i<A.rows;i++)
146      // elimination variables
147      generator[A.columns+i]=A.coefficients[i][j];
148
149    generator[A.columns+A.rows]=0;
150    // inversion variable
151
152    // Note that the relative order of the variables is important:
153    // If the elimination variables do not follow the other variables,
154    // the conversion of the term ordering has not the desired effect.
155
156    binomial* bin=new binomial(A.rows+1+A.columns,generator,w);
157    add_generator(*bin);
158  }
159
160  // now add the "inversion generator"
161  for(int j=0;j<A.columns;j++)
162    generator[j]=0;
163  for(int i=0;i<A.rows+1;i++)
164    generator[A.columns+i]=1;
165  binomial* bin=new binomial(A.rows+1+A.columns,generator,w);
166  add_generator(*bin);
167
168  delete[] generator;
169  return *this;
170}
171
172ideal& ideal::Positive_Conti_Traverso_ideal(matrix& A,const term_ordering& _w)
173{
174
175  // A is assumed to have only nonnegative entries;then we need no
176  // "inversion variable".
177
178  w=_w;
179  // The argument term ordering should be given by the objective function.
180
181  w.convert_to_elimination_ordering(A.rows, LEX);
182  // extend term ordering into an elimination ordering of the appropriate
183  // size
184
185  Integer *generator=new Integer[A.columns+A.rows];
186  // A.columns + A.rows is the number of variables for the Conti-Traverso
187  // algorithm without "inversion variable".
188
189  // build the initial ideal generators
190  for(int j=0;j<A.columns;j++)
191  {
192    for(int k=0;k<A.columns;k++)
193      // original variables
194      if(j==k)
195        generator[k]=-1;
196      else
197        generator[k]=0;
198
199    for(int i=0;i<A.rows;i++)
200      // elimination variables
201      generator[A.columns+i]=A.coefficients[i][j];
202
203    // Note that the relative order of the variables is important:
204    // If the elimination variables do not follow the other variables,
205    // the conversion of the term ordering has not the desired effect.
206
207    binomial* bin=new binomial(A.rows+A.columns,generator,w);
208    add_generator(*bin);
209  }
210  delete[] generator;
211  return *this;
212}
213
214ideal& ideal::Pottier_ideal(matrix& A, const term_ordering& _w)
215{
216
217  w=_w;
218  // The argument term_ordering should be given by the objective function.
219
220  w.convert_to_elimination_ordering(1,LEX);
221  // add one elimination variable used to saturate the ideal
222
223  if(A._kernel_dimension==-2)
224    // kernel of A not yet computed, do this now
225    A.LLL_kernel_basis();
226
227  if((A._kernel_dimension==-1) &&  (A.columns<0))
228    // error occurred in kernel computation or matrix corrupt
229  {
230    cout<<"\nWARNING: ideal& ideal::Pottier_ideal(matrix&, const "
231      "term_ordering&):\ncannot build ideal from a corrupt input matrix"<<endl;
232    size=-1;
233    return *this;
234  }
235
236  Integer *generator=new Integer[A.columns+1];
237  // This is the number of variables needed for Pottier's algorithm.
238
239
240  // compute initial generating system from the kernel of A
241  for(int j=0;j<A._kernel_dimension;j++)
242  {
243
244    for(int k=0;k<A.columns;k++)
245    {
246
247      // We should first verifie if the components of the LLL-reduced lattice
248      // basis fit into the basic data type (Integer as defined in globals.h).
249      // This overflow control does of course not detect overflows in the
250      // course of the LLL-algorithm!
251
252#ifdef _SHORT_
253
254      if(((A.H)[j][k]>(const BigInt &)SHRT_MAX) || ((A.H)[j][k]<(const BigInt &)SHRT_MIN))
255      {
256        cerr<<"\nWARNING: ideal& ideal::Pottier_ideal(matrix&, const "
257          "term_ordering&):\n"
258          "LLL-reduced kernel basis does not fit into the used "
259          "basic data type int."<<endl;
260        size=-3;
261        delete[] generator;
262        return *this;
263      }
264
265#endif // _SHORT_
266
267#ifdef _INT_
268
269      if(((A.H)[j][k]>(const BigInt&)INT_MAX) || ((A.H)[j][k]<(const BigInt&)INT_MIN))
270      {
271        cerr<<"\nWARNING: ideal& ideal::Pottier_ideal(matrix&, const "
272          "term_ordering&):\n"
273          "LLL-reduced kernel basis does not fit into the used "
274          "basic data type int."<<endl;
275        size=-3;
276        delete[] generator;
277        return *this;
278      }
279
280#endif  // _INT_
281
282#ifdef _LONG_
283
284      if(((A.H)[j][k]>(const BigInt&)LONG_MAX) || ((A.H)[j][k]<(const BigInt&)LONG_MIN))
285      {
286        cerr<<"\nWARNING: ideal& ideal::Pottier_ideal(matrix&, const "
287          "term_ordering&):\n"
288          "LLL-reduced kernel basis does not fit into the used "
289          "basic data type long."<<endl;
290        size=-3;
291        delete[] generator;
292        return *this;
293      }
294
295#endif  // _LONG_
296
297      generator[k]=(A.H)[j][k];
298    }
299
300    generator[A.columns]=0;
301    // elimination variable
302
303    // Note that the relative order of the variables is important:
304    // If the elimination variable does not follow the other variables,
305    // the conversion of the term ordering has not the desired effect.
306
307    binomial* bin=new binomial(A.columns+1,generator,w);
308    add_generator(*bin);
309  }
310
311  // build "saturation generator"
312
313
314  // The use of the hosten_shapiro procedure is useful here because the head
315  // of the computed saturation generator is smaller if less variables are
316  // involved.
317  int* sat_var = NULL;
318  int number_of_sat_var = A.hosten_shapiro(sat_var);
319  if( (number_of_sat_var == 0) || (sat_var == NULL) )
320  {
321    delete[] generator;
322    return *this;
323  }
324
325  for(int j=0;j<A.columns;j++)
326    generator[j]=0;
327
328  for(int k=0;k<number_of_sat_var;k++)
329    generator[sat_var[k]]=1;
330
331  generator[A.columns]=1;
332
333  binomial* bin=new binomial(A.columns+1,generator,w);
334  add_generator(*bin);
335  // The "saturation generator" seems to be a monomial, but is interpreted
336  // as a binomial with tail 1 by the designed data structures.
337
338  delete[] sat_var;
339  delete[] generator;
340
341  return *this;
342}
343
344ideal& ideal::Hosten_Sturmfels_ideal(matrix& A, const term_ordering& _w)
345{
346
347  // check term ordering
348  if((_w.weight_refinement()!=W_REV_LEX) && (_w.is_positive()==FALSE))
349    cerr<<"\nWARNING: ideal& ideal::Hosten_Sturmfels_ideal(matrix&, const "
350      "term_ordering&):\nargument term ordering should be a weighted reverse"
351      "lexicographical \nwith positive weights"<<endl;
352
353  w=_w;
354  // The argument term_ordering should be given by a homogeneous grading.
355
356  if(A._kernel_dimension==-2)
357    // kernel of A not yet computed, do this now
358    A.LLL_kernel_basis();
359
360  if((A._kernel_dimension==-1) &&  (A.columns<0))
361    // error occurred in kernel computation or matrix corrupt
362  {
363    cout<<"\nWARNING: ideal& ideal::Hosten_Sturmfels_ideal(matrix&, const "
364      "term_ordering&):\ncannot build ideal from a corrupt input matrix"<<endl;
365    size=-1;
366    return *this;
367  }
368
369  Integer * generator=new Integer[A.columns];
370  // The algorithm of Hosten and Sturmfels does not need supplementary
371  // variables.
372
373
374  // compute initial generating system from the kernel of A
375  for(int j=0;j<A._kernel_dimension;j++)
376  {
377
378    for(int k=0;k<A.columns;k++)
379    {
380
381      // We should first verifie if the components of the LLL-reduced lattice
382      // basis fit into the basic data type (Integer as defined in globals.h).
383      // This overflow control does of course not detect overflows in the
384      // course of the LLL-algorithm!
385
386#ifdef _SHORT_
387
388      if(((A.H)[j][k]>(const BigInt &)SHRT_MAX) || ((A.H)[j][k]<(const BigInt &)SHRT_MIN))
389      {
390        cerr<<"\nWARNING: ideal& ideal::Hosten_Sturmfels_ideal(matrix&, const "
391          "term_ordering&):\nLLL-reduced kernel basis does not fit "
392          "into the used basic data type int."<<endl;
393        size=-3;
394        delete[] generator;
395        return *this;
396      }
397
398#endif // _SHORT_
399
400#ifdef _INT_
401
402      if(((A.H)[j][k]>(const BigInt&)INT_MAX) || ((A.H)[j][k]<(const BigInt&)INT_MIN))
403      {
404        cerr<<"\nWARNING: ideal& ideal::Hosten_Sturmfels_ideal(matrix&, const "
405          "term_ordering&):\nLLL-reduced kernel basis does not fit "
406          "into the used basic data type int."<<endl;
407        size=-3;
408        delete[] generator;
409        return *this;
410      }
411
412#endif  // _INT_
413
414#ifdef _LONG_
415
416      if(((A.H)[j][k]>(const BigInt&)LONG_MAX) || ((A.H)[j][k]<(const BigInt&)LONG_MIN))
417      {
418        cerr<<"\nWARNING: ideal& ideal::Hosten_Sturmfels_ideal(matrix&, const "
419          "term_ordering&):\nLLL-reduced kernel basis does not fit "
420          "into the used basic data type long."<<endl;
421        size=-3;
422        delete[] generator;
423        return *this;
424      }
425
426#endif  // _LONG_
427
428      generator[k]=(A.H)[j][k];
429    }
430
431    // verifie term ordering
432    if(w.weight(generator)!=0)
433      cerr<<"\nWARNING: ideal& ideal::Hosten_Sturmfels_ideal(matrix&, "
434        "const term_ordering&):\nInvalid row space vector does not induce "
435        "homogeneous grading."<<endl;
436
437    binomial* bin=new binomial(A.columns,generator,w);
438    add_generator(*bin);
439  }
440
441  delete[] generator;
442  return *this;
443}
444
445ideal& ideal::DiBiase_Urbanke_ideal(matrix& A, const term_ordering& _w)
446{
447  w=_w;
448
449  if(A._kernel_dimension==-2)
450    // kernel of A not yet computed, do this now
451    A.LLL_kernel_basis();
452
453  if((A._kernel_dimension==-1) &&  (A.columns<0))
454    // error occurred in kernel computation or matrix corrupt
455  {
456    cout<<"\nWARNING: ideal& ideal::DiBiase_Urbanke_ideal(matrix&, const "
457      "term_ordering&):\ncannot build ideal from a corrupt input matrix"<<endl;
458    size=-1;
459    return *this;
460  }
461
462  // now compute flip variables
463
464  int* F;
465  // set of flip variables
466  // If F[i]==j, x_j will be flipped.
467
468  int r=A.compute_flip_variables(F);
469  // number of flip variables
470
471  if(r<0)
472  {
473    cout<<"Kernel of the input matrix contains no vector with nonzero "
474      "components.\nPlease use another algorithm."<<endl;
475    size=-1;
476    return *this;
477  }
478
479  // check term ordering (as far as possible)
480  BOOLEAN ordering_okay=TRUE;
481
482  if(_w.weight_refinement()!=W_LEX)
483    ordering_okay=FALSE;
484
485  if(r>0)
486  {
487    for(int i=0;i<_w.number_of_weighted_variables();i++)
488      if((_w[i]!=0) && (i!=F[0]))
489        ordering_okay=FALSE;
490  }
491
492  if(ordering_okay==FALSE)
493    cerr<<"\nWARNING: ideal& ideal::DiBiase_Urbanke_ideal(matrix&, const "
494      "term_ordering&):\nargument term ordering might be inappropriate"<<endl;
495
496  Integer *generator=new Integer[A.columns];
497  // The algorithm of DiBiase and Urbanke does not need supplementary
498  // variables.
499
500  // compute initial generating system from the kernel of A
501  for(int j=0;j<A._kernel_dimension;j++)
502  {
503
504    for(int k=0;k<A.columns;k++)
505    {
506
507      // We should first verifie if the components of the LLL-reduced lattice
508      // basis fit into the basic data type (Integer as defined in globals.h).
509      // This overflow control does of course not detect overflows in the
510      // course of the LLL-algorithm!
511
512#ifdef _SHORT_
513
514      if(((A.H)[j][k]>(const BigInt &)SHRT_MAX) || ((A.H)[j][k]<(const BigInt &)SHRT_MIN))
515      {
516        cerr<<"\nWARNING: ideal& ideal::DiBiase_Urbanke_ideal(matrix&, const "
517          "term_ordering&):\nLLL-reduced kernel basis does not fit "
518          "into the used basic data type int."<<endl;
519        size=-3;
520        delete[] generator;
521        return *this;
522      }
523
524#endif // _SHORT_
525
526#ifdef _INT_
527
528      if(((A.H)[j][k]>(const BigInt&)INT_MAX) || ((A.H)[j][k]<(const BigInt&)INT_MIN))
529      {
530        cerr<<"\nWARNING: ideal& ideal::DiBiase_Urbanke_ideal(matrix&, const "
531          "term_ordering&):\nLLL-reduced kernel basis does not fit "
532          "into the used basic data type int."<<endl;
533        size=-3;
534        delete[] generator;
535        return *this;
536      }
537
538#endif  // _INT_
539
540#ifdef _LONG_
541
542      if(((A.H)[j][k]>(const BigInt&)LONG_MAX) || ((A.H)[j][k]<(const BigInt&)LONG_MIN))
543      {
544        cerr<<"\nWARNING: ideal& ideal::DiBiase_Urbanke_ideal(matrix&, const "
545          "term_ordering&):\nLLL-reduced kernel basis does not fit "
546          "into the used basic data type long."<<endl;
547        size=-3;
548        delete[] generator;
549        return *this;
550      }
551
552#endif  // _LONG_
553      generator[k]=(A.H)[j][k];
554    }
555
556    // flip variables
557    for(int l=0;l<r;l++)
558      generator[F[l]]*=-1;
559
560    binomial* bin=new binomial(A.columns,generator,w);
561    add_generator(*bin);
562  }
563  delete[] F;
564  delete[] generator;
565  return *this;
566}
567
568ideal& ideal::Bigatti_LaScala_Robbiano_ideal(matrix& A,const term_ordering& _w)
569{
570
571  // check term ordering
572  if((_w.weight_refinement()!=W_REV_LEX) && (_w.is_positive()==FALSE))
573    cerr<<"\nWARNING: ideal& ideal::Bigatti_LaScala_Robbiano_ideal(matrix&, "
574      "const term_ordering&):\nargument term ordering should be a weighted  "
575      "reverse lexicographical \nwith positive weights"<<endl;
576
577  w=_w;
578  // The argument term_ordering should be given by a homogeneous grading.
579
580  if(A._kernel_dimension==-2)
581    // kernel of A not yet computed, do this now
582    A.LLL_kernel_basis();
583
584  if((A._kernel_dimension==-1) &&  (A.columns<0))
585    // error occurred in kernel computation or matrix corrupt
586  {
587    cout<<"\nWARNING: ideal& ideal::Bigatti_LaScala_Robbiano_ideal(matrix&, "
588      "const term_ordering&):\n"
589      "cannot build ideal from a corrupt input matrix"<<endl;
590    size=-1;
591    return *this;
592  }
593
594  // now compute saturation variables
595
596  // The techniques for computing a small set of saturation variables are
597  // useful here for the following two reasons:
598  // - The head of the saturation generator involves less variables, is
599  //   smaller in term ordering.
600  // - The weight of the pseudo-elimination variable is smaller.
601  int* sat_var;
602  int number_of_sat_var=A.hosten_shapiro(sat_var);
603
604  float weight=0;
605  for(int i=0;i<number_of_sat_var;i++)
606    weight+=w[sat_var[i]];
607
608  w.append_weighted_variable(weight);
609  // one supplementary variable used to saturate the ideal
610
611  Integer *generator=new Integer[A.columns+1];
612  // The algorithm of Bigatti, LaScala and Robbiano needs one supplementary
613  // weighted variable.
614
615  // first build "saturation generator"
616  for(int k=0;k<A.columns;k++)
617    generator[k]=0;
618  for(int i=0;i<number_of_sat_var;i++)
619    generator[sat_var[i]]=1;
620  generator[A.columns]=-1;
621
622  delete[] sat_var;
623
624  binomial* bin=new binomial(A.columns+1,generator,w);
625  add_generator(*bin);
626
627  // compute initial generating system from the kernel of A
628  for(int j=0;j<A._kernel_dimension;j++)
629  {
630    for(int k=0;k<A.columns;k++)
631    {
632      // We should first verifie if the components of the LLL-reduced lattice
633      // basis fit into the basic data type (Integer as defined in globals.h).
634      // This overflow control does of course not detect overflows in the
635      // course of the LLL-algorithm!
636
637#ifdef _SHORT_
638
639      if(((A.H)[j][k]>(const BigInt &)SHRT_MAX) || ((A.H)[j][k]<(const BigInt &)SHRT_MIN))
640      {
641        cerr<<"\nWARNING: ideal& ideal::Bigatti_LaScala_Robbiano_ideal"
642          "(matrix&, const term_ordering&):\nLLL-reduced kernel basis does "
643          "not fit into the used basic data type int."<<endl;
644        size=-3;
645        delete[] generator;
646        return *this;
647      }
648
649#endif // _SHORT_
650
651#ifdef _INT_
652
653      if(((A.H)[j][k]>(const BigInt&)INT_MAX) || ((A.H)[j][k]<(const BigInt&)INT_MIN))
654      {
655        cerr<<"\nWARNING: ideal& ideal::Bigatti_LaScala_Robbiano_ideal"
656          "(matrix&, const term_ordering&):\nLLL-reduced kernel basis does "
657          "not fit into the used basic data type int."<<endl;
658        size=-3;
659        delete[] generator;
660        return *this;
661      }
662
663#endif  // _INT_
664
665#ifdef _LONG_
666
667      if(((A.H)[j][k]>(const BigInt&)LONG_MAX) || ((A.H)[j][k]<(const BigInt&)LONG_MIN))
668      {
669        cerr<<"\nWARNING: ideal& ideal::Bigatti_LaScala_Robbiano_ideal"
670          "(matrix&, const term_ordering&):\nLLL-reduced kernel basis does "
671          "not fit into the used basic data type long."<<endl;
672        size=-3;
673        return *this;
674      }
675
676#endif  // _LONG_
677      generator[k]=(A.H)[j][k];
678    }
679    generator[A.columns]=0;
680    // saturation variable
681    // Note that the relative order of the variables is important (because
682    // of the reverse lexicographical refinement of the weight).
683
684    if(w.weight(generator)!=0)
685      cerr<<"\nWARNING: ideal& ideal::Bigatti_LaScala_Robbiano_ideal(matrix&, "
686        "const term_ordering&):\nInvalid row space vector does not induce "
687        "homogeneous grading."<<endl;
688
689    binomial* bin=new binomial(A.columns+1,generator,w);
690    add_generator(*bin);
691    // insert generator
692  }
693  delete[] generator;
694  return *this;
695}
696
697/////////////////////////////////////////////////////////////////////////////
698//////////////// public member functions ////////////////////////////////////
699/////////////////////////////////////////////////////////////////////////////
700
701/////////////////// constructors and destructor /////////////////////////////
702
703ideal::ideal(matrix& A, const term_ordering& _w, const int& algorithm)
704{
705
706  // check arguments as far as possible
707
708  if(A.error_status()<0)
709  {
710    cerr<<"\nWARNING: ideal::ideal(matrix&, const term_ordering&, const "
711      "int&):\ncannot create ideal from a corrupt input matrix"<<endl;
712    size=-1;
713    return;
714  }
715
716  if(_w.error_status()<0)
717  {
718    cerr<<"\nWARNING: ideal::ideal(matrix&, const term_ordering&, const "
719      "int&):\ncannot create ideal with a corrupt input ordering"<<endl;
720    size=-1;
721    return;
722  }
723
724  if((_w.number_of_elimination_variables()!=0) &&
725     (_w.number_of_weighted_variables()!=A.columns))
726    cerr<<"\nWARNING: ideal& ideal::ideal(matrix&, const term_ordering&):\n"
727      "argument term ordering might be inappropriate"<<endl;
728
729#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
730
731  create_subset_tree();
732
733#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
734
735  size=0;
736
737  // initialize the S-pair flags with the default value
738  // (this is not really necessray, but looks nicer when outputting the
739  // ideal without having computed a Groebner basis)
740  rel_primeness=1;
741  M_criterion=2;
742  F_criterion=0;
743  B_criterion=8;
744  second_criterion=0;
745
746  interreduction_percentage=12.0;
747
748  // construct the ideal according to the algorithm
749  switch(algorithm)
750  {
751      case CONTI_TRAVERSO:
752        Conti_Traverso_ideal(A,_w);
753        break;
754      case POSITIVE_CONTI_TRAVERSO:
755        Positive_Conti_Traverso_ideal(A,_w);
756        break;
757      case POTTIER:
758        Pottier_ideal(A,_w);
759        break;
760      case HOSTEN_STURMFELS:
761        Hosten_Sturmfels_ideal(A,_w);
762        break;
763      case DIBIASE_URBANKE:
764        DiBiase_Urbanke_ideal(A,_w);
765        break;
766      case BIGATTI_LASCALA_ROBBIANO:
767        Bigatti_LaScala_Robbiano_ideal(A,_w);
768        break;
769      default:
770        cerr<<"\nWARNING: ideal::ideal(matrix&, const term_ordering&, const "
771          "int&):\nunknown algorithm for ideal construction"<<endl;
772        size=-1;
773        return;
774  }
775  number_of_new_binomials=size;
776}
777
778ideal::ideal(const ideal& I)
779{
780
781  if(I.error_status()<0)
782    cerr<<"\nWARNING: ideal::ideal(const ideal&):\n"
783      "trying to create ideal from a corrupt one"<<endl;
784
785  size=0;
786  // the size is automatically incremented when copying the generators
787
788  w=I.w;
789
790  rel_primeness=I.rel_primeness;
791  M_criterion=I.M_criterion;
792  F_criterion=I.F_criterion;
793  B_criterion=I.B_criterion;
794  second_criterion=I.second_criterion;
795
796  interreduction_percentage=I.interreduction_percentage;
797
798  // copy generators
799  // To be sure to get a real copy of the argument ideal, the lists
800  // aux_list and new_generators are also copied.
801  list_iterator iter;
802
803
804#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
805
806  iter.set_to_list(I.generators);
807
808  while(iter.is_at_end()==FALSE)
809  {
810    binomial* bin=new binomial(iter.get_element());
811    add_generator(*bin);
812    iter.next();
813  }
814
815  iter.set_to_list(I.new_generators);
816
817  while(iter.is_at_end()==FALSE)
818  {
819    binomial* bin=new binomial(iter.get_element());
820    add_new_generator(*bin);
821    iter.next();
822  }
823
824#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
825
826#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
827
828  create_subset_tree();
829
830  for(int i=0;i<Number_of_Lists;i++)
831  {
832    iter.set_to_list(I.generators[i]);
833
834    while(iter.is_at_end()==FALSE)
835    {
836      binomial* bin=new binomial(iter.get_element());
837      add_generator(*bin);
838      iter.next();
839    }
840  }
841
842  for(int i=0;i<Number_of_Lists;i++)
843  {
844    iter.set_to_list(I.new_generators[i]);
845
846    while(iter.is_at_end()==FALSE)
847    {
848      binomial* bin=new binomial(iter.get_element());
849      add_new_generator(*bin);
850      iter.next();
851    }
852  }
853
854#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
855
856  iter.set_to_list(I.aux_list);
857
858  while(iter.is_at_end()==FALSE)
859  {
860    binomial* bin=new binomial(iter.get_element());
861    aux_list._insert(*bin);
862    iter.next();
863  }
864  number_of_new_binomials=size;
865}
866
867ideal::ideal(ifstream& input, const term_ordering& _w, const int&
868             number_of_generators)
869{
870  if(_w.error_status()<0)
871  {
872    cerr<<"\nWARNING: ideal::ideal(ifstream&, const term_ordering&, const "
873      "int&):\ncannot create ideal with a corrupt input ordering"<<endl;
874    size=-1;
875    return;
876  }
877
878  w=_w;
879
880  // initialize the S-pair flags with the default value
881  // (this is not really necessray, but looks nicer when outputting the
882  // ideal without having computed a Groebner basis)
883  rel_primeness=1;
884  M_criterion=2;
885  F_criterion=0;
886  B_criterion=8;
887  second_criterion=0;
888
889  interreduction_percentage=12.0;
890
891#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
892
893  create_subset_tree();
894
895#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
896
897  int number_of_variables=
898    w.number_of_elimination_variables()+w.number_of_weighted_variables();
899  Integer* generator=new Integer[number_of_variables];
900
901  for(long i=0;i<number_of_generators;i++)
902  {
903    for(int j=0;j<number_of_variables;j++)
904    {
905      input>>generator[j];
906
907      if(!input)
908        // input failure, set "error flag"
909      {
910        cerr<<"\nWARNING: ideal::ideal(ifstream&, const term_ordering&, "
911          "const int&): \ninput failure when reading generator "<<i<<endl;
912        size=-2;
913        delete[] generator;
914        return;
915      }
916    }
917    binomial* bin=new binomial(number_of_variables,generator,w);
918    add_generator(*bin);
919  }
920  size=number_of_generators;
921  number_of_new_binomials=size;
922  delete[] generator;
923}
924
925ideal::~ideal()
926{
927
928#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
929
930  destroy_subset_tree();
931
932#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
933
934  // The destructor of the lists is automatically called.
935}
936
937///////////////////// object information ////////////////////////////////////
938
939long ideal::number_of_generators() const
940{
941  return size;
942}
943
944int ideal::error_status() const
945{
946  if(size<0)
947    return -1;
948  else
949    return 0;
950}
951
952//////////////////////////// output /////////////////////////////////////////
953
954void ideal::print() const
955{
956  printf("\nterm ordering:\n");
957  w.print();
958
959  printf("\ngenerators:\n");
960
961#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
962
963  for(int i=0;i<Number_of_Lists;i++)
964    generators[i].ordered_print(w);
965
966#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
967
968#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
969
970    generators.ordered_print(w);
971
972#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
973
974  printf("\nnumber of generators: %ld\n",size);
975}
976
977void ideal::print_all() const
978{
979  print();
980  cout<<"\nCurrently used S-pair criteria:"<<endl;
981  if(rel_primeness)
982    cout<<"relatively prime leading terms"<<endl;
983  if(M_criterion)
984    cout<<"criterion M"<<endl;
985  if(F_criterion)
986    cout<<"criterion F"<<endl;
987  if(B_criterion)
988    cout<<"criterion B"<<endl;
989  if(second_criterion)
990    cout<<"second criterion"<<endl;
991  cout<<"\nInterreduction frequency:  "<<setprecision(1)
992      <<interreduction_percentage<<" %"<<endl;
993}
994
995void ideal::print(FILE *output) const
996{
997  fprintf(output,"\nterm ordering:\n");
998  w.print(output);
999
1000  fprintf(output,"\ngenerators:\n");
1001
1002#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
1003
1004  for(int i=0;i<Number_of_Lists;i++)
1005    generators[i].ordered_print(output,w);
1006
1007#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
1008
1009#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
1010
1011    generators.ordered_print(output,w);
1012
1013#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
1014
1015  fprintf(output,"\nnumber of generators: %ld\n",size);
1016
1017  fprintf(output,"\nInterreduction frequency:  %.1f %% \n", interreduction_percentage);
1018}
1019
1020void ideal::print_all(FILE* output) const
1021{
1022  print(output);
1023  fprintf(output,"\nCurrently used S-pair criteria:\n");
1024  if(rel_primeness)
1025    fprintf(output,"relatively prime leading terms\n");
1026  if(M_criterion)
1027    fprintf(output,"criterion M\n");
1028  if(F_criterion)
1029    fprintf(output,"criterion F\n");
1030  if(B_criterion)
1031    fprintf(output,"criterion B\n");
1032  if(second_criterion)
1033    fprintf(output,"second criterion\n");
1034}
1035
1036void ideal::print(ofstream& output) const
1037{
1038  output<<"\nterm ordering:\n"<<endl;
1039  w.print(output);
1040
1041  output<<"\ngenerators:\n"<<endl;
1042
1043#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
1044
1045  for(int i=0;i<Number_of_Lists;i++)
1046    generators[i].ordered_print(output,w);
1047
1048#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
1049
1050#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
1051
1052    generators.ordered_print(output,w);
1053
1054#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
1055
1056    output<<"\nnumber of generators: "<<size<<endl;
1057}
1058
1059void ideal::print_all(ofstream& output) const
1060{
1061  print(output);
1062  output<<"\nCurrently used S-pair criteria:"<<endl;
1063  if(rel_primeness)
1064    output<<"relatively prime leading terms"<<endl;
1065  if(M_criterion)
1066    output<<"criterion M"<<endl;
1067  if(F_criterion)
1068    output<<"criterion F"<<endl;
1069  if(B_criterion)
1070    output<<"criterion B"<<endl;
1071  if(second_criterion)
1072    output<<"second_criterion"<<endl;
1073  output<<"\nInterreduction frequency:  "<<setprecision(1)
1074        <<interreduction_percentage<<" %"<<endl;
1075}
1076
1077void ideal::format_print(ofstream& output) const
1078{
1079#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
1080
1081  for(int i=0;i<Number_of_Lists;i++)
1082    generators[i].ordered_format_print(output,w);
1083
1084#endif  // SUPPORT_DRIVEN_METHODS_EXTENDED
1085
1086#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
1087
1088    generators.ordered_format_print(output,w);
1089
1090#endif  // NO_SUPPORT_DRIVEN_METHODS_EXTENDED
1091}
1092#endif  // IDEAL_CC
Note: See TracBrowser for help on using the repository browser.