Basic Polynomial Algebra Subprograms (BPAS)  v. 1.652
zerodimensionalregularchain.hpp
1 #ifndef _ZERODIMENSIONALREGULARCHAIN_H_
2 #define _ZERODIMENSIONALREGULARCHAIN_H_
3
4
5 #include "../polynomial.h"
6 #include "../Ring/BPASField.hpp"
7 #include "regularchain.hpp"
8 #include "chainstructures.hpp"
9 #include "../TriangularSet/triangularset.hpp"
10 #include "../SubResultantChain/subresultantchain.hpp"
11
12 extern long long unsigned int rcProfilingStart;
13 extern float primitivePartTime;
14 extern float squareFreePartTime;
15 extern float subresultantChainTime;
16 extern float zerodimensionalregularchainTime;
17 extern float pseudoDivideTime;
18 extern float normalFormTime;
19
20 /**
21  * A class for handling regular chains in dimension zero.
22  * A ZeroDimensionalRegularChain contains polynomials of type BPASRecursivelyViewedPolynomial, which have coefficients in a BPASField.
23  **/
24 template <class Field, class RecursivePoly>
25 class ZeroDimensionalRegularChain : public RegularChain<Field,RecursivePoly>,
26  public virtual BPASZeroDimensionalRegularChain<Field,RecursivePoly>
27 {
28  protected:
29
38
41
42  /**
43  * Cut an input zero-dimensional regular chain at the symbol v, returning the zero-dimensional subchain below v,
44  * the polynomial with main variable v and the potentially positive-dimensional subchain above v.
45  *
46  * @param T: a regular chain
47  * @param v: a symbol
48  * @param Tlv: the zero-dimensional subchain of T below v
49  * @param Tv: the recursively viewed polynomial with main variable v, if it exists
50  * @param Tgv: the (potentially positive-dimensional) subchain of T above v
51  **/
53
54  /**
55  * Cut the current object at the symbol v, returning the polynomial with main variable v and the subchain above v, which may no longer be zero-dimensional.
56  *
57  * @param v: a symbol
58  * @param Tv: the recursively viewed polynomial with main variable v, if it exists
59  * @param Tgv: the regular chain obtained from the polynomials of the current object above v
60  **/
61  void cutRegularChain(const Symbol& v, RecursivePoly& Tv, RegularChain<Field,RecursivePoly>& Tgv) const;
62
63  /**
64  * Cut the current object at the symbol v, returning the zero-dimensional subchain below v and the polynomial with main variable v.
65  *
66  * @param v: a symbol
67  * @param Tlv: the zero-dimensional subchain of the current object below v
68  * @param Tv: the recursively viewed polynomial with main variable v, if it exists
69  **/
70  void cutRegularChain(const Symbol& v, ZeroDimensionalRegularChain<Field,RecursivePoly>& Tlv, RecursivePoly& Tv) const;
71
72  /**
73  * Add an input polynomial to the current object
74  *
75  * @param p: a recursively viewed polynomial
76  **/
77  void constructChain(const RecursivePoly& p, int options=ASSUME_REGULAR);
78
79  /**
80  * Add an an upper regular chain to the current object
81  *
82  * @param T: a recursively viewed polynomial
83  **/
84  void constructChain(const RegularChain<Field,RecursivePoly>& T, int options=ASSUME_REGULAR);
85
86  /**
87  * Construct a set of regular chains from the current object and an input polynomial
88  *
89  * @param p: a recursively viewed polynomial
90  **/
91  std::vector<ZeroDimensionalRegularChain<Field,RecursivePoly>> constructChains(const RecursivePoly& p, int options=ASSUME_REGULAR) const;
92
93  /**
94  * Construct a set of regular chains from the current object and an input polynomial
95  *
96  * @param p: a recursively viewed polynomial
97  **/
98  std::vector<ZeroDimensionalRegularChain<Field,RecursivePoly>> constructChains(const RegularChain<Field,RecursivePoly>& T, int options=ASSUME_REGULAR) const;
99
100  /**
101  * Compute the last nonzero subresultant of the subresultant chain src of f and g modulo the current regular chain,
102  * i.e., compute a splitting of pairs (R_i,T_i) such that R_i is the last nonzero subresultant modulo T_i.
103  *
104  * @param f: input polynomial
105  * @param g: input polynomial
106  * @param v: common main variable of f and g
107  * @param isGCD: boolean flag specifying whether the function is called for GCD computation
108  **/
109  std::vector<PolyChainPair<RecursivePoly,ZeroDimensionalRegularChain<Field,RecursivePoly>>> lastNonZeroSubResultant(const RecursivePoly& f, const RecursivePoly& g, const Symbol& v, bool isGCD) const;
110
111  /**
112  * Compute the last nonzero subresultant of the subresultant chain src of f and g modulo the current regular chain,
113  * i.e., compute a splitting of pairs (R_i,T_i) such that R_i is the last nonzero subresultant modulo T_i.
114  *
115  * @param f: input polynomial
116  * @param g: input polynomial
117  * @param v: common main variable of f and g
118  * @param src: subresultant chain of f and g
119  * @param isGCD: boolean flag specifying whether the function is called for GCD computation
120  **/
121  std::vector<PolyChainPair<RecursivePoly,ZeroDimensionalRegularChain<Field,RecursivePoly>>> lastNonZeroSubResultant_inner(const RecursivePoly& f, const RecursivePoly& g, const Symbol& v, const SubResultantChain<RecursivePoly,RecursivePoly>& src, bool isGCD) const;
122
123  public:
124
126
127  /**
128  * Default constructor: creates an empty zero-dimensional regular chain with variable size
129  * with empty list of transcendentals.
130  *
131  * @param
132  **/
134
135  /**
136  * Construct an empty zero-dimensional regular chain of variable size with
137  * variables given by xs with empty list of transcendentals.
138  *
139  * @param ps: the transcendental variable names
140  **/
141  ZeroDimensionalRegularChain<Field,RecursivePoly> (const std::vector<Symbol>& ps);
142
143  /**
144  * Construct a zero-dimensional regular chain of variable size containing a univariate polynomial p
145  * with empty list of transcendentals.
146  *
147  * @param p: a recursively viewed polynomial with only one variable
148  **/
149  ZeroDimensionalRegularChain<Field,RecursivePoly> (const RecursivePoly& p);
150
151  /**
152  * Construct a variable zero-dimensional regular chain containing p, such that the supplied list of transcendental variable names
153  * includes all of the variables in p except its main variable, which becomes the only algebraic variable of the chain.
154  *
155  * @param p: a recursively viewed polynomial
156  * @param ts: the transcendental variable names
157  **/
158  ZeroDimensionalRegularChain<Field,RecursivePoly> (const RecursivePoly& p, const std::vector<Symbol>& ts);
159
160  /**
161  * Copy constructor.
162  *
163  * @param a: a zero-dimensional regular chain
164  **/
166
167  /**
168  * Copy constructor taking a regular chain as input. Note that this routine allow the construction of fixed zero-dimensional regular
169  * chains that are technically positive-dimensional because the polynomials above the maximum algebraic variable are zero.
170  * This is allowed to optimize the performance of routines in the RegularChain class.
171  *
172  * @param a: a regular chain
173  **/
175
176  /**
177  * Move constructor.
178  *
179  * @param a: an r-value reference zero-dimensional regular chain
180  **/
182
183  /**
184  * Move constructor taking a regular chain as input. Note that this routine allow the construction of fixed zero-dimensional regular
185  * chains that are technically positive-dimensional because the polynomials above the maximum algebraic variable are zero.
186  * This is allowed to optimize the performance of routines in the RegularChain class.
187  *
188  * @param a: an r-value reference regular chain
189  **/
191
192  /**
193  * Computational constructor: creates a triangular set given all the data
194  *
195  * @param vs: variables of the zero-dimensional regular chain
196  * @param avs: algebraic variables of the zero-dimensional regular chain
197  * @param tvs: transcendental variables of the zero-dimensional regular chain
198  * @param polys: polynomials of the zero-dimensional regular chain
199  * @param tsm: whether the zero-dimensional regular chain is variable or fixed
200  * @param c: characteristic of the zero-dimensional regular chain
201  **/
202  ZeroDimensionalRegularChain<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);
203
204  /**
205  * Assignment operator =.
206  *
207  * @param a: a triangular set
208  **/
210
211  /**
212  * Assignment operator = imposed by abstract class BPASTriangularSet.
213  *
214  * @param a: a triangular set
215  **/
217
218  /**
219  * Assignment operator = imposed by abstract class BPASRegularChain.
220  *
221  * @param a: a regular chain
222  **/
224
225  /**
226  * Assignment operator = imposed by abstract class BPASZeroDimensionalRegularChain.
227  *
228  * @param a: a zero-dimensional regular chain
229  **/
231
232  /**
233  * Move assignment operator = imposed by class ZeroDimensionalRegularChain.
234  *
235  * @param a: a zero-dimensional regular chain
236  **/
238
239  /**
240  * Move assignment operator = imposed by abstract class BPASTriangularSet.
241  *
242  * @param a: a triangular set
243  **/
245
246  /**
247  * Move assignment operator =
248  *
249  * @param a: a BPASRegularChain
250  **/
252
253  /**
254  * Move assignment operator = imposed by abstract class BPASZeroDimensionalRegularChain.
255  *
256  * @param a: a zero-dimensional regular chain
257  **/
259
260  /**
261  * Add operator +:
262  * Adds a polynomial p to a zero-dimensional regular chain and returns a new zero-dimensional regular chain,
263  * assuming that the main variable of p is neither algebraic nor transcendental, p contains no other non-transcendental
264  * variables, and that init(p) is regular modulo the saturated ideal of the current object.
265  *
266  * @param p: a recursively viewed polynomial
267  **/
268  ZeroDimensionalRegularChain<Field,RecursivePoly> operator+ (const RecursivePoly& p) const;
269
270  /**
271  * Add assignment operator +=:
272  * Adds a polynomial p to a zero-dimensional regular chain, assuming that the main variable of p
273  * is neither algebraic nor transcendental, p contains no other non-transcendental
274  * variables, and that init(p) is regular modulo the saturated ideal of the current object.
275  *
276  * @param p: a recursively viewed polynomial
277  **/
279
280  /**
281  * Add operator +:
282  * Adds the polynomials of an input regular chain to the current object and returns a new zero-dimensional
283  * regular chain, assuming that the result of the addition is both a regular chain and zero-dimensional.
284  *
285  * @param p: a regular chain
286  **/
288
289  /**
290  * Add assignment operator +=:
291  * Adds the polynomials of an input regular chain to the current object, assuming that the result of
292  * the addition is both a regular chain and zero-dimensional.
293  *
294  * @param p: a recursively viewed polynomial
295  **/
297
298  /**
299  * Identity operator ==.
300  *
301  *
302  * @param a: A triangular set
303  **/
305
306  /**
307  * Negated identity operator !=.
308  *
309  *
310  * @param a: A triangular set
311  **/
313
314  /**
315  * Get the number of (potentially algebraic) variables. This can only be different than the number
316  * of algebraic variables for fixed zero-dimensional regular chains.
317  *
318  * @param
319  **/
320  inline int numberOfVariables() const {
322  }
323
324  /**
325  * Get the number of algebraic variables in the current object.
326  *
327  * @param
328  **/
329  inline int numberOfAlgebraicVariables() const {
331  }
332
333  /**
334  * Get the number of transcendental variables in the current object.
335  *
336  * @param
337  **/
338  inline int numberOfTranscendentalVariables() const {
340  }
341
342  /**
343  * Get the (potentially algebraic) variable names for the current object in decreasing order.
344  * This can only be different from the list of algebraic variable names for fixed zero-dimensional
345  * regular chains.
346  *
347  * @param
348  **/
349  inline std::vector<Symbol> variables() const {
351  }
352
353  /**
354  * Get algebraic variables in the current object.
355  *
356  * @param
357  **/
358  inline std::vector<Symbol> mainVariables() const {
360  }
361
362  /**
363  * Get transcendental variables in the current object.
364  *
365  * @param
366  **/
367  inline std::vector<Symbol> transcendentalVariables() const {
369  }
370
371  /**
372  * Find out if the input symbol is an algebraic variable of the current object.
373  *
374  * @param s: a symbol
375  **/
376  inline bool isAlgebraic(const Symbol& s) const {
378  }
379
380  /**
381  * Find out if the current object is the empty chain.
382  *
383  * @param
384  **/
385  inline bool isEmpty() const {
387  }
388
389  /**
390  * Get the list of polynomials in the current object.
391  *
392  * @param
393  **/
394  inline std::vector<RecursivePoly> polynomials() const {
396  }
397
398  /**
399  * Select the polynomial in the current object with main variable s, if it exists.
400  *
401  * @param s: a symbol
402  **/
403  inline RecursivePoly select(const Symbol& s) const {
405  }
406
407  /**
408  * Returns the zero-dimensional regular chain consisting of polynomials with
409  * main variable strictly less than s. NB: the type of the returned object is always
410  * a ZeroDimensionalRegularChain, since the lower chain is always genuinely zero-dimensional;
411  * however, if the current object is a variable zero-dimensional regular chain, the returned
412  * object really is zero-dimensional, in the sense that all variables are algebraic, but if
413  * the current object is a fixed type, then the chain may only be morally zero-dimensional
414  * in the sense that all variables below some variable are algebraic but the chain has
415  * non-algebraic variables.
416  *
417  * @param s: symbol of the main variable of specified element of the regular chain
418  * @param ts: The returned regular chain
419  **/
420  void lower(const Symbol& s, BPASTriangularSet<Field,RecursivePoly>& ts) const;
421
422  /**
423  * Returns the regular chain consisting of polynomials with
424  * main variable strictly greater than s. The type of the returned object is always
425  * a RegularChain, since the upper chain can be genuinely positive dimensional.
426  *
427  * @param s: symbol of the main variable of specified element of the regular chain
428  * @param ts: The returned regular chain
429  **/
430  void upper(const Symbol& s, BPASTriangularSet<Field,RecursivePoly>& ts) const;
431
432  /**
433  * Compute the common solutions of the input polynomial and the current regular chain.
434  * More precisely, this routine computes the intersection of the varieties of the input polynomial and the
435  * current zero-dimensional regular chain, expressed as a set of zero-dimensional regular chains.
436  *
437  * @param p: a recursively viewed polynomial
438  **/
439  std::vector<ZeroDimensionalRegularChain<Field,RecursivePoly>> intersect(const RecursivePoly& p) const;
440
441  /**
442  * Compute a decomposition of the current object such that on each component the input polynomial is either
443  * zero or regular modulo the saturated ideal of that component. If the polynomial is zero, (0, T_i) is returned;
444  * if the polynomial is regular, (p_i, T_i), is returned, where p_i is equivalent to p modulo the saturated ideal of T_i.
445  *
446  * @param p: a recursively viewed polynomial
447  **/
448  std::vector<PolyChainPair<RecursivePoly,ZeroDimensionalRegularChain<Field,RecursivePoly>>> regularize(const RecursivePoly& p) const;
449
450  /**
451  * Compute a decomposition of the current object such that on each component the initial of the input polynomial is either
452  * zero or regular modulo the saturated ideal of that component. If the initial is zero, (0, T_i) is returned;
453  * if the initial is regular, (p_i, T_i), is returned, where p_i is equivalent to p modulo the saturated ideal of T_i.
454  *
455  * @param p: a recursively viewed polynomial
456  **/
457  std::vector<PolyChainPair<RecursivePoly,ZeroDimensionalRegularChain<Field,RecursivePoly>>> regularizeInitial(const RecursivePoly& p) const;
458
459  /**
460  * Determine whether a recursively viewed polynomial is invertible with respect to the current regular chain.
461  * More precisely, compute a splitting consisting of pairs (b_i,T_i) such that b_i is true if f is invertible
462  * modulo T_i and b_i is false if f is zero modulo T_i.
463  *
464  * @param p: a recursively viewed polynomial
465  **/
466  std::vector<BoolChainPair<ZeroDimensionalRegularChain<Field,RecursivePoly>>> isInvertible(const RecursivePoly& p) const;
467
468  /**
469  * Compute the gcd of two input polynomials p and q modulo the saturated ideal of the current object. The result is a list of pairs (g_i,T_i) of
470  * polynomials g_i and regular chains T_i, where g_i is gcd(p,q) modulo the saturated ideal of T_i.
471  *
472  * @param p: a recursively viewed polynomial
473  * @param q: a recursively viewed polynomial
474  * @param v: common main variable of f and g
475  **/
476  std::vector<PolyChainPair<RecursivePoly,ZeroDimensionalRegularChain<Field,RecursivePoly>>> regularGCD(const RecursivePoly& p, const RecursivePoly& q, const Symbol& v);
477
478  /**
479  * Generate a random zero-dimensional regular chain based on the number of terms of the polynomials of the chain.
480  *
481  * @param nVars: number of variables = number of algebraic variables
482  * @param nTrcVars: number of transcendental variables
483  * @param nTerms: maximum number of terms in the polynomials
484  * @param coefBound: maximum coefficient size
485  * @param pSparsity: sparsity of the polynomials
486  * @param includeNeg: whether to include negative coefficients
487  **/
488  void randomZeroDimensionalRegularChain(int nVars, int nTrcVars, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg);
489
490  /**
491  * Generate a random zero-dimensional regular chain based on a list of maximum degrees of variables in the polynomials in the chain.
492  *
493  * @param nVars: number of variables = number of algebraic variables
494  * @param nTrcVars: number of transcendental variables
495  * @param maxDegs: maximum degrees among the full list of variables
496  * @param coefBound: maximum coefficient size
497  * @param pSparsity: sparsity of the polynomials
498  * @param includeNeg: whether to include negative coefficients
499  **/
500  void randomZeroDimensionalRegularChain(int nVars, int nTrcVars, std::vector<int> maxDegs, unsigned long int coefBound, double pSparsity, bool includeNeg);
501
502 };
503
504 #endif
ZeroDimensionalRegularChain< Field, RecursivePoly > & operator+=(const RecursivePoly &p)
Add assignment operator +=: Adds a polynomial p to a zero-dimensional regular chain, assuming that the main variable of p is neither algebraic nor transcendental, p contains no other non-transcendental variables, and that init(p) is regular modulo the saturated ideal of the current object.
bool isEmpty() const
Copy an object derived from abstract BPASTriangularSet class to type of current object.
std::vector< RecursivePoly > polynomials() const
Get the vector of polynoials in the triangular set.
Definition: triangularset.hpp:369
bool operator!=(ZeroDimensionalRegularChain< Field, RecursivePoly > &a)
Negated identity operator !=.
std::vector< Symbol > mainVariables() const
Get algebraic variables in the current object.
Definition: zerodimensionalregularchain.hpp:358
An abstract class defining the interface of a zero-dimensional regular chain.
Definition: polynomial.h:233
void lower(const Symbol &s, BPASTriangularSet< Field, RecursivePoly > &ts) const
Returns the zero-dimensional regular chain consisting of polynomials with main variable strictly less...
bool isEmpty() const
Find out if the current object is the empty chain.
Definition: zerodimensionalregularchain.hpp:385
std::vector< Symbol > transcendentalVariables() const
Get transcendental variables in the current object.
Definition: zerodimensionalregularchain.hpp:367
ZeroDimensionalRegularChain< Field, RecursivePoly > & operator=(const ZeroDimensionalRegularChain< Field, RecursivePoly > &a)
Assignment operator =.
A class for handling regular chains in dimension zero.
Definition: regularchain.hpp:10
int numberOfTranscendentalVariables() const
Get the number of transcendental variables.
Definition: triangularset.hpp:302
std::vector< Symbol > variables() const
Get the (potentially algebraic) variable names for the current object in decreasing order...
Definition: zerodimensionalregularchain.hpp:349
int numberOfTranscendentalVariables() const
Get the number of transcendental variables in the current object.
Definition: zerodimensionalregularchain.hpp:338
RecursivePoly select(const Symbol &s) const
Select the polynomial in the current object with main variable s, if it exists.
Definition: regularchain.hpp:585
bool operator==(ZeroDimensionalRegularChain< Field, RecursivePoly > &a)
Identity operator ==.
int numberOfVariables() const
Get the number of (potentially algebraic) variables.
Definition: zerodimensionalregularchain.hpp:320
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
bool isAlgebraic(const Symbol &s) const
Find out if the input symbol is an algebraic variable of the current object.
Definition: zerodimensionalregularchain.hpp:376
std::vector< PolyChainPair< RecursivePoly, ZeroDimensionalRegularChain< Field, RecursivePoly > > > regularize(const RecursivePoly &p) const
Compute a decomposition of the current object such that on each component the input polynomial is eit...
std::vector< RecursivePoly > polynomials() const
Get the list of polynomials in the current object.
Definition: zerodimensionalregularchain.hpp:394
void upper(const Symbol &s, BPASTriangularSet< Field, RecursivePoly > &ts) const
Returns the regular chain consisting of polynomials with main variable strictly greater than s...
std::vector< ZeroDimensionalRegularChain< Field, RecursivePoly > > intersect(const RecursivePoly &p) const
Compute the common solutions of the input polynomial and the current regular chain.
std::vector< Symbol > variables() const
Get the (potentially algebriac) variable names in decreasing order.
Definition: regularchain.hpp:576
std::vector< BoolChainPair< ZeroDimensionalRegularChain< Field, RecursivePoly > > > isInvertible(const RecursivePoly &p) const
Determine whether a recursively viewed polynomial is invertible with respect to the current regular c...
int numberOfAlgebraicVariables() const
Get the number of algebraic variables in the current object.
Definition: zerodimensionalregularchain.hpp:329
std::vector< PolyChainPair< RecursivePoly, ZeroDimensionalRegularChain< Field, RecursivePoly > > > regularGCD(const RecursivePoly &p, const RecursivePoly &q, const Symbol &v)
Compute the gcd of two input polynomials p and q modulo the saturated ideal of the current object...
int options() const
Get the encoded options of the regular chain, a bitwise or of RegularChainOption values.
int numberOfAlgebraicVariables() const
Get the number of algebraic variables.
Definition: triangularset.hpp:293
ZeroDimensionalRegularChain< Field, RecursivePoly > operator+(const RecursivePoly &p) const
Add operator +: Adds a polynomial p to a zero-dimensional regular chain and returns a new zero-dimens...
A class for handling regular chains of arbitrary dimension.
Definition: regularchain.hpp:33
int numberOfVariables() const
Get the number of (potentially algebraic) variables in the current object.
Definition: regularchain.hpp:491
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
void randomZeroDimensionalRegularChain(int nVars, int nTrcVars, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg)
Generate a random zero-dimensional regular chain based on the number of terms of the polynomials of t...
std::vector< PolyChainPair< RecursivePoly, ZeroDimensionalRegularChain< Field, RecursivePoly > > > regularizeInitial(const RecursivePoly &p) const
Compute a decomposition of the current object such that on each component the initial of the input po...
std::vector< Symbol > transcendentalVariables() const
Get the transcendentalVariables variables.
Definition: triangularset.hpp:329
RecursivePoly select(const Symbol &s) const
Select the polynomial in the current object with main variable s, if it exists.
Definition: zerodimensionalregularchain.hpp:403
std::vector< Symbol > mainVariables() const
Get the algebraic variables.
Definition: triangularset.hpp:320