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