 Basic Polynomial Algebra Subprograms (BPAS)  v. 1.652
triangularset.hpp
1 #ifndef _TRIANGULARSET_H_
2 #define _TRIANGULARSET_H_
3
4 //#include "Polynomial/mpolynomial.h"
5 #include "../polynomial.h"
6 #include "../ring.h"
7 #include "../Utils/TemplateHelpers.hpp"
8 #include "../Utils/SymbolHelpers.hpp"
9 //#include "../RegularChain/regularchain.hpp"
10 //#include "../RegularChain/zerodimensionalregularchain.hpp"
11 #include <iostream>
12
13 using std::endl;
14 using std::cerr;
15
16 extern long long unsigned int rcProfilingStart;
17 extern float primitivePartTime;
18 extern float squareFreePartTime;
19 extern float subresultantChainTime;
20 extern float zerodimensionalregularchainTime;
21 extern float pseudoDivideTime;
22 extern float normalFormTime;
23
24 //template <class Field, class RecursivePoly> RegularChain;
25
26 /**
27  * An enumeration which describes the mode of the triangular set.
28  * TS_FIXED is the ALGEBRAIC case, forces a fixed list of variables, determinining the maximum size of the TS.
29  * TS_VARIABLE is the DIFFERENTIAL case, allows the list of variables, hence size of the TS, to change.
30  **/
31 typedef enum TriangularSetMode {
32  TS_FIXED = 0x0,
33  TS_VARIABLE = 0x1
34 } TriangularSetMode;
35
36 /**
37  * A triangular set templated by a multivariate polynomial over a field.
38  * The field should be a BPASField and the multivariate polynomial should
39  * be recursively viewed, as in BPASRecursivelyViewedPolynomial.
40  */
41 template <class Field, class RecursivePoly>
42 class TriangularSet : public virtual BPASTriangularSet<Field,RecursivePoly>
43 {
44
45  protected:
46  TriangularSetMode mode; // fixed or variable TS structure
47  mpz_class characteristic; // characteristic of the TS (inherited from base Field)
48  std::vector<RecursivePoly> set; // the set of polynomials
49  std::vector<Symbol> vars; // list of active and inactive algebraic variables
50  std::vector<Symbol> algVars; // list of active algebraic variables
51  std::vector<Symbol> trcVars; // list of transcendental variables (cannot appear in polynomials)
52  Symbol sNMaxVar; // max variable of largest strongly normalized subset of the TS
53  // TODO: remove stronglyNormalized attribute and compute it when needed using sNMaxVar
54  bool stronglyNormalized; // flag whether the TS is strongly normalized
55
56  /**
57  * Determine whether the triangular set is strongly normalized and the maximum variable
58  * of the largest strongly normalized subset of the triangular set.
59  *
60  * @param
61  **/
62  void updateTriangularSetStates();
63
64  /**
65  * Determine whether after adding p the triangular set is strongly normalized and update the maximum variable
66  * of the largest strongly normalized subset of the triangular set.
67  *
68  * @param p: a recursively viewed polynomial that has just been added to the set
69  **/
70  void updateTriangularSetStates(const RecursivePoly& p);
71
72  /**
73  * Return the index of the input symbol in the array of (potentially algebraic) variables of the triangular set.
74  *
75  * @param s: a symbol
76  **/
77  int variableIndex(const Symbol& s) const;
78
79
80  public:
81  /**
82  * Default constructor: creates an empty triangular set of variable size
83  * with empty list of transcendentals
84  *
85  * @param
86  **/
88
89  /**
90  * Construct an empty triangular set of fixed size in the s decreasingly ordered
91  * variables given by xs with empty list of transcendentals.
92  *
93  * @param s: The number of polynomials
94  * @param xs: The variable names
95  **/
96  TriangularSet<Field,RecursivePoly> (const std::vector<Symbol>& xs);
97
98  /**
99  * Construct an empty triangular set of fixed size in the s decreasingly ordered
100  * variables given by xs and list of transcendentals given by ts.
101  *
102  * @param s: The number of polynomials
103  * @param xs: The variable names
104  * @param ts: The transcendental variable names
105  **/
106  TriangularSet<Field,RecursivePoly> (const std::vector<Symbol>& xs, const std::vector<Symbol>& ts);
107
108  /**
109  * Construct a variable triangular set containing p, such that the variables of p are treated as (potentially algebraic) variables,
110  * with empty list of transcendentals.
111  *
112  * @param p: The recursively viewed polynomial to add
113  **/
114  TriangularSet<Field,RecursivePoly> (const RecursivePoly& p);
115
116  /**
117  * Construct a variable triangular set containing p, such that the variables in ts are
118  * treated as transcendental, while any remaining variables of p are treated as (potentially algebraic) variables.
119  *
120  * @param p: The recursively viewed polynomial to add
121  * @param ts: The transcendental variable names
122  **/
123  TriangularSet<Field,RecursivePoly> (const RecursivePoly& p, const std::vector<Symbol>& ts);
124
125  /**
126  * Copy constructor.
127  *
128  * @param a: A triangular set
129  **/
131
132 // /**
133 // * Copy constructor
134 // *
135 // * @param a: A regular chain
136 // **/
137 // TriangularSet<Field,RecursivePoly> (const RegularChain<Field,RecursivePoly>& a);
138
139 // /**
140 // * Copy constructor
141 // *
142 // * @param a: A zero dimensional regular chain
143 // **/
144 // TriangularSet<Field,RecursivePoly> (const ZeroDimensionalRegularChain<Field,RecursivePoly>& a);
145
146  /**
147  * Move constructor.
148  *
149  * @param a: An r-value triangular set
150  **/
152
153 // /**
154 // * Move constructor
155 // *
156 // * @param a: An r-value regular chain
157 // **/
158 // TriangularSet<Field,RecursivePoly> (RegularChain<Field,RecursivePoly>&& a);
159
160 // /**
161 // * Move constructor
162 // *
163 // * @param a: An r-value zero dimensional regular chain
164 // **/
165 // TriangularSet<Field,RecursivePoly> (ZeroDimensionalRegularChain<Field,RecursivePoly>&& a);
166
167  /**
168  * Computational constructor: creates a triangular set given all the data.
169  *
170  * @param vs: variables of the triangular set
171  * @param avs: algebraic variables of the triangular set
172  * @param tvs: transcendental variables of the triangular set
173  * @param polys: polynomials of the triangular set
174  * @param tsm: whether the triangular set is variable or fixed
175  * @param c: characteristic of the triangular set
176  **/
177  TriangularSet<Field,RecursivePoly> (const std::vector<Symbol>& vs, const std::vector<Symbol>& avs, const std::vector<Symbol>& tvs, const std::vector<RecursivePoly>& ts, TriangularSetMode tsm, const mpz_class& c);
178
179  /**
180  * Deconstructor.
181  *
182  * @param
183  **/
185
186 // /**
187 // * Copy an object derived from abstract BPASTriangularSet class to type of current object
188 // *
189 // * @param ts: triangular set to copy
190 // **/
191 // inline void copy(const BPASTriangularSet<Field,RecursivePoly>& ts) override {
192 // if (dynamic_cast<const TriangularSet<Field,RecursivePoly>*>(&ts))
193 // *this = *dynamic_cast<const TriangularSet<Field,RecursivePoly>*>(&ts);
194 // else throw (std::invalid_argument("BPAS: Cannot cast BPASTriangularSet to TriangularSet."));
195 // }
196
197  /**
198  * Tests if the TriangularSet is empty.
199  *
200  * @param
201  **/
202  bool isEmpty() const;
203
204  /**
205  * Tests if the polynomial is constant relative to the TriangularSet, i.e., whether it is and element of
206  * the Field or its only variables are transcendental.
207  *
208  * @param p: a recursively viewed polynomial
209  **/
210  bool isConstantPolynomial(const RecursivePoly& p) const;
211
212  /**
213  * Assignment operator =.
214  *
215  * @param a: A triangular set
216  **/
218
219  /**
220  * Assignment operator =.
221  *
222  * @param a: A triangular set
223  **/
225
226  /**
227  * Move assignment operator =.
228  *
229  * @param a: A triangular set
230  **/
232
233  /**
234  * Move assignment operator =.
235  *
236  * @param a: A triangular set
237  **/
239
240  /**
241  * Add operator +.
242  * Adds a polynomial to a triangular set and returns a new triangular set.
243  *
244  * @param p: A recursively viewed polynomial
245  **/
246  TriangularSet<Field,RecursivePoly> operator+ (const RecursivePoly& p);
247
248  /**
249  * Add assignment operator +=.
250  * Adds a polynomial to a triangular set.
251  *
252  * @param p: A recursively viewed polynomial
253  **/
254  TriangularSet<Field,RecursivePoly>& operator+= (const RecursivePoly& p);
255
256  /**
257  * Identity operator ==.
258  *
259  * @param a: A triangular set
260  **/
262
263  /**
264  * Negated identity operator !=.
265  *
266  * @param a: A triangular set
267  **/
269
270  /**
271  * Get the number of variables.
272  *
273  * @param
274  **/
275  inline int numberOfVariables() const {
276  return vars.size();
277  }
278
279  /**
280  * Get the size of the triangular set.
281  *
282  * @param
283  **/
284  inline int size() const {
285  return algVars.size();
286  }
287
288  /**
289  * Get the number of algebraic variables.
290  *
291  * @param
292  **/
293  inline int numberOfAlgebraicVariables() const {
294  return algVars.size();
295  }
296
297  /**
298  * Get the number of transcendental variables.
299  *
300  * @param
301  **/
302  inline int numberOfTranscendentalVariables() const {
303  return trcVars.size();
304  }
305
306  /**
307  * Get the variable names in decreasing order.
308  *
309  * @param
310  **/
311  inline std::vector<Symbol> variables() const {
312  return vars;
313  }
314
315  /**
316  * Get the algebraic variables.
317  *
318  * @param
319  **/
320  inline std::vector<Symbol> mainVariables() const {
321  return algVars;
322  }
323
324  /**
325  * Get the transcendentalVariables variables.
326  *
327  * @param
328  **/
329  inline std::vector<Symbol> transcendentalVariables() const {
330  return trcVars;
331  }
332
333  /**
334  * Get the list of variables followed by the transcendental variables.
335  *
336  * @param
337  **/
338  std::vector<Symbol> allVariables() const;
339
340
341  /**
342  * Determine if the input variable s is algebraic, i.e., if the triangular set
343  * contains a polynomial with s its as leading variable.
344  *
345  * @param s: the input variable
346  **/
347  inline bool isAlgebraic(const Symbol& s) const {
348  if (std::find(algVars.begin(),algVars.end(),s) != algVars.end())
349  return true;
350  else
351  return false;
352  }
353
354  /**
355  * Return true if the triangular set is strongly normalized, i.e., the initals of all polynomials
356  * are in the Field; return false otherwise.
357  *
358  * @param
359  **/
360  inline bool isStronglyNormalized() const {
361  return stronglyNormalized;
362  }
363
364  /**
365  * Get the vector of polynoials in the triangular set.
366  *
367  * @param
368  **/
369  inline std::vector<RecursivePoly> polynomials() const {
370  return set;
371  }
372
373  /**
374  * Return the dimension of the triangular set (understood in terms of the space of (potentially algebraic) variables).
375  *
376  * @param
377  **/
378  inline int dimension() const {
379  return (vars.size() - algVars.size());
380  }
381
382  /**
383  * Return the dimension of the triangular set lower(v) (understood in terms of the space of (potentially algebraic) variables).
384  *
385  * @param
386  **/
387  inline int dimensionLower(Symbol v) const {
388  if (!isAMemberOf(v,vars)) {
389  return 0;
390  }
392  varsSize = vars.size() - 1 - varsSize;
393  for (int i=0; i<algVars.size(); ++i) {
394  if (variableIndex(algVars[i])>vi)
396  }
398  }
399
400  /**
401  * Return the codimension of the triangular set (understood in terms of the space of (potentially algebraic) variables).
402  *
403  * @param
404  **/
405  inline int codimension() const {
406  return algVars.size();
407  }
408
409  /**
410  * Test to determine whether the triangular set can be treated as zero dimensional, i.e., whether the triangular set
411  * becomes zero dimensional when all non-algebraic variables are removed and whether the polynomial p contains only
412  * algebraic variables.
413  *
414  * @param p: a recursively viewed polynomial
415  * @param p: (optional) flag to exclude the main variable of p when determining whether it contains only algebraic variables (default false)
416  **/
417  bool canComputeInDimensionZero(const RecursivePoly& p, bool excludeMainVariable = false) const;
418
419  /**
420  * Test to determine if only algebraic variables (aside from transcendentals) appear in the polynomials of the triangular set.
421  *
422  * @param
423  **/
424  bool isZeroDimensionalMathematically() const;
425
426  /**
427  * Select a polynomial given the leading variable;
428  * if no such polynomial, 0 is returned.
429  *
430  * @param x: The leading variable name
431  **/
432  RecursivePoly select(const Symbol& s) const;
433
434  /**
435  * Replace each polynomial of the triangular set with its primitive part.
436  *
437  * @param
438  **/
439  void makePrimitive();
440
441  /**
442  * Returns the triangular set consisting of polynomials with
443  * main variable strictly less than s.
444  *
445  * @param s: symbol of the main variable of specified element of the triangular set
446  * @param ts: The returned triangular set
447  **/
448  void lower(const Symbol& s, BPASTriangularSet<Field,RecursivePoly>& ts) const;
449
450  /**
451  * Returns the triangular set consisting of polynomials with
452  * main variable strictly greater than s.
453  *
454  * @param s: symbol of the main variable of specified element of the triangular set
455  * @param ts: The returned triangular set
456  **/
457  void upper(const Symbol& s, BPASTriangularSet<Field,RecursivePoly>& ts) const;
458
459  /**
460  * Pseudo division: return the pseudo-remainder, the pseudo-quotients and
461  * c such that c*p = ∑(q_i T_i) + r.
462  *
463  * @param p: an input recursively viewed polynomial
464  * @param quo: (optional) the array of quotients
465  * @param c: (optional) the constant multiplied to the input polynomial
466  **/
467  RecursivePoly pseudoDivide (const RecursivePoly& p, std::vector<RecursivePoly>* quo=NULL, RecursivePoly* c=NULL) const;
468
469  /**
470  * Return the normalForm of the input polynomial modulo the triangular set in the sense of Groebner basis
471  *
472  * @param p: innput recursively viewed polynomial
473  * @param Q: (optional) the array of quotient
474  **/
475  RecursivePoly normalForm(const RecursivePoly& p, std::vector<RecursivePoly>* Q=NULL) const;
476
477  /**
478  * Reduce the input polynomial modulo the triangular set.
479  *
480  * @param p: input recursively viewed polynomial
481  **/
482  RecursivePoly reduce(const RecursivePoly& p) const;
483
484  /**
485  * returns r such that c*r = p modulo sat(T) such that
486  * c has no algebraic variables, and c is returned as an input parameter.
487  *
488  * @param p: input recursively viewed polynomial
489  * @param c: returned value of the content of p modulo sat(T)
490  * @param usePrimitiveFactorization: (optional) whether to use primitive factorization to compute c (default true)
491  * @param onlyInDimZero: (optional) only perform the reduction if the canComputeInDimensionZero(p) is true (default false)
492  **/
493  RecursivePoly reduce(const RecursivePoly& p, RecursivePoly& c, bool usePrimitiveFactorization = true, bool onlyInDimZero = false) const;
494
495  /**
496  * Generate a random triangular set polynomial based on its number of terms.
497  *
498  * @param variables: variables of the triangular set
499  * @param algVar: index of the algebraic variable
500  * @param transcendentalVariables: transcendental variables of the triangular set
501  * @param nTerms: number of terms in the polynomial
502  * @param coefBound: maximum size of the coefficients
503  * @param pSparsity: sparsity of the polynomial
504  * @param includeNeg: whether to include negative coefficients
505  **/
506  RecursivePoly randomTriangularSetPolynomial(std::vector<Symbol> variables, int algVar, std::vector<Symbol> transcendentalVariables, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg);
507
508  /**
509  * Generate a random triangular set polynomial based on its maximum degrees in its variables.
510  *
511  * @param variables: variables of the triangular set
512  * @param algVar: index of the algebraic variable
513  * @param transcendentalVariables: transcendental variables of the triangular set
514  * @param maxDegs: vector of maximum degrees among the set of variables
515  * @param coefBound: maximum size of the coefficients
516  * @param pSparsity: proportional sparsity of the polynomial
517  * @param includeNeg: whether to include negative coefficients
518  **/
519  RecursivePoly randomTriangularSetPolynomial(std::vector<Symbol> variables, int algVar, std::vector<Symbol> transcendentalVariables, std::vector<int> maxDegs, unsigned long int coefBound, double pSparsity, bool includeNeg);
520
521  /**
522  * Generate a random triangular set based on the number of terms of its polynomials.
523  *
524  * @param nVars: number of variables
525  * @param nAlgVars: number of algebraic variables
526  * @param nTrcVars: number of transcendental variables
527  * @param nTerms: number of terms in the polynomial
528  * @param coefBound: maximum size of the coefficients
529  * @param pSparsity: sparsity of the polynomial
530  * @param includeNeg: whether to include negative coefficients
531  **/
532  void randomTriangularSet(int nVars, int nAlgVars, int nTrcVars, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg);
533
534  /**
535  * Generate a random strongly normalized triangular set based on the number of terms in its polynomials.
536  *
537  * @param nVars: number of variables
538  * @param nAlgVars: number of algebraic variables
539  * @param nTrcVars: number of transcendental variables
540  * @param nTerms: number of terms in the polynomial
541  * @param coefBound: maximum size of the coefficients
542  * @param pSparsity: sparsity of the polynomial
543  * @param includeNeg: whether to include negative coefficients
544  **/
545  void randomStronglyNormalizedTriangularSet(int nVars, int nAlgVars, int nTrcVars, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg);
546
547  /**
548  * Display the triangular set.
549  *
550  * @param
551  **/
552  void display();
553
554  /**
555  * Overload stream operator << for triangular sets.
556  *
557  * @param out: Stream object
558  * @param a: A triangular set
559  **/
560  inline friend std::ostream& operator<< (std::ostream& out, TriangularSet<Field,RecursivePoly>& a) {
561  bool isNotFirst = 0;
562  out << "[";
563  for (int i = 0; i < a.set.size(); ++i) {
564  if (!a.set[i].isZero()) {
565  if (isNotFirst) { out << ", "; }
566  out << a.set[i];
567  isNotFirst = 1;
568  }
569  }
570  out << "]";
571  return out;
572  }
573
574  /**
575  * Convert a triangular set to an expression tree (array of its polynomials).
576  *
577  * @param
578  **/
580  if (!set.size()) {
581  ExprTreeNode* node = new ExprTreeNode(EXPR_ARRAY, NULL, NULL, NULL);
582  return ExpressionTree(node);
583  }
584  else {
585  std::vector<RecursivePoly> tsp;
586  for (int i=0; i<set.size(); ++i) {
587  if (!set[i].isZero())
588  tsp.push_back(set[i]);
589  }
590  ExpressionTree t;
591  t.fromVector<RecursivePoly>(tsp);
592  return(t);
593  }
594  }
595 };
596
597 #endif
A triangular set templated by a multivariate polynomial over a field.
Definition: triangularset.hpp:42
bool isEmpty() const
Copy an object derived from abstract BPASTriangularSet class to type of current object.
std::vector< Symbol > variables() const
Get the variable names in decreasing order.
Definition: triangularset.hpp:311
bool canComputeInDimensionZero(const RecursivePoly &p, bool excludeMainVariable=false) const
Test to determine whether the triangular set can be treated as zero dimensional, i.e., whether the triangular set becomes zero dimensional when all non-algebraic variables are removed and whether the polynomial p contains only algebraic variables.
std::vector< RecursivePoly > polynomials() const
Get the vector of polynoials in the triangular set.
Definition: triangularset.hpp:369
ExpressionTree convertToExpressionTree() const
Convert a triangular set to an expression tree (array of its polynomials).
Definition: triangularset.hpp:579
void display()
Display the triangular set.
TriangularSet< Field, RecursivePoly > & operator+=(const RecursivePoly &p)
Add assignment operator +=.
std::vector< Symbol > allVariables() const
Get the list of variables followed by the transcendental variables.
int codimension() const
Return the codimension of the triangular set (understood in terms of the space of (potentially algebr...
Definition: triangularset.hpp:405
int numberOfVariables() const
Get the number of variables.
Definition: triangularset.hpp:275
void upper(const Symbol &s, BPASTriangularSet< Field, RecursivePoly > &ts) const
Returns the triangular set consisting of polynomials with main variable strictly greater than s...
int dimension() const
Return the dimension of the triangular set (understood in terms of the space of (potentially algebrai...
Definition: triangularset.hpp:378
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
TriangularSet< Field, RecursivePoly > & operator=(const TriangularSet< Field, RecursivePoly > &a)
Assignment operator =.
int numberOfTranscendentalVariables() const
Get the number of transcendental variables.
Definition: triangularset.hpp:302
bool isStronglyNormalized() const
Return true if the triangular set is strongly normalized, i.e., the initals of all polynomials are in...
Definition: triangularset.hpp:360
TriangularSet< Field, RecursivePoly > operator+(const RecursivePoly &p)
void makePrimitive()
Replace each polynomial of the triangular set with its primitive part.
RecursivePoly reduce(const RecursivePoly &p) const
Reduce the input polynomial modulo the triangular set.
RecursivePoly randomTriangularSetPolynomial(std::vector< Symbol > variables, int algVar, std::vector< Symbol > transcendentalVariables, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg)
Generate a random triangular set polynomial based on its number of terms.
RecursivePoly select(const Symbol &s) const
Select a polynomial given the leading variable; if no such polynomial, 0 is returned.
bool operator==(TriangularSet< Field, RecursivePoly > &a)
Identity operator ==.
int dimensionLower(Symbol v) const
Return the dimension of the triangular set lower(v) (understood in terms of the space of (potentially...
Definition: triangularset.hpp:387
bool isAlgebraic(const Symbol &s) const
Determine if the input variable s is algebraic, i.e., if the triangular set contains a polynomial wit...
Definition: triangularset.hpp:347
void lower(const Symbol &s, BPASTriangularSet< Field, RecursivePoly > &ts) const
Returns the triangular set consisting of polynomials with main variable strictly less than s...
bool isZeroDimensionalMathematically() const
Test to determine if only algebraic variables (aside from transcendentals) appear in the polynomials ...
RecursivePoly pseudoDivide(const RecursivePoly &p, std::vector< RecursivePoly > *quo=NULL, RecursivePoly *c=NULL) const
Pseudo division: return the pseudo-remainder, the pseudo-quotients and c such that c*p = ∑(q_i T_i) ...
void randomTriangularSet(int nVars, int nAlgVars, int nTrcVars, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg)
Generate a random triangular set based on the number of terms of its polynomials. ...
void fromVector(const std::vector< ExpTreeConvert > &ringVec)
Fill this expression tree with the vector of BPASRing elements specified.
Definition: ExpressionTree.hpp:180
int numberOfAlgebraicVariables() const
Get the number of algebraic variables.
Definition: triangularset.hpp:293
An abstract class defining the interface of a triangular set.
Definition: polynomial.h:196
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
void randomStronglyNormalizedTriangularSet(int nVars, int nAlgVars, int nTrcVars, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg)
Generate a random strongly normalized triangular set based on the number of terms in its polynomials...
bool isConstantPolynomial(const RecursivePoly &p) const
Tests if the polynomial is constant relative to the TriangularSet, i.e., whether it is and element of...
RecursivePoly normalForm(const RecursivePoly &p, std::vector< RecursivePoly > *Q=NULL) const
Return the normalForm of the input polynomial modulo the triangular set in the sense of Groebner basi...
bool operator!=(TriangularSet< Field, RecursivePoly > &a)
Negated identity operator !=.
ExprTreeNode is a single node in the bianry tree of an ExpressionTree.
Definition: ExprTreeNode.hpp:76
std::vector< Symbol > transcendentalVariables() const
Get the transcendentalVariables variables.
Definition: triangularset.hpp:329
int size() const
Get the size of the triangular set.
Definition: triangularset.hpp:284
std::vector< Symbol > mainVariables() const
Get the algebraic variables.
Definition: triangularset.hpp:320