# source:git/IntegerProgramming/ideal.cc@2a94d3

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