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
create_subset_tree()19 void 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
destroy_subset_tree()60 void 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
add_new_generator(binomial & bin)71 ideal& 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
add_generator(binomial & bin)90 ideal& 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
Conti_Traverso_ideal(matrix & A,const term_ordering & _w)118 ideal& 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
Positive_Conti_Traverso_ideal(matrix & A,const term_ordering & _w)172 ideal& 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
Pottier_ideal(matrix & A,const term_ordering & _w)214 ideal& 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
Hosten_Sturmfels_ideal(matrix & A,const term_ordering & _w)344 ideal& 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
DiBiase_Urbanke_ideal(matrix & A,const term_ordering & _w)445 ideal& 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
Bigatti_LaScala_Robbiano_ideal(matrix & A,const term_ordering & _w)568 ideal& 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
ideal(matrix & A,const term_ordering & _w,const int & algorithm)703 ideal::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
ideal(const ideal & I)778 ideal::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
ideal(ifstream & input,const term_ordering & _w,const int & number_of_generators)867 ideal::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
~ideal()925 ideal::~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
number_of_generators() const939 long ideal::number_of_generators() const
940 {
941 return size;
942 }
943
error_status() const944 int ideal::error_status() const
945 {
946 if(size<0)
947 return -1;
948 else
949 return 0;
950 }
951
952 //////////////////////////// output /////////////////////////////////////////
953
print() const954 void 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
print_all() const977 void 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
print(FILE * output) const995 void 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
print_all(FILE * output) const1020 void 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
print(ofstream & output) const1036 void 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
print_all(ofstream & output) const1059 void 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
format_print(ofstream & output) const1077 void 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
1093