 Basic Polynomial Algebra Subprograms (BPAS)  v. 1.652
mzpolynomial.hpp
1 #ifndef _SMZPALTARRAY_H_
2 #define _SMZPALTARRAY_H_
3
4 #include "../Ring/Integer.hpp"
5 #include "../polynomial.h"
6 #include "uzpolynomial.h"
7 #include "../RingPolynomial/upolynomial.h"
8 #include "../RationalNumberPolynomial/mrpolynomial.h"
9 #include "SMZP_CppSupport.hpp"
10 #include "SMZP_Support.h"
11 #include "SMZP_Support_Test.h"
12 #include "SMZP_Support_Recursive.h"
13 #include <gmpxx.h>
14 #include "../ExpressionTree/ExpressionTree.hpp"
15 #include "../DataStructures/Factors.hpp"
16
19 #endif
20
22
23 /**
24  * An element of the SLP of an integer polynomial.
25  */
27
28  public:
29  union CoefOrInt {
30  Integer* c;
31  int i;
32  };
33
34  int op; // 0: '+'; 1: '*'.
35  int type; // 0: coef & variate;
36  // 1: coef & result;
37  // 2: variate & result;
38  // 3: result & result;
39  // 4: coef (constant);
40  CoefOrInt a; // variate or result or coef position
41  int b; // variate or result or coef position
42  Interval res; // Storing the result
43
45  a.c = NULL;
46  }
47
49  op = r.op;
50  type = r.type;
51  b = r.b;
52  res = r.res;
53  if (type == 0 || type == 1 || type == 4) {
54  a.c = new Integer(*(r.a.c));
55  } else {
56  a.i = r.a.i;
57  }
58  }
59
61  if (type == 0 || type == 1) {
62  delete a.c;
63  }
64  }
65 };
66
67 /**
68  * A multivariate polynomial with Integer coefficients using a
69  * sparse representation. Only non-zero coefficients are encoded.
70  */
71 class SparseMultivariateIntegerPolynomial: public BPASRecursivelyViewedPolynomial<Integer,SparseMultivariateIntegerPolynomial> {
72
73  private:
74  mutable AltArrZ_t* poly;
75  int nvar; //number of variables
76  Symbol* names; //list of strings representing the variables.
77  //names is 1 if "system-generated" variables
78  //names is 9 if "user-specified" variables
79
81
82  /**
83  * Construct an SMZP given the alternating array.
84  */
85  SparseMultivariateIntegerPolynomial(AltArrZ_t* aa, int vars, Symbol* varNames);
86
87  /**
88  * Attempt to construct an SMZP given the rational number alternating array.
89  */
90  SparseMultivariateIntegerPolynomial(const RationalNumber& r, AltArr_t* aa, int vars, Symbol* varNames);
91
92  /**
93  * Determine if *this and b have compatible variable orderings.
94  * xs returns the mapping of both *this and b to the compatible superset
95  * returns true iff compatible.
96  */
97  bool isOrderedRing(const SparseMultivariateIntegerPolynomial& b, std::vector<int>& xs) const;
98
99  /**
100  * Rearrange exponent vectors in place and then re-sort the polynomial.
101  */
102  void reorderVarsInPlace(int varmap[]);
103
104  /**
105  * Rearrange exponent vectors, expanding as needed, and then re-sort the polynomial.
106  */
107  void expandVarsInPlace(int vars, Symbol* newvars, int varmap[]);
108
109  /**
110  * Returns a copy of *this under the new variable ordering supplied.
111  * varmap is such that this.names[i] = newvars[varmap[i]]
112  * Returns an SMQP equal to *this but expended to newvars.
113  */
114  SparseMultivariateIntegerPolynomial expandVariables(int vars, Symbol* newvars, int varmap[]) const;
115
116  public:
117
119
120  std::vector<SparseMultivariateIntegerPolynomial> subresultantChain (const SparseMultivariateIntegerPolynomial& q, int filled = 0) const;
121
123
124  std::vector<SLPZRepresentation> slp;
125
126  /* Constructors */
127
128  /**
129  * Construct a multivariate polynomial
130  *
131  **/
133
134  /**
135  * Construct a multivariate polynomial with specific number of variables
136  *
137  * @param v: Number of variables
138  **/
140
141  /**htop
142
143  * Construct with a variable name such that f(x) = x;
144  *
145  * @param x: The variable name
146  **/
148
149  /**
150  * Construct a polynomial by parsing the string str.
151  */
152  SparseMultivariateIntegerPolynomial (const std::string& str);
153
154  /**
155  * Copy Constructor.
156  *
157  * Does not reuse underlying memory allocated by b.
158  *
159  * @param b: A sparse multivariate polynomial
160  **/
162
163  /**
164  * Move Constructor.
165  *
166  * @params b: The r-value reference polynomial.
167  */
169
170  /**
171  * Create a SMZP from an SMQP.
172  */
174
175  /**
176  * Create a SMZP from an Integer.
177  */
178  SparseMultivariateIntegerPolynomial(const Integer& r, int nvar = 0);
179
180  /**
181  * Create a SMZP from a RationalNumber.
182  */
183  SparseMultivariateIntegerPolynomial(const RationalNumber& r, int nvar = 0);
184
185  /**
186  * Create a SMZP from a univariate rational polynomial.
187  *
188  * @param p: A SUZP polynomial.
189  **/
191
192  /**
193  * Construct from a SUP<SMZP> polynomial such that the resulting SMZP
194  * has main variable equal to the variable of s.
195  *
196  * @param s: The SUP<SMZP> polynomial
197  **/
199
200  /**
201  * Destroy the polynomial and underlying node memory.
202  **/
204
205
206  /* BPASRing interface */
207  static mpz_class characteristic;
208  static RingProperties properties;
209  // static bool isPrimeField;
210  // static bool isSmallPrimeField;
211  // static bool isComplexField;
212
213  /**
214  * Is this polynomial zero.
215  * returns true iff this polynomial encodes 0.
216  */
217  bool isZero() const;
218
219  /**
220  * Set this polynomial to zero. Maintains existing variable ordering.
221  */
222  void zero();
223
224  /**
225  * Is this polynomial one.
226  * return true iff this polynomial encodes 1.
227  */
228  bool isOne() const;
229
230  /**
231  * Sets this polynomial to one. Maintains existing variable ordering.
232  */
233  void one();
234
235  /**
236  * Is this polynomial negative one.
237  * returns true iff this polynomial encodes -1.
238  */
239  bool isNegativeOne() const;
240
241  /**
242  * Sets this polynomial to -1. Maintains existing variable ordering.
243  */
244  void negativeOne();
245
246  /**
247  * Determine if this polynomial encodes a constant.
248  * returns 0 if not a constant, 1 if a constant >= 0, -1 if a negative contstant.
249  */
250  int isConstant() const;
251
252  /**
253  * Obtain the unit normal (a.k.a canonical associate) of an element.
254  * If either parameters u, v, are non-NULL then the units are returned such that
255  * b = ua, v = u^-1. Where b is the unit normal of a, and is the returned value.
256  */
258  if (isZero()) {
259  return *this;
260  }
261
262  if (mpz_cmp_si(this->poly->elems->coef, 0l) < 0) {
264  if (u != NULL) {
266  }
267  if (v != NULL) {
268  *v = *u;
269  }
270  return ret;
271  }
272
273  if (u != NULL) {
274  (*u).one();
275  }
276  if (v != NULL) {
277  (*v).one();
278  }
279  return *this;
280  }
281
282  /* BPASPolynomial interface */
283
284  /**
285  * Assign this polynomail to equal the specified.
286  */
288
289  /**
290  * Movement assignment: move b to be this polynomail.
291  */
293
294  /**
295  * Assign this polynomial to be equal to the constant ring element.
296  */
298
299  /**
300  * Add two SMQP polynomials together, *this and the specified.
301  */
304
305  /**
306  * Add the polynomails a and b and return the sum.
307  */
308  // friend SparseMultivariateIntegerPolynomial operator+ (SparseMultivariateIntegerPolynomial&& a, const SparseMultivariateIntegerPolynomial& b);
309
310  /**
311  * Update *this by adding the specified polynomail to it.
312  */
314
315  /**
316  * Subtract the specified polynomail from *this
317  */
320
321  /**
322  * Subtract the polynomial b from a and return the difference.
323  */
324  // friend SparseMultivariateIntegerPolynomial operator- (SparseMultivariateIntegerPolynomial&& a, const SparseMultivariateIntegerPolynomial& b);
325
326  /**
327  * Unary operation, return *this * -1.
328  */
330
331  /**
332  * Update *this by subtracting the specified polynomial from it.
333  */
335
336  /**
337  * Multiply *this by the specified polynomail.
338  */
341
342  /**
343  * Multiply the polynomials a and b, returning their product.
344  */
345  // friend SparseMultivariateIntegerPolynomial operator* (SparseMultivariateIntegerPolynomial&& a, const SparseMultivariateIntegerPolynomial& b);
346
347  /**
348  * Update this by multiplying by the specified polynomail.
349  */
351
352  /**
353  * Divide *this by the specified polynomial.
354  */
357
358  // friend SparseMultivariateIntegerPolynomial operator/ (SparseMultivariateIntegerPolynomial&& a, const SparseMultivariateIntegerPolynomial& b);
359
360  /**
361  * Update *this by dividing by the specified polynomial.
362  */
364
365  /**
366  * Exponentiate *this by the input exponent integer.
367  * Treats negative exponents as positive.
368  */
369  SparseMultivariateIntegerPolynomial operator^ (long long int e) const;
370
371  /**
372  * Update *this by exponentiating this to the input integer.
373  * Treats negative exponents as positive.
374  */
376
377  /**
378  * Determine if *this is equal to the specified polynomial.
379  * This takes into account the variable ordering on both poylnomials
380  * in such a way that the same polynomial under different variable orderings
381  * are NOT equal.
382  */
384
385  /**
386  * Determine if *this is not equal to the specified polynomial.
387  * This takes into account the variable ordering on both poylnomials
388  * in such a way that the same polynomial under different variable orderings
389  * are NOT equal.
390  */
392
393  /**
394  * Output the string representation of *this to the input ostream.
395  */
396  void print(std::ostream& os) const;
397
398  /**
399  * Parse a polynomial from the in stream. Exactly one line is parsed.
400  */
401  friend std::istream& operator>>(std::istream& in, SparseMultivariateIntegerPolynomial& p);
402
403  /**
404  * Parse a polynomial from the string str and place it in *this.
405  */
406  void fromString(const std::string& str);
407
408  /**
409  * Get GCD between *this and b.
410  */
412
413  /**
414  * Get the GCD between *this and b as a primitive polynomial.
415  */
417
418  /**
419  * Compute squarefree factorization of *this with respect to all of its variables.
420  */
422
423  /**
424  * Compute squarefree factorization of *this with respect to the list of variables, vars.
425  */
426  Factors<SparseMultivariateIntegerPolynomial> squareFree(const std::vector<Symbol>& vars) const;
427
428  /**
429  * Computes the square free part of this polynomail. That is, the polynomial of this
430  * divided by all square factors. This is with respect to all variables.
431  */
433
434  /**
435  * Computes the square free part of this polynomail. That is, the polynomial of this
436  * divided by all square factors. This is with respect to all variables.
437  */
438  SparseMultivariateIntegerPolynomial squareFreePart(std::vector<Symbol>& vars) const;
439
440  /**
441  * Get the content with respect to all variables. That is, a single
442  * rational number. The content here is one such that this/content is
443  * an integer polynomial with content of 1.
444  *
445  * Moreover, the content is one such that the leading coefficient
446  * of the corresponding primitive part is positive.
447  */
448  Integer content() const;
449
450  /**
451  * Get the content of this polynomial with respect to the variables in
452  * the input vector v.
453  *
454  * Moreover, the content is one such that the leading coefficient
455  * of the corresponding primitive part is positive.
456  */
457  SparseMultivariateIntegerPolynomial content(const std::vector<Symbol>& v) const;
458
459  /**
460  * Get the primitive part with respect to all variables.
461  * This is equivalent to this / content().
462  */
464
465  /**
466  * Get the primitive part with respect to all variables.
467  * This is equivalent to this / content().
468  *
469  * Simultaneously returns the rational number content in the parameter content.
470  */
472
473  /**
474  * Get the primitive part with respect to the variables in the vector v.
475  *
476  * returns the primitive part.
477  */
478  SparseMultivariateIntegerPolynomial primitivePart(const std::vector<Symbol>& v) const;
479
480  /**
481  * Get the primitive part with respect to the variables in the vector v.
482  * Returns the corresponding content in the content reference.
483  * returns the primitive part.
484  */
485  SparseMultivariateIntegerPolynomial primitivePart(const std::vector<Symbol>& v, SparseMultivariateIntegerPolynomial& content) const;
486
487  /**
488  * Get the leading coefficient of *this with respect to the main variable.
489  *
490  * returns the initial.
491  */
493
494  /**
495  * Get the main variable. That is, the highest-ordered variable with
496  * positive degree.
497  *
498  * returns the main variable.
499  */
500  inline Symbol mainVariable() const {
502  }
503
504  /**
505  * Get the degree of the main variable.
506  *
507  * returns the degree.
508  */
509  int mainDegree() const;
510
511  /**
512  * Get the rank of this polynomial.
513  * That is, the main variable raised to the main degree.
514  *
515  * returns the rank.
516  */
518
519  /**
520  * Get the head of this polynomial. That is, the initial multiplied
521  * by the rank.
522  *
523  * returns the head.
524  */
526
527  /**
528  * Get the tail of this polynomial. That is, This - this.head().
529  *
530  * returns the tail.
531  */
533
534  SparseMultivariateIntegerPolynomial separant() const;
535
536  /* BPASMultivariatePolynomial interface */
537
538  /**
539  * Get the number of variables in this polynomial.
540  */
541  int numberOfVariables() const;
542
543  /**
544  * Get the number of variables in this polynomial ring.
545  */
546  inline int numberOfRingVariables() const {
547  return ringVariables().size();
548  }
549
550  /**
551  * Get the number of non-zero terms
552  */
553  Integer numberOfTerms() const;
554
555  /**
556  * Total degree.
557  */
558  Integer degree() const;
559
560  /**
561  * Get the degree of a variable
562  */
563  Integer degree(const Symbol&) const;
564
565  /**
566  * Get the leading coefficient
567  */
568  Integer leadingCoefficient() const;
569
570  /**
571  * Set the leading coefficient.
572  */
573  void setLeadingCoefficient(const Integer& it);
574
575  /**
576  * Get the trailing coefficient.
577  */
579
580  /**
581  * Get a coefficient, given the exponent of each variable
582  */
583  Integer coefficient(int, const int*) const;
584
585  inline Integer coefficient(const std::vector<int>& v) const {
586  return coefficient(v.size(), v.data());
587  }
588
589  /**
590  * Set a coefficient, given the exponent of each variable
591  */
592  void setCoefficient(int, const int*, const Integer&);
593
594  inline void setCoefficient(const std::vector<int>& v, const Integer& r) {
595  setCoefficient(v.size(), v.data(), r);
596  }
597
598
599  /**
600  * Set variables' names.
601  *
602  * This method can be used to shrink, expand, re-order, and re-name the variables
603  * of the polynomial ring in which this polynomial belongs.
604  *
605  * Any symbol in the input vector that matches the current variables
606  * is considered a re-order. Non-matching symbols are considered a re-name
607  * and this renames is done in the order they appear by increasing index.
608  * For example: Q[x,y,z] -> Q[y,s,t] will have y reordered to be the
609  * first variable, x renamed to s, and z renamed to t.
610  *
611  * If the size of the input vector is greater than the current number of variables
612  * then the polynomial ring is being expanded. Matching variables from this
613  * polynomial are re-ordered as they appear in the input vector. Current variables
614  * that have no match in the input vector are re-named in order of increasing index
615  * of unused variables from the input vector.
616  * For example: Q[x,y,z] -> Q[s,t,z,x] will have y named to s, t a new variable,
617  * and z and x re-ordered accordingly.
618  *
619  * If the size of the input vector is less than the current number of variables
620  * then the polynomial ring is shrink to remove variables. Variables in the
621  * input vector that are also found to be in the current polynomial ring
622  * are matched and re-ordered as necessary.
623  *
624  * It is invalid to remove a variable which is non-zero in this polynomial.
625  */
626  void setRingVariables (const std::vector<Symbol>&);
627
628  /**
629  * Get variable names of all variables available to this polynomial,
630  * even those that have zero degree.
631  */
632  std::vector<Symbol> ringVariables() const;
633
634  /**
635  * Get variable names of variables with non-zero degree;
636  */
637  std::vector<Symbol> variables() const;
638
639
640  /* SMQP-specific */
641
642  /**
643  * Determine if *this is equal to b.
644  * This takes into account the variable ordering on both poylnomials
645  * in such a way that the same polynomial under different variable orderings
646  * are NOT equal.
647  */
648  bool isEqual(const SparseMultivariateIntegerPolynomial& b) const;
649
650  /**
651  * Convert current object to its k-th derivative
652  *
653  * @param s: Symbol to differentiate with respect to
654  * @param k: Order of the derivative, k > 0
655  **/
656  inline void differentiate(const Symbol& s, int k) {
657  *this = this->derivative(s, k);
658  }
659
660  /**
661  * Convert current object to its derivative
662  *
663  * @param s: Symbol to differentiate with respect to
664  **/
665  inline void differentiate(const Symbol& s) {
666  this->differentiate(s,1);
667  }
668
669  /**
670  * Return k-th derivative
671  *
672  * @param s: Symbol to differentiate with respect to
673  * @param k: Order of the k-th derivative, k > 0
674  **/
675  SparseMultivariateIntegerPolynomial derivative(const Symbol& s, int k) const;
676
677  /**
678  * Compute derivative
679  *
680  * @param s: Symbol to differentiate with respect to
681  **/
683  return this->derivative(s,1);
684  }
685
686  /**
687  * Convert current object to its k-th integral
688  *
689  * @param s: Symbol to differentiate with respect to
690  * @param k: Order of the derivative, k > 0
691  **/
692  inline void integrate(const Symbol& s, int k) {
693  *this = this->integral(s, k);
694  }
695
696  /**
697  * Convert current object to its derivative
698  *
699  * @param s: Symbol to differentiate with respect to
700  **/
701  inline void integrate(const Symbol& s) {
702  this->integrate(s,1);
703  }
704
705  /**
706  * Return k-th integral. If Symbol s is not a symbol contained in this
707  * polynomial then it becomes the main variable of the result and
708  * integration proceeds as expected.
709  *
710  * If the integral of this polynomial cannot be represented as an integer
711  * polynomial then an error occurs. See rationalIntegral().
712  *
713  * @param s: Symbol to differentiate with respect to
714  * @param k: Order of the k-th derivative, k > 0
715  **/
716  SparseMultivariateIntegerPolynomial integral(const Symbol& s, int k) const;
717
718  /**
719  * Return k-th integral. If Symbol s is not a symbol contained in this
720  * polynomial then it becomes the main variable of the result and
721  * integration proceeds as expected.
722  *
723  * This method returns a rational number polynomial and therefore works
724  * regardless of the coefficients of this polynomial.
725  *
726  * @param s: Symbol to differentiate with respect to
727  * @param k: Order of the k-th derivative, k > 0
728  **/
729  SparseMultivariateRationalPolynomial rationalIntegral(const Symbol& s, int k) const;
730
731  /**
732  * Compute integral
733  *
734  * @param s: Symbol to differentiate with respect to
735  **/
737  return this->integral(s,1);
738  }
739
740  /**
741  * Return the integral of this, with respect to Symbol s, as a rational number polynomial.
742  *
743  * @param s: the symbol to integrate with respect to
744  * returns the integral
745  */
746  SparseMultivariateRationalPolynomial rationalIntegral(const Symbol& s) const;
747
748  /**
749  * Evaluate f(x)
750  *
751  * @param syms: Array of Symbols to evaluate at corresponding xs
752  * @param xs: Evaluation points
753  **/
754  inline SparseMultivariateIntegerPolynomial evaluate(int n, const Symbol* syms, const Integer* xs) const {
755  std::vector<Symbol> vecSyms;
756  std::vector<Integer> vecRats;
757  vecSyms.reserve(n);
758  vecRats.reserve(n);
759  for (int i = 0; i < n; ++i) {
760  vecSyms.push_back(syms[i]);
761  vecRats.push_back(xs[i]);
762  }
763  return evaluate(vecSyms, vecRats);
764  }
765
766  /**
767  * Evaluate *this polynomial given the variables and their values in vars, and values.
768  * vars must be a list of variables which are a (not necessarily proper) subset.
769  * vars and values should have matching indices. i.e. the values of vars[i] is values[i].
770  *
771  * returns a new SMQP where all variables in vars have been evaluated using the values given.
772  */
773  SparseMultivariateIntegerPolynomial evaluate(const std::vector<Symbol>& vars, const std::vector<Integer>& values) const;
774
775  /**
776  * Find the interpolating polynomial for the integer points and values specified by each vector, respectively.
777  * The points vector is a vector of vectors, where each element of the outer vector represents a multi-dimensional point.
778  * Each multi-dimensional point should have the same number of dimensions and in the same order.
779  *
780  * An error will occur if the resulting interpolating polynomial cannot be represented as an integer polynomial.
781  *
782  * returns the interpolating polynomial.
783  */
784  static SparseMultivariateIntegerPolynomial interpolate(const std::vector<std::vector<Integer>>& points, const std::vector<Integer>& vals);
785
786  /**
787  * Find the interpolating polynomial for the rational number points and values specified by each vector, respectively.
788  * The points vector is a vector of vectors, where each element of the outer vector represents a multi-dimensional point.
789  * Each multi-dimensional point should have the same number of dimensions and in the same order.
790  *
791  * An error will occur if the resulting interpolating polynomial cannot be represented as an integer polynomial.
792  *
793  * returns the interpolating polynomial.
794  */
795  static SparseMultivariateIntegerPolynomial interpolate(const std::vector<std::vector<RationalNumber>>& points, const std::vector<RationalNumber>& vals);
796
797
798  /**
799  * Divide this by polynomial b, returning the quotient and remainder in q and r, respectively.
800  *
801  * returns a boolean indicating if the division was exact.
802  */
804
805  /**
806  * Divide this by polynomial b, return the quotient and remainder in q and r as rational number polynomials.
807  * This differs from the normal divide function where divisibility of coefficients does not matter as the result
808  * belongs to the polynomial ring over the rational numbers.
809  *
810  * returns a boolean indicating if the division was exact.
811  */
813
814  /**
815  * Get the remainder of *this divided by b.
816  */
818
819  /**
820  * Update *this by setting it to the remainder of *this divided by b.
821  */
823
824  /**
825  * Pseudo divide this by b. The remainder is returned.
826  * if parameter quo is not null then the quotient is returned in quo.
827  * if parameter mult is not null then the multiplier is set to the initial of b
828  * raised to the power of degree(c, mvar(c)) - degree(b, mvar(c)) + 1.
829  *
830  * returns the pseudo remainder.
831  */
833
834
835  /**
836  * Add *this and a mpz_t.
837  */
838  inline SparseMultivariateIntegerPolynomial operator+ (const mpz_t r) const {
839  return (*this + mpz_class(r));
840  }
841
842  /**
843  * Add *this and the mpz_class r.
844  */
845  SparseMultivariateIntegerPolynomial operator+ (const mpz_class& r) const;
846
848  return (*this + r.get_mpz());
849  }
850
851  /**
852  * Add mpz_t r and SMQP b.
853  */
855  return (b + r);
856  }
857
858  /**
859  * Update *this by adding r
860  */
862  return (*this += mpz_class(r));
863  }
864
865
866  /**
867  * Add mpz_class r and SMQP b.
868  */
870  return (b + r);
871  }
872
873  /**
874  * Update *this by adding the mpz_class r to it.
875  */
877
878  /**
879  * Update *this by adding the Integer r to it.
880  */
882  *this += r.get_mpz();
883  return *this;
884  }
885
886  /**
887  * Subtract the mpz_t r from *this.
888  */
889  inline SparseMultivariateIntegerPolynomial operator- (const mpz_t r) const {
890  return (*this - mpz_class(r));
891  }
892
893  /**
894  * Subtract the mpz_class r from *this.
895  */
896  SparseMultivariateIntegerPolynomial operator- (const mpz_class& r) const;
897
898  /**
899  * Subtract the Integer r from *this.
900  */
902  return (*this - r.get_mpz());
903  }
904
905  /**
906  * Subtract SMQP b from mpz_t r.
907  */
909  return (-b + r);
910  }
911
912  /**
913  * Update *this by subtracting mpz_t r.
914  */
916  return (*this -= mpz_class(r));
917  }
918
919
920  /**
921  * Subtract SMQP b from mpz_class r.
922  */
924  return (-b + r);
925  }
926
927  /**
928  * Update *this by subtracting mpz_class r.
929  */
931
932  /**
933  * Update *this by subtracting Integer r.
934  */
936  *this -= r.get_mpz();
937  return *this;
938  }
939
940  /**
941  * Multiply *this by mpz_t r.
942  */
943  inline SparseMultivariateIntegerPolynomial operator* (const mpz_t r) const {
944  return (*this * mpz_class(r));
945  }
946
947  /**
948  * Multiply *this by mpz_class r.
949  */
950  SparseMultivariateIntegerPolynomial operator* (const mpz_class& r) const;
951
952  /**
953  * Multiply *this by Integer r.
954  */
956  return (*this * r.get_mpz());
957  }
958
959  /**
960  * Multiply mpz_t r and SMQP b.
961  */
963  return (b * r);
964  }
965
966  /**
967  * Update *this by multiplying by mpz_t r.
968  */
970  return (*this *= mpz_class(r));
971  }
972
973  /**
974  * Multiply mpz_class r and SMQP b.
975  */
977  return (b * r);
978  }
979
980  /**
981  * Update *this by multiplying by mpz_class r.
982  */
984
985  /**
986  * Update *this by multiplying by Integer r.
987  */
989  *this *= r.get_mpz();
990  return *this;
991  }
992
993  /**
994  * Divide *this by mpz_t r.
995  */
996  inline SparseMultivariateIntegerPolynomial operator/ (const mpz_t r) const {
997  return (*this / mpz_class(r));
998  }
999
1000  /**
1001  * Divide *this by mpz_class r.
1002  */
1003  SparseMultivariateIntegerPolynomial operator/ (const mpz_class& r) const;
1004
1005  /**
1006  * Divide *this by Integer r.
1007  */
1009  return (*this / r.get_mpz());
1010  }
1011
1012  /**
1013  * Divide mpz_t r by SMQP b.
1014  */
1016
1017  /**
1018  * Update *this by dividing by mpz_t r.
1019  */
1021  return (*this /= mpz_class(r));
1022  }
1023  /**
1024  * Divide mpz_class r by SMQP b.
1025  */
1027  mpz_t t;
1028  mpz_init(t);
1029  mpz_set(t, r.get_mpz_t());
1031  mpz_clear(t);
1032  return ret;
1033  }
1034
1035  /**
1036  * Update *this by dividing by mpz_class r.
1037  */
1038  SparseMultivariateIntegerPolynomial& operator/= (const mpz_class& r);
1039  /**
1040  * Update *this by dividing by Integer r.
1041  */
1043  *this /= r.get_mpz();
1044  return *this;
1045  }
1046
1047  /**
1048  * Get the polynomial term at index. Returns 0 if index is beyond the
1049  * number of terms in this polynomial.
1050  */
1052
1053  /**
1054  * Get the leading variable, that is, the highest-order variable with positive degree
1055  * of this polynomial.
1056  * returns the leading variable or the empty string if this polynomial has zero variables.
1057  */
1058  Symbol leadingVariable() const;
1059
1060  /**
1061  * Get the degree of this polynomial w.r.t the leading variable.
1062  */
1064
1065  /**
1066  * Is the contant term zero.
1067  */
1068  bool isConstantTermZero() const;
1069
1070  /**
1071  * Get the leading coefficient w.r.t the input variable 'x'.
1072  * Returns the leading exponent as e.
1073  *
1074  * returns the coefficient as a new SMQP.
1075  */
1077
1078  /**
1079  * Convert to a SUP<SMQP> given the variable 'x'.
1080  *
1081  * returns the SUP<SMQP>.
1082  */
1084
1085  /**
1086  * Negate all the coefficients of *this. Note, that due to the
1087  * sharing nature of underling nodes, this may alter the Nodes of
1088  * other SMQP.
1089  */
1090  void negate();
1091
1092  /**
1093  * Get a copy of this such that all underlying memory is NOT shared.
1094  * Note, any following arithmetic operations on the returned result
1095  * will result in possibly making the underlying memory shared again.
1096  */
1098
1099  /**
1100  * Factors this polynomial into irreducible factors.
1101  * The Factors may include a common numerical (integer) factor.
1103  */
1105
1106  /**
1107  * SLP representation of the polynomial
1108  **/
1109  void straightLineProgram();
1110
1111  /**
1112  * Print SLP representation
1113  **/
1114  void printSLP(std::ostream& out = std::cout) const;
1115
1116  /**
1117  * Change *this to be a random non-zero polynomial.
1118  * numvar: number of variables
1119  * nterms: number of terms
1120  * coefBound: limit on the number of bits encoding the coefficients.
1121  * sparsity: succesive terms are at most sparsity away from each other
1122  * includeNeg: a bool to say if coefs can be randomly negative or all positive
1123  */
1124  void randomPolynomial(int numvar, int nterms, unsigned long int coefBound, degree_t sparsity, bool includeNeg);
1125
1126  /**
1127  * Change *this to be a random non-zero polynomial. The number of variables will
1128  * be equal to the size of the maxDegs vector. The term whose monomial
1129  * has exponents equal to those in maxDegs is guaranteed to exist in the
1130  * resulting polynomial.
1131  * A sparsity of 0 produces a dense polynomial. A sparsity of 1 produces only
1132  * one term; one whose monomial has exponents equal to maxDegs.
1133  *
1134  * coefBound: limit on the number of bits encoding the coefficients.
1135  * sparsity: a percentage of zero-terms between term with maxDegs and the constant term.
1136  * includeNeg: a bool to say if coefs can be randomly negative or all positive
1137  */
1138  void randomPolynomial(std::vector<int> maxDegs, unsigned long int coefBound, float sparsity, bool includeNeg);
1139
1140  /**
1141  * Convert *this to an ExpressionTree.
1142  *
1143  * returns the new ExpressionTree.
1144  */
1146 };
1147
1148
1149
1150
1151
bool isOne() const
Is this polynomial one.
std::vector< Symbol > variables() const
Get variable names of variables with non-zero degree;.
SparseUnivariatePolynomial< SparseMultivariateRationalPolynomial > convertToSUP(const Symbol &x) const
Convert to a SUP<SMQP> given the variable &#39;x&#39;.
A multivariate polynomial with Integer coefficients using a sparse representation.
Definition: mzpolynomial.hpp:71
SparseMultivariateRationalPolynomial & operator-=(const SparseMultivariateRationalPolynomial &b)
Update *this by subtracting the specified polynomial from it.
SparseMultivariateRationalPolynomial evaluate(int n, const Symbol *syms, const RationalNumber *xs) const
Evaluate f(x)
Definition: mrpolynomial.h:733
A univariate polynomial over an arbitrary BPASRing represented sparsely.
Definition: BigPrimeField.hpp:21
void setRingVariables(const std::vector< Symbol > &)
Set variables&#39; names.
static SparseMultivariateRationalPolynomial interpolate(const std::vector< std::vector< RationalNumber >> &points, const std::vector< RationalNumber > &vals)
Find the interpolating polynomial for the points and values specified by each vector, respectively.
SparseMultivariateRationalPolynomial & operator=(const SparseMultivariateRationalPolynomial &b)
Assign this polynomail to equal the specified.
SparseMultivariateRationalPolynomial operator[](int index) const
Get the polynomial term at index.
RationalNumber coefficient(int, const int *) const
Get a coefficient, given the exponent of each variable.
A multivariate polynomial with RationalNumber coefficients represented sparely.
Definition: mrpolynomial.h:70
Factors< SparseMultivariateRationalPolynomial > factor() const
Factors this polynomial into irreducible factors.
Integer numberOfTerms() const
Get the number of non-zero terms.
void fromString(const std::string &str)
Parse a polynomial from string str and place in *this.
int numberOfRingVariables() const
Get the number of variables in this polynomial ring.
Definition: mzpolynomial.hpp:546
ExpressionTree convertToExpressionTree() const
Convert *this to an ExpressionTree.
SparseMultivariateRationalPolynomial operator/(const SparseMultivariateRationalPolynomial &b) const
Divide *this by the specified polynomial.
SparseMultivariateRationalPolynomial pseudoDivide(const SparseMultivariateRationalPolynomial &b, SparseMultivariateRationalPolynomial *quo=NULL, SparseMultivariateRationalPolynomial *mult=NULL, bool lazy=0) const
Pseudo divide this by b.
Get the degree of this polynomial w.r.t the leading variable.
Definition: mzpolynomial.hpp:29
friend std::istream & operator>>(std::istream &in, SparseMultivariateRationalPolynomial &p)
Parse polynomial from in stream.
Factors< SparseMultivariateRationalPolynomial > squareFree() const
Compute squarefree factorization of *this with respect to all of its variables.
int mainDegree() const
Get the degree of the main variable.
SparseMultivariateRationalPolynomial primitiveGCD(const SparseMultivariateRationalPolynomial &b) const
Get the GCD between *this and b as a primitive polynomial.
SparseMultivariateIntegerPolynomial evaluate(int n, const Symbol *syms, const Integer *xs) const
Evaluate f(x)
Definition: mzpolynomial.hpp:754
Integer degree() const
Total degree.
void negate()
Negate all the coefficients of *this.
SparseMultivariateRationalPolynomial operator*(const SparseMultivariateRationalPolynomial &b) const
Multiply *this by the specified polynomail.
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
bool isEqual(const SparseMultivariateRationalPolynomial &b) const
Determine if *this is equal to b.
bool operator!=(const SparseMultivariateRationalPolynomial &b) const
Determine if *this is not equal to the specified polynomial.
SparseMultivariateRationalPolynomial gcd(const SparseMultivariateRationalPolynomial &b) const
Get GCD between *this and b.
int numberOfVariables() const
Get the number of variables in this polynomial.
void straightLineProgram()
SLP representation of the polynomial.
void negativeOne()
Sets this polynomial to -1.
Data Structure for interval [a, b].
Definition: interval.h:9
SparseMultivariateIntegerPolynomial unitCanonical(SparseMultivariateIntegerPolynomial *u, SparseMultivariateIntegerPolynomial *v) const
Obtain the unit normal (a.k.a canonical associate) of an element.
Definition: mzpolynomial.hpp:257
A univariate polynomial with Integer coefficients using a dense representation.
Definition: uzpolynomial.h:13
SparseMultivariateRationalPolynomial derivative(const Symbol &s, int k) const
Return k-th derivative.
Symbol mainVariable() const
Get the main variable.
Definition: mzpolynomial.hpp:500
SparseMultivariateRationalPolynomial deepCopy() const
Get a copy of this such that all underlying memory is NOT shared.
SparseMultivariateRationalPolynomial operator+(const SparseMultivariateRationalPolynomial &b) const
Add two SMQP polynomials together, *this and the specified.
SparseMultivariateIntegerPolynomial integral(const Symbol &s) const
Compute integral.
Definition: mzpolynomial.hpp:736
std::vector< Symbol > ringVariables() const
Get variable names of all variables available to this polynomial, even those that have zero degree...
SparseMultivariateRationalPolynomial primitivePart() const
Get the primitive part with respect to all variables.
RationalNumber trailingCoefficient() const
Get the trailing coefficient.
void print(std::ostream &os) const
Output the string representation of *this to the input ostream.
SparseMultivariateRationalPolynomial & operator*=(const SparseMultivariateRationalPolynomial &b)
Multiply the polynomials a and b, returning their product.
void differentiate(const Symbol &s, int k)
Convert current object to its k-th derivative.
Definition: mzpolynomial.hpp:656
A simple data structure for encapsulating a collection of Factor elements.
Definition: Factors.hpp:95
Get the leading coefficient.
bool divide(const SparseMultivariateRationalPolynomial &b, SparseMultivariateRationalPolynomial &q, SparseMultivariateRationalPolynomial &r) const
Divide this by polynomial b, returning the quotient and remainder in q and r, respectively.
void zero()
Set this polynomial to zero.
SparseMultivariateRationalPolynomial initial() const
Get the leading coefficient of *this with respect to the main variable.
void setCoefficient(int, const int *, const RationalNumber &)
Set a coefficient, given the exponent of each variable.
An arbitrary-precision Integer.
Definition: Integer.hpp:22
SparseMultivariateRationalPolynomial integral(const Symbol &s, int k) const
Return k-th integral.
void integrate(const Symbol &s, int k)
Convert current object to its k-th integral.
Definition: mrpolynomial.h:695
SparseMultivariateRationalPolynomial leadingCoefficientInVariable(const Symbol &x, int *e=NULL) const
Get the leading coefficient w.r.t the input variable &#39;x&#39;.
void printSLP(std::ostream &out=std::cout) const
Print SLP representation.
SparseMultivariateRationalPolynomial & operator/=(const SparseMultivariateRationalPolynomial &b)
Update *this by dividing by the specified polynomial.
SparseMultivariateRationalPolynomial operator%(const SparseMultivariateRationalPolynomial &b) const
Get the remainder of *this divided by b.
SparseMultivariateRationalPolynomial operator^(long long int e) const
Exponentiate *this by the input exponent integer.
RationalNumber content() const
Get the content with respect to all variables.
void one()
Sets this polynomial to one.
SparseMultivariateRationalPolynomial rank() const
Get the rank of this polynomial.
SparseMultivariateRationalPolynomial & operator%=(const SparseMultivariateRationalPolynomial &b)
Update *this by setting it to the remainder of *this divided by b.
bool operator==(const SparseMultivariateRationalPolynomial &b) const
Determine if *this is equal to the specified polynomial.
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
An arbitrary-precision rational number.
Definition: RationalNumber.hpp:24
bool isNegativeOne() const
Is this polynomial negative one.
An element of the SLP of an integer polynomial.
Definition: mzpolynomial.hpp:26
void one()
Sets this polynomial to one.
Get the leading variable, that is, the highest-order variable with positive degree of this polynomial...
Get the head of this polynomial.
bool isZero() const
Is this polynomial zero.
void integrate(const Symbol &s)
Convert current object to its derivative.
Definition: mzpolynomial.hpp:701
bool isConstantTermZero() const
Is the contant term zero.
SparseMultivariateIntegerPolynomial derivative(const Symbol &s) const
Compute derivative.
Definition: mzpolynomial.hpp:682
void integrate(const Symbol &s, int k)
Convert current object to its k-th integral.
Definition: mzpolynomial.hpp:692
void randomPolynomial(int numvar, int nterms, unsigned long int coefBound, degree_t sparsity, bool includeNeg)
Change *this to be a random non-zero polynomial.
SparseMultivariateRationalPolynomial & operator+=(const SparseMultivariateRationalPolynomial &b)
Add the polynomails a and b and return the sum.
SparseMultivariateRationalPolynomial squareFreePart() const
Computes the square free part of this polynomail.
int isConstant() const
Determine if this polynomial encodes a constant.
SparseMultivariateRationalPolynomial & operator^=(long long int e)
Update *this by exponentiating this to the input integer.
SparseMultivariateRationalPolynomial operator-() const
Subtract the polynomial b from a and return the difference.
SparseMultivariateRationalPolynomial tail() const
Get the tail of this polynomial.
void differentiate(const Symbol &s)
Convert current object to its derivative.
Definition: mzpolynomial.hpp:665
void differentiate(const Symbol &s, int k)
Convert current object to its k-th derivative.
Definition: mrpolynomial.h:659
An abstract class defining the interface of a multivariate polynomial that can be viewed recursively...
Definition: polynomial.h:166