Bounded-degree factors

The function bounded_degree_factors computes the bounded degree factors, with multiplicity, of a lacunary (a.k.a. super-sparse) polynomial. Actually, three different implementations are given: the univariate case, the bivariate case, and the multivariate case (which can also be used with bivariate polynomials). The generic function bounded_degree_factors simply choses the right implementation.

The functions described below used as inputs and outputs elements of type multivariate<…>, sparse_polynomial<…> and irreducible_factor<…>. For more on the first two types, please refer to the documentation of Multimix. For the third type, please refer to the documentation of Factorix.

1.Univariate polynomials

The function bounded_degree_factors_univariate takes as input a polynomial of type sparse_polynomial<C,monomial<vector<E> > > and a integer of type nat and outputs a vector of factors of type vector<irreducible_factor<sparse_polynomial<…> > >. It computes the irreducible factors of degree at most of . An example of use is as follows:

#include <lacunaryx/bounded_degree_factors_univariate.hpp>
…
#define E integer // or int
#define C integer // or rational
#define Monomial monomial< vector<E> >
#define Sparse_polynomial sparse_polynomial<C, Monomial>

…

Sparse_polynomial x (1, Monomial (vec(1))); // defines the variable x
Sparse_polynomial p= x*x*(x+1)*(x+1)*(x*x-2)*(2*x*x*x-x*x+3)*(x*x+x+1);
string s="4356768657564355757856462587657634635";
integer e(s);
p *= (1+3*binpow(x,1345) - 2*(x-4)*binpow(x,e)+(x*x*x-6)*binpow(x,2*e));

vector< irreducible_factor<Sparse_polynomial> > v=
  bounded_degree_factors_univariate(p, 2); 
           // [(x,2),(x+1,2),(x^2-2,1),(x^2+x+1,1)] 
           // but not (2*x^3-x^2+3,1) since its degree is 3 > 2.

2.Bivariate polynomials

For bivariate polynomials, one may either use the function bounded_degree_factors_bivariate or the more general function bounded_degree_factors_multivariate presented in the next section. Instead of taking as input a nat as in the univariate case, bounded_degree_factors_bivariate takes as input a vector<nat> to be able to bound the degree in each variable independently.

#include <lacunaryx/bounded_degree_factors_bivariate.hpp>
…
#define E integer // or int
#define C integer // or rational
#define Monomial monomial< vector<E> >
#define Sparse_polynomial sparse_polynomial<C, Monomial>

…

Sparse_polynomial x (1, Monomial (vec(1,0))); // defines the variable x
Sparse_polynomial y (1, Monomial (vec(0,1))); // defines the variable y

Sparse_polynomial p= x*x*y*(x-2)*(2*y+3)*(2*y+3)*(y-x*x*x+3)*(2*x+7*y*y*y);
string s="4356768657564355757856462587657634635";
integer e(s);
p *= (1 + 3*binpow(x,1345)*binpow(y,54334) - 2*(x-4*y)*binpow(x,e)*y*y + (x*x*x-6)*binpow(y,2*e));

vector< irreducible_factor<Sparse_polynomial> > v=
  bounded_degree_factors_bivariate(p, vec(3,2)); 
           // [(x,2),(y,1),(x-2,1),(2*y+3,2),(y-x^3+3,1)]
           // but not (2*x+7*y^3,1) since its y-degree is 3 > 2.

3.Multivariate polynomials

For multivariate polynomials, we rely on the facility provided by the type multivariate<…> of Multimix. Thus, the function bounded_degree_factors_multivariate takes as input a polynomial of type multivariate<Sparse_polynomial> where Sparse_polynomial is defined as in the univariate and bivariate cases. The output is a vector of type vector<irreducible_factor<multivariate<Sparse_polynomial> > >. As for the bivariate case, the bound on the degree of the computed factors is given as a vector<nat>.

#include <lacunaryx/bounded_degree_factors_multivariate.hpp>
…
#define E integer // or int
#define C integer // or rational
#define Monomial monomial< vector<E> >
#define Sparse_polynomial sparse_polynomial<C, Monomial>
#define Multivariate_polynomial multivariate<Sparse_polynomial>

…

Monomial mx (multivariate_coordinate<> ("x"));
Monomial my (multivariate_coordinate<> ("y"));
Monomial mz (multivariate_coordinate<> ("z"));
Multivariate_polynomial x, y, z, p;

x= Multivariate_polynomial (C(1), mx); // defines the variable x
y= Multivariate_polynomial (C(1), my); // defines the variable y
z= Multivariate_polynomial (C(1), mz); // defines the variable z

p= x * y*y * z*z*z*z;
p*= 1 - binpow (y, 1000);
p*= x*x*x*x*x*x - 3 * x*x*x*x * y * z*z + 7 * y*y*y * z*z*z; 
  // x^6 - 3*x^4*y*z^2 + 7*y^3*z^3
p*= 2 * y*y * x*x*x*x*x*x + 7 * y *z*z  + 3 * x*x*x*x * z;
  // 2*x^6*y^2 + 7*y*z^2 + 3*x^4*z



vector< irreducible_factor<Multivariate_polynomial> > v=
  bounded_degree_factors_multivariate(p, vec(6,3,2)); 
  // [(x,1),(y,2),(z,4),(y-1,1),(y+1,1),(y^2+1,1),(2x^6y^2 + 7yz^2 + 3x^4z,1)]
  // but not x^6 - 3*x^4*y*z^2 + 7*y^3*z^3 since its z-degree is 3 > 2.

4.Use within Mathemagix

These functions have not been glued for use in Mathemagix yet. Only the computations of linear factors are available.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU General Public License. If you don't have this file, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.