PolyBoRi
linear_algebra_step.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
14 //*****************************************************************************
15 
16 #ifndef polybori_groebner_linear_algebra_step_h_
17 #define polybori_groebner_linear_algebra_step_h_
18 
19 // include basic definitions
20 #include "groebner_defs.h"
21 #include "add_up.h"
22 #include "nf.h"
23 #include "draw_matrix.h"
24 
25 #include "GroebnerStrategy.h"
28 
29 #include "BitMask.h"
30 #include "PseudoLongProduct.h"
31 #include "Long64From32BitsPair.h"
32 
33 #ifdef PBORI_HAVE_NTL
34 #include <NTL/GF2.h>
35 #include <NTL/mat_GF2.h>
36 NTL_CLIENT
37 #endif
38 #ifdef PBORI_HAVE_M4RI
39 const int M4RI_MAXKAY = 16;
40 #endif
41 
42 #include <vector>
43 #include <utility>
44 #include <sstream>
45 
47 
48 inline int
51  if (ms.isZero())
52  return -1;
53  else {
54  //Monomial min=*(std::min_element(ms.begin(),ms.end(), LessWeightedLengthInStrat(strat)));
55  Exponent min=*(std::min_element(ms.expBegin(),ms.expEnd(), LargerDegreeComparer()));
56  return strat.index(min);
57  }
58 }
59 
60 
61 #if defined(PBORI_HAVE_NTL) || defined(PBORI_HAVE_M4RI)
62 
63 typedef Exponent::idx_map_type from_term_map_type;
64 
65 
66 
67 inline void
68 fix_point_iterate(const GroebnerStrategy& strat,std::vector<Polynomial> extendable_system, std::vector<Polynomial>& res1,MonomialSet& res_terms,MonomialSet& leads_from_strat){
69 
70  BoolePolyRing current_ring(res_terms.ring());
71  leads_from_strat=MonomialSet(current_ring);
72  res_terms=MonomialSet(current_ring);
73 
74  for(std::size_t i=0;i<extendable_system.size();i++){
75  Polynomial p=extendable_system[i];
76  PBORI_ASSERT(p.ring().id() == current_ring.id());
77 
78  if PBORI_UNLIKELY(p.isZero()) continue;
79 
80  p=cheap_reductions(strat.generators, p);
81 
82  // Polynomial p=mod_mon_set(p_orig.diagram(),strat.generators.monomials);
83  // if (strat.generators.optLL){
84  // Polynomial p_bak2=p;
85  // p=ll_red_nf(p,strat.generators.llReductor);
86  // if (p!=p_bak2) p=mod_mon_set(p.diagram(),strat.generators.monomials);
87  // }
88  MonomialSet new_terms=p.diagram().diff(res_terms);
89  MonomialSet::const_iterator it=new_terms.begin();
90  MonomialSet::const_iterator end=new_terms.end();
91  while(it!=end){
92  Monomial m=*it;
93 
94  int index=select_largest_degree(strat.generators, m);
95  if PBORI_LIKELY(index>=0){
96 
97  Monomial m2=m/strat.generators[index].lead;
98  Polynomial p2=m2*strat.generators[index].p;
99  extendable_system.push_back(p2);
100  PBORI_ASSERT(current_ring.id() == strat.generators[index].lead.ring().id());
101  PBORI_ASSERT(current_ring.id() == strat.generators[index].p.ring().id());
102  PBORI_ASSERT(current_ring.id() == m.ring().id());
103  PBORI_ASSERT(current_ring.id() == m2.ring().id());
104  PBORI_ASSERT(current_ring.id() == p2.ring().id());
105  }
106  ++it;
107  }
108  res_terms=res_terms.unite(new_terms);
109  res1.push_back(p);
110  }
111  leads_from_strat=res_terms.diff(mod_mon_set(res_terms,strat.generators.minimalLeadingTerms));
112 }
113 
114 inline void
115 fill_matrix(mzd_t* mat,std::vector<Polynomial> polys, from_term_map_type from_term_map){
116  for(std::size_t i=0;i<polys.size();i++){
117  Polynomial::exp_iterator it=polys[i].expBegin();//not order dependend
118  Polynomial::exp_iterator end=polys[i].expEnd();
119  while(it!=end){
120  #ifndef PBORI_HAVE_M4RI
121  mat[i][from_term_map[*it]]=1;
122  #else
123  from_term_map_type::const_iterator from_it=from_term_map.find(*it);
124  PBORI_ASSERT(from_it!=from_term_map.end());
125  mzd_write_bit(mat,i,from_it->second,1);
126  #endif
127  it++;
128  }
129  }
130 }
131 
132 inline void
133 translate_back(std::vector<Polynomial>& polys, MonomialSet leads_from_strat,mzd_t* mat,const std::vector<int>& ring_order2lex, const std::vector<Exponent>& terms_as_exp,const std::vector<Exponent>& terms_as_exp_lex,int rank){
134  int cols=mat->ncols;
135  // int rows=mat->nrows; /// @todo unused?
136 
137  int i;
138  for(i=0;i<rank;i++){
139  int j;
140  std::vector<int> p_t_i;
141 
142  bool from_strat=false;
143  for(j=0;j<cols;j++){
144  #ifndef PBORI_HAVE_M4RI
145  if (mat[i][j]==1){
146  #else
147  if PBORI_UNLIKELY(mzd_read_bit(mat,i,j)==1){
148  #endif
149  if (p_t_i.size()==0){
150  if (leads_from_strat.owns(terms_as_exp[j])) {
151  from_strat=true;break;
152  }
153  }
154  p_t_i.push_back(ring_order2lex[j]);
155  }
156  }
157  if (!(from_strat)){
158  std::vector<Exponent> p_t(p_t_i.size());
159  std::sort(p_t_i.begin(),p_t_i.end(),std::less<int>());
160  for(std::size_t j=0;j<p_t_i.size();j++){
161  p_t[j]=terms_as_exp_lex[p_t_i[j]];
162  }
163  polys.push_back(add_up_lex_sorted_exponents(leads_from_strat.ring(),
164  p_t,0,p_t.size()));
165  PBORI_ASSERT(!(polys[polys.size()-1].isZero()));
166  }
167  }
168 }
169 
170 
171 inline void
172 linalg_step(std::vector<Polynomial>& polys, MonomialSet terms,MonomialSet leads_from_strat, bool log, bool optDrawMatrices=false, const char* matrixPrefix="mat"){
173  if PBORI_UNLIKELY(polys.size()==0) return;
174 
175  static int round=0;
176 
177  int rows=polys.size();
178  int cols=terms.size();
179  if PBORI_UNLIKELY(log){
180  std::cout<<"ROWS:"<<rows<<"COLUMNS:"<<cols<<std::endl;
181  }
182  #ifndef PBORI_HAVE_M4RI
183  mat_GF2 mat(INIT_SIZE,rows,cols);
184  #else
185  mzd_t* mat=mzd_init(rows,cols);
186  #endif
187  MatrixMonomialOrderTables tabs(terms);
188 
189  fill_matrix(mat,polys,tabs.from_term_map);
190 
191  polys.clear();
192  #ifndef PBORI_HAVE_M4RI
193  int rank=gauss(mat);
194  #else
195  if PBORI_UNLIKELY(optDrawMatrices){
196  ++round;
197  std::ostringstream matname;
198  matname << matrixPrefix << round << ".png"<< std::ends;
199  draw_matrix(mat, matname.str().c_str());
200  }
201  int rank=mzd_echelonize_m4ri(mat, TRUE, 0);//optimal_k_for_gauss(mat->nrows,mat->ncols,strat));
202  #endif
203  if PBORI_UNLIKELY(log){
204  std::cout<<"finished gauss"<<std::endl;
205  }
206  translate_back(polys, leads_from_strat, mat,tabs.ring_order2lex, tabs.terms_as_exp,tabs.terms_as_exp_lex,rank);
207 
208  #ifdef PBORI_HAVE_M4RI
209  mzd_free(mat);
210  #endif
211 }
212 
213 inline void
214 printPackedMatrixMB(mzd_t* mat){
215  int i,j;
216  for(i=0;i<mat->nrows;i++){
217  for(j=0;j<mat->ncols;j++){
218  std::cout<<(int)mzd_read_bit(mat,i,j);
219  }
220  std::cout<<std::endl;
221  }
222 }
223 
224 inline mzd_t*
225 transposePackedMB(mzd_t* mat){
226  return mzd_transpose(NULL,mat);
227  /*mzd_t* res=mzd_init(mat->ncols,mat->nrows);
228  int i,j;
229  for(i=0;i<mat->nrows;i++){
230  for(j=0;j<mat->ncols;j++){
231  mzd_write_bit(res,j,i,mzd_read_bit(mat,i,j));
232  }
233  }
234  return res;*/
235 }
236 
237 inline mzd_t*
238 pbori_transpose(mzd_t* mat) {
239 
240  if PBORI_UNLIKELY(mat->nrows == 0)
241  return mzd_init(mat->ncols, 0);
242 
243  if PBORI_UNLIKELY(mat->ncols == 0)
244  return mzd_init(0, mat->nrows);
245 
246  return mzd_transpose(NULL,mat);
247 }
248 
249 
250 
251 inline void
252 linalg_step_modified(std::vector < Polynomial > &polys, MonomialSet terms, MonomialSet leads_from_strat, bool log, bool optDrawMatrices, const char* matrixPrefix)
253 {
254  BoolePolyRing current_ring(terms.ring());
255  PBORI_ASSERT(current_ring.id() == leads_from_strat.ring().id());
256 #ifndef PBORI_NDEBUG
257  std::vector < Polynomial >::const_iterator start(polys.begin()),
258  finish(polys.end());
259 
260  while (start != finish) {
261  PBORI_ASSERT(current_ring.id() == start->ring().id());
262  ++start;
263  }
264 #endif
265 
266  int unmodified_rows=polys.size();
267  int unmodified_cols=terms.size();
268 
270  if (PBORI_UNLIKELY( (PseudoLongProduct(unmodified_cols, unmodified_rows) >
271  Long64From32BitsPair<4u, 2820130816u>::get()) )){
272  PBoRiError error(CTypes::matrix_size_exceeded);
273  throw error;
274  }
275 
276  static int round=0;
277  round++;
278  // const int russian_k=16; ///
279  MonomialSet terms_unique(current_ring);
280  std::vector < Monomial > terms_unique_vec;
281  MonomialSet terms_step1(current_ring);
282  std::vector < std::pair < Polynomial, Monomial > >polys_lm;
283 
284  for (std::size_t i = 0; i < polys.size(); i++) {
285  if PBORI_LIKELY(!(polys[i].isZero()))
286  polys_lm.push_back(std::pair < Polynomial, Monomial > (polys[i], polys[i].lead()));
287  }
288 std:: sort(polys_lm.begin(), polys_lm.end(), PolyMonomialPairComparerLess());
289  polys.clear();
290 
291  //special cases
292  if PBORI_UNLIKELY(polys_lm.size() == 0)
293  return;
294  Monomial last(current_ring);
295  if PBORI_UNLIKELY(polys_lm[0].second.deg() == 0) {
296  PBORI_ASSERT(polys_lm[0].first.isOne());
297  polys.resize(1, current_ring);
298  polys[0] = 1;
299 
300  return;
301  }
302 
303  std::vector < Polynomial > polys_triangular;
304  std::vector < Polynomial > polys_rest;
305 
306  {
307  std::vector < std::pair < Polynomial, Monomial > >::iterator it = polys_lm.begin();
308  std::vector < std::pair < Polynomial, Monomial > >::iterator end = polys_lm.end();
309 
310  while (it != end) {
311  if PBORI_LIKELY(it->second != last) {
312  last = it->second;
313  polys_triangular.push_back(it->first);
314 
315 
316  PBORI_ASSERT(std:: find(terms_unique_vec.begin(), terms_unique_vec.end(), it->second) == terms_unique_vec.end());
317 
318  terms_unique_vec.push_back(it->second);
319  terms_step1=terms_step1.unite(it->first.diagram());
320  } else
321  polys_rest.push_back(it->first);
322  it++;
323  }
324  }
325  polys.clear();
326  std::reverse(polys_triangular.begin(), polys_triangular.end());
327  terms_unique = add_up_generic(terms_unique_vec, current_ring.zero());
328  PBORI_ASSERT(terms_step1.diff(terms).isZero());
329  PBORI_ASSERT(polys_triangular.size()!=0);
330  from_term_map_type eliminated2row_number;
331  int remaining_cols;
332  mzd_t* mat_step1;
333  std::vector<int> compactified_columns2old_columns;
334  int rows_step1;
335  std::vector<int> row_start;
336  //std::vector<Polynomial> result;
337  MatrixMonomialOrderTables step1(terms_step1);
338  //std::vector<Exponent> terms_as_exp_step1;
339  {
340  int rows=polys_triangular.size();
341  int cols=terms_step1.size();
342  rows_step1=rows;
343  if PBORI_UNLIKELY(log){
344  std::cout<<"STEP1: ROWS:"<<rows<<"COLUMNS:"<<cols<<std::endl;
345  }
346 
347  mat_step1=mzd_init(rows,cols);
348  //vector<Exponent> terms_as_exp_lex_step1;
349  //vector<int> ring_order2lex_step1;
350  //vector<int> lex_order2ring_step1;
351  // from_term_map_type from_term_map_step1;
352 //setup_order_tables(terms_as_exp_step1,terms_as_exp_lex_step1,ring_order2lex_step1,lex_order2ring_step1,from_term_map_step1, terms_step1);
353  fill_matrix(mat_step1,polys_triangular,step1.from_term_map);
354 
355  polys_triangular.clear();
356 
357  if PBORI_UNLIKELY(optDrawMatrices) {
358  std::ostringstream matname;
359  matname << matrixPrefix << round << "_step1.png" <<std::ends;
360  draw_matrix(mat_step1, matname.str().c_str());
361  }
362  //optimize: call back subst directly
363  mzd_top_echelonize_m4ri
364  (mat_step1,0);
365 
366  if PBORI_UNLIKELY(log){
367  std::cout<<"finished gauss"<<std::endl;
368  }
369  int rank=mat_step1->nrows;
370 
371  //sort rows
372  int pivot_row=0;
373  row_start.resize(rows);
374  PBORI_ASSERT(cols>=rows);
375  remaining_cols=cols-rows;
376  compactified_columns2old_columns.resize(remaining_cols);
377  for(int i=0;i<cols;i++){
378  int j=pivot_row;
379  for(;j<rows;j++){
380  if PBORI_UNLIKELY(mzd_read_bit(mat_step1,j,i)==1){
381  if (j!=pivot_row)
382  mzd_row_swap(mat_step1,j,pivot_row);
383 
384  eliminated2row_number[step1.terms_as_exp[i]]=pivot_row;
385  row_start[pivot_row]=i;
386  pivot_row++;
387 
388  break;
389  }
390  }
391  if PBORI_UNLIKELY(j==rows){
392  PBORI_ASSERT(i>=pivot_row);
393  compactified_columns2old_columns[i-pivot_row]=i;
394  }
395 
396  }
397  if PBORI_UNLIKELY(log){
398  std::cout<<"finished sort"<<std::endl;
399  }
400  PBORI_ASSERT(pivot_row==rows);
401 
402  translate_back(polys, leads_from_strat, mat_step1,step1.ring_order2lex, step1.terms_as_exp,step1.terms_as_exp_lex,rank);
403 
404  if PBORI_UNLIKELY(log){
405  std::cout<<"finished translate"<<std::endl;
406  }
407 
408  //delete columns
409  mzd_t* transposed_step1 = pbori_transpose(mat_step1);
410  if PBORI_UNLIKELY(log){
411  std::cout<<"finished transpose"<<std::endl;
412  }
413  mzd_free(mat_step1);
414 
415  for(int i=0;i<remaining_cols;i++){
416  int source=compactified_columns2old_columns[i];
417  PBORI_ASSERT(i<=source);
418  PBORI_ASSERT(source<=transposed_step1->nrows);
419  if PBORI_LIKELY(i!=source) mzd_row_swap(transposed_step1,source,i);
420 
421  }
422  if PBORI_UNLIKELY(log){
423  std::cout<<"finished permute"<<std::endl;
424  }
425 
426  //cols, rows arguments are swapped, as matrix is transposed
427  mzd_t* sub_step1=mzd_submatrix(NULL,transposed_step1,0,0,remaining_cols,rows);
428 
429  if PBORI_UNLIKELY(log){
430  std::cout<<"finished submat"<<std::endl;
431  }
432  mzd_free(transposed_step1);
433  mat_step1 = pbori_transpose(sub_step1);
434  if PBORI_UNLIKELY(log){
435  std::cout<<"finished transpose"<<std::endl;
436  }
437  mzd_free(sub_step1);
438  }
439  MonomialSet terms_step2=terms.diff(terms_unique);
440  const int rows_step2=polys_rest.size();
441  const int cols_step2=terms_step2.size();
442  mzd_t* mat_step2=mzd_init(rows_step2,cols_step2);
443  mzd_t* mat_step2_factor=mzd_init(rows_step2,mat_step1->nrows);
444  MatrixMonomialOrderTables step2(terms_step2);
445  // vector<Exponent> step2.terms_as_exp;
446  // vector<Exponent> step2.terms_as_exp_lex;
447  // vector<int> step2.ring_order2lex;
448  // vector<int> step2.lex_order2ring;
449  // from_term_map_type step2.from_term_map;
450  // setup_order_tables(step2.terms_as_exp,step2.terms_as_exp_lex,step2.ring_order2lex,step2.lex_order2ring,step2.from_term_map, terms_step2);
451 
452 
453  for(std::size_t i=0;i<polys_rest.size();i++){
454  Polynomial p_r=polys_rest[i];
455  Polynomial p_t=p_r.diagram().intersect(terms_step2);
456  Polynomial p_u=p_r.diagram().diff(p_t.diagram());
457  Polynomial::exp_iterator it(p_u.expBegin()), end(p_u.expEnd());
458 
459  while(it!=end){
460  Exponent e=*it;
461  from_term_map_type::const_iterator from_it=eliminated2row_number.find(e);
462  PBORI_ASSERT(step1.terms_as_exp[row_start[from_it->second]]==e);
463  PBORI_ASSERT(from_it!=eliminated2row_number.end());
464  int index=from_it->second;//...translate e->line number;
465  mzd_write_bit(mat_step2_factor,i,index,1);
466  it++;
467  }
468  it=p_t.expBegin();
469  end=p_t.expEnd();
470  while(it!=end){
471  Exponent e=*it;
472  from_term_map_type::const_iterator from_it=step2.from_term_map.find(e);
473  PBORI_ASSERT(from_it!=step2.from_term_map.end());
474  int index=from_it->second;
475  mzd_write_bit(mat_step2,i,index,1);
476  it++;
477  }
478  }
479 
480  if PBORI_UNLIKELY(log){
481  std::cout<<"iterate over rest polys"<<std::endl;
482  }
483 
484  std::vector<int> remaining_col2new_col(remaining_cols);
485  for(int i=0;i<remaining_cols;i++){
486  remaining_col2new_col[i]=step2.from_term_map[step1.terms_as_exp[compactified_columns2old_columns[i]]];
487  }
488  PBORI_ASSERT(mat_step2_factor->ncols==mat_step1->nrows);
489  PBORI_ASSERT(mat_step1->nrows==terms_unique.size());
490  PBORI_ASSERT(mat_step1->ncols==remaining_cols);
491 
492  if PBORI_UNLIKELY(optDrawMatrices)
493  {
494  std::ostringstream matname;
495  matname << matrixPrefix << round << "_mult_A.png"<<std::ends;
496  draw_matrix(mat_step2_factor, matname.str().c_str());
497  matname.clear();
498  matname << mat_step2_factor << round << "_mult_B.png"<<std::ends;
499  draw_matrix(mat_step1,matname.str().c_str());
500  }
501  if PBORI_UNLIKELY(log){
502  std::cout<<"start mult"<<std::endl;
503  }
504 
505  mzd_t* eliminated;
506  if PBORI_LIKELY((mat_step2_factor->nrows!=0) && (mat_step1->nrows!=0) && (mat_step2_factor->ncols!=0) && (mat_step1->ncols!=0))
507  eliminated=mzd_mul_m4rm(NULL,mat_step2_factor,mat_step1,0);
508  else
509  eliminated=mzd_init(mat_step2_factor->nrows,mat_step1->ncols);
510 
511  mzd_free(mat_step2_factor);
512  if PBORI_UNLIKELY(log){
513  std::cout<<"end mult"<<std::endl;
514  }
515  mzd_free(mat_step1);
516  PBORI_ASSERT(polys_rest.size()==eliminated->nrows);
517  PBORI_ASSERT(mat_step2->nrows==eliminated->nrows);
518  for(std::size_t i=0;i<polys_rest.size();i++){
519  PBORI_ASSERT(remaining_cols==eliminated->ncols);
520  for(int j=0;j<remaining_cols;j++){
521  if PBORI_UNLIKELY(mzd_read_bit(eliminated,i,j)==1){
522  PBORI_ASSERT(step2.terms_as_exp[remaining_col2new_col[j]]==step1.terms_as_exp[compactified_columns2old_columns[j]]);
523 
524  if PBORI_UNLIKELY(mzd_read_bit(mat_step2,i,remaining_col2new_col[j])==1){
525  mzd_write_bit(mat_step2,i,remaining_col2new_col[j],0);
526  } else mzd_write_bit(mat_step2,i,remaining_col2new_col[j],1);
527  }
528  }
529  }
530 
531  mzd_free(eliminated);
532 
533  if PBORI_UNLIKELY(log){
534  std::cout<<"STEP2: ROWS:"<<rows_step2<<"COLUMNS:"<<cols_step2<<std::endl;
535  }
536  if PBORI_UNLIKELY(optDrawMatrices)
537  {
538  std::ostringstream matname;
539  matname << matrixPrefix << round << "_step2.png"<<std::ends;
540  draw_matrix(mat_step2, matname.str().c_str());
541  }
542 
543 
544  int rank_step2;
545  if ((mat_step2->ncols>0) &&( mat_step2->nrows>0)){
546  rank_step2=
547  mzd_echelonize_m4ri(mat_step2,TRUE,0);
548  //mzd_echelonize_pluq(mat_step2,TRUE);
549  } else
550  rank_step2=0;
551 
552  if PBORI_UNLIKELY(log){
553  std::cout<<"finished gauss"<<std::endl;
554  }
555 
556  translate_back(polys, leads_from_strat, mat_step2,step2.ring_order2lex, step2.terms_as_exp,step2.terms_as_exp_lex,rank_step2);
557  mzd_free(mat_step2);
558 
559 
560 }
561 
562 
563 inline std::vector<Polynomial>
564 gauss_on_polys(const std::vector<Polynomial>& orig_system){
565 
566  if (orig_system.empty())
567  return orig_system;
568 
569  Polynomial init(0, orig_system[0].ring());
570  MonomialSet terms=unite_polynomials(orig_system, init);
571  MonomialSet from_strat(init.ring());//no strat
572  std::vector<Polynomial> polys(orig_system);
573  linalg_step(polys, terms, from_strat, false);
574  return polys;
575 }
576 #endif
577 
579 
580 #endif /* polybori_groebner_linear_algebra_step_h_ */
This class is just a wrapper for using variables for storing indices as interim data structure for Bo...
Definition: BooleExponent.h:34
Polynomial add_up_generic(const std::vector< T > &res_vec, int start, int end, Polynomial init)
Definition: add_up.h:205
polybori::BooleExponent Exponent
Definition: groebner_defs.h:33
Polynomial cheap_reductions(const ReductionStrategy &strat, Polynomial p)
Definition: nf.cc:831
size_type index(const KeyType &key) const
Retrieve index associated to key.
Definition: PolyEntryVector.h:99
#define END_NAMESPACE_PBORIGB
Definition: groebner_defs.h:16
const self & diagram() const
Access internal decision diagram.
Definition: BooleSet.h:231
const ring_type & ring() const
Access ring, where this belongs to.
Definition: BoolePolynomial.h:478
self divisorsOf(const term_type &rhs) const
Compute intersection with divisors of rhs.
Definition: BooleSet.cc:156
void draw_matrix(mzd_t *mat, const char *filename)
Definition: draw_matrix.h:36
exp_iterator expEnd() const
Finish of iteration over exponent vectors.
Definition: BooleSet.cc:109
This class reinterprets decicion diagram managers as Boolean polynomial rings, adds an ordering and v...
Definition: BoolePolyRing.h:40
BoolePolynomial Polynomial
Definition: embed.h:51
Polynomial unite_polynomials(const std::vector< Polynomial > &res_vec, int start, int end, Polynomial init)
Definition: add_up.h:153
#define BEGIN_NAMESPACE_PBORIGB
Definition: groebner_defs.h:15
exp_iterator expBegin() const
Start of iteration over exponent vectors.
Definition: BooleSet.cc:101
This class wraps the underlying decicion diagram type and defines the necessary operations.
Definition: BoolePolynomial.h:85
hash_type id() const
Get unique identifier for this ring.
Definition: BoolePolyRing.h:151
#define PBORI_LIKELY(expression)
For optimizing if-branches.
Definition: pbori_defs.h:56
polybori::BooleSet MonomialSet
Definition: groebner_defs.h:45
bool isZero() const
Test whether diagram represents the empty set.
Definition: CCuddDDFacade.h:244
MonomialSet mod_mon_set(const MonomialSet &as, const MonomialSet &vs)
Definition: nf.cc:855
size_type size() const
Returns number of terms.
Definition: BooleSet.h:242
int select_largest_degree(const ReductionStrategy &strat, const Monomial &m)
Definition: linear_algebra_step.h:49
#define PBORI_ASSERT(arg)
Definition: pbori_defs.h:118
const ring_type & ring() const
Access ring, where this belongs to.
Definition: BooleMonomial.h:235
MonomialSet add_up_lex_sorted_exponents(const BoolePolyRing &ring, std::vector< Exponent > &vec, int start, int end)
Definition: add_up.h:61
bool_type isZero() const
Check whether polynomial is constant zero.
Definition: BoolePolynomial.h:294
LeadingTerms leadingTerms
Definition: ReductionTerms.h:51
const_iterator begin() const
Start of iteration over terms.
Definition: BooleSet.cc:70
Definition: BooleSet.h:57
This class defines ReductionStrategy.
Definition: ReductionStrategy.h:34
This class is just a wrapper for using variables from cudd's decicion diagram.
Definition: BooleMonomial.h:50
This class defines LargerDegreeComparer.
Definition: LargerDegreeComparer.h:28
BooleMonomial Monomial
Definition: embed.h:53
#define PBORI_UNLIKELY(expression)
Definition: pbori_defs.h:59