source: git/IntegerProgramming/ideal.cc @ 7067b3

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