mmx::lacunaryx Namespace Reference

Functions

template<typename C , typename V1 , typename V2 , typename M , typename W > void set_as_bivariate_polynomial (polynomial< polynomial< C, V2 >, V1 > &p, const sparse_polynomial< C, M, W > &q)
template<typename C , typename M , typename W > polynomial< polynomial< C > > as_bivariate_polynomial (const sparse_polynomial< C, M, W > &q)
template<typename C , typename E , typename V > sparse_polynomial< C, monomial
< vector< E > >, V > as_sparse_polynomial (const polynomial< polynomial< rational > > &q)
template<typename C , typename E , typename V > irreducible_factor
< sparse_polynomial< C,
monomial< vector< E > >, V > > as_sparse_factor (const irreducible_factor< polynomial< polynomial< rational > > > &f)
template<typename C , typename E , typename V > sparse_polynomial< C, monomial
< vector< E > >, V > homogenize (const sparse_polynomial< C, monomial< vector< E > >, V > &p)
template<typename E , typename C , typename V > E w_deg (const sparse_polynomial< C, monomial< vector< E > >, V > &p, vector< E > w)
template<typename E > E w_deg (const monomial< vector< E > > m, vector< E > w)
template<typename E , typename C , typename V > vector< nat > sort_poly (const sparse_polynomial< C, monomial< vector< E > >, V > &q, vector< E > w)
template<typename E , typename C , typename V > vector< nat > sort_poly (const sparse_polynomial< C, monomial< vector< E > >, V > &q, nat var)
template<typename E , typename C , typename V > vector< sparse_polynomial< C,
monomial< vector< E > >, V > > w_homogeneous_parts (const sparse_polynomial< C, monomial< vector< E > >, V > &p, vector< E > w)
template<typename C , typename V , typename M , typename W > void set_as_polynomial (polynomial< C, V > &p, const sparse_polynomial< C, M, W > &q)
template<typename C , typename M , typename W > polynomial< C > as_polynomial (const sparse_polynomial< C, M, W > &q)
template<typename C > nat multiplicity (const polynomial< C > &f, const polynomial< C > &p)
template<typename C , typename E , typename V > sparse_polynomial< C, monomial
< vector< E > >, V > as_sparse_polynomial (const polynomial< rational > &q)
template<typename C , typename E , typename V > irreducible_factor
< sparse_polynomial< C,
monomial< vector< E > >, V > > as_sparse_factor (const irreducible_factor< polynomial< rational > > &f)
template<typename C , typename E , typename V > vector< irreducible_factor
< sparse_polynomial< C,
monomial< vector< E > >, V > > > intersect_factors (const vector< irreducible_factor< sparse_polynomial< C, monomial< vector< E > >, V > > > &f1, const vector< irreducible_factor< sparse_polynomial< C, monomial< vector< E > >, V > > > &f2)
template<typename E , typename C , typename V > sparse_polynomial< C, monomial
< vector< E > >, V > sparse_derive (const sparse_polynomial< C, monomial< vector< E > >, V > &p)

Function Documentation

polynomial<polynomial<C> > mmx::lacunaryx::as_bivariate_polynomial ( const sparse_polynomial< C, M, W > & q ) [inline]

Definition at line 69 of file linear_factors_bivariate.hpp.

References mmx::CF(), and set_as_bivariate_polynomial().

Referenced by mmx::truly_bivariate_linear_factors().

00069                                                                                          {
00070     polynomial<C> sample (CF(q));  
00071     polynomial<polynomial<C> > p (get_format (sample));
00072     set_as_bivariate_polynomial(p,q);
00073     return p;
00074   }

polynomial<C> mmx::lacunaryx::as_polynomial ( const sparse_polynomial< C, M, W > & q ) [inline]

Definition at line 51 of file linear_factors_univariate.hpp.

References mmx::CF(), and set_as_polynomial().

Referenced by mmx::multiplicity(), and mmx::non_cyclotomic_factors().

00051                                                                   {
00052     polynomial<C> p (CF(q));
00053     set_as_polynomial(p,q);
00054     return p;
00055   }

irreducible_factor< sparse_polynomial<C, monomial< vector<E> > , V> > mmx::lacunaryx::as_sparse_factor ( const irreducible_factor< polynomial< rational > > & f ) [inline]

Definition at line 93 of file linear_factors_univariate.hpp.

References Sparse_factor.

00093                                                               {
00094     return Sparse_factor (as_sparse_polynomial<C,E,V> (f.f), f.m);
00095   }

irreducible_factor< sparse_polynomial<C, monomial< vector<E> > , V> > mmx::lacunaryx::as_sparse_factor ( const irreducible_factor< polynomial< polynomial< rational > > > & f ) [inline]

Definition at line 104 of file linear_factors_bivariate.hpp.

References Sparse_factor.

00104                                                              {
00105     return Sparse_factor (as_sparse_polynomial<C,E,V> (f.f), f.m);
00106   }

sparse_polynomial<C, monomial< vector<E> > , V> mmx::lacunaryx::as_sparse_polynomial ( const polynomial< rational > & q ) [inline]

Definition at line 72 of file linear_factors_univariate.hpp.

References mmx::coefficients(), Monomial, mmx::N(), and Sparse_polynomial.

00072                                                        {
00073     vector<C> coefficients;
00074     vector<Monomial> monomials;
00075     C lcm_den=1;
00076     for (nat i=0; i<N(q); i++) {
00077       rational c= q[i];
00078       if (c != 0) lcm_den= lcm(lcm_den,as<C> (denominator (c)));
00079     }
00080     for (nat i=0; i<N(q); i++) {
00081       rational c= q[i];
00082       if (c != 0) {
00083         C num= as<C> (numerator (c));
00084         C den= as<C> (denominator (c));
00085         coefficients << num*(lcm_den/den);
00086         monomials << Monomial (vec(i));
00087       }
00088     }
00089     return Sparse_polynomial (coefficients, monomials, 1);
00090   }

sparse_polynomial<C, monomial< vector<E> > , V> mmx::lacunaryx::as_sparse_polynomial ( const polynomial< polynomial< rational > > & q ) [inline]

Definition at line 78 of file linear_factors_bivariate.hpp.

References mmx::coefficients(), Monomial, mmx::N(), and Sparse_polynomial.

00078                                                                      {
00079     vector< polynomial<rational> > v= coefficients(q);
00080     vector<C> coefficients;
00081     vector<Monomial> monomials;
00082     C lcm_den=1;
00083     for (nat i=0; i<N(v); i++) {
00084       for (nat j=0; j<N(v[i]); j++) {
00085         rational c= v[i][j];
00086         if (c != 0) lcm_den= lcm (lcm_den, as<C> (denominator (c)));
00087       }
00088     }
00089     for (nat i=0; i<N(v); i++) {
00090       for (nat j=0; j<N(v[i]); j++) {
00091         rational c= v[i][j];
00092         if (c != 0) {
00093           C num= as<C> (numerator (c));
00094           C den= as<C> (denominator (c));
00095           coefficients << num*lcm_den/den;
00096           monomials << Monomial (vec(i,j));
00097         }
00098       }
00099     }
00100     return Sparse_polynomial (coefficients, monomials, 2);
00101   }

sparse_polynomial<C, monomial< vector<E> > , V> mmx::lacunaryx::homogenize ( const sparse_polynomial< C, monomial< vector< E > >, V > & p ) [inline]

Definition at line 109 of file linear_factors_bivariate.hpp.

References mmx::coefficients(), mmx::deg(), mmx::E, Monomial, mmx::N(), Sparse_polynomial, and mmx::supp().

Referenced by mmx::linear_factors_bivariate(), and mmx::linear_factors_bivariate_naive().

00109                                                            {
00110     //ASSERT (dim(p) == 1, "wrong dimension"); 
00111     E d= deg(p);
00112     vector<Monomial> v= supp(p);
00113     for (nat i=0; i<N(v); i++) {
00114       E dm= deg (v[i],0);
00115       v[i]= Monomial (vec (dm,d-dm));
00116     }
00117     return Sparse_polynomial ( coefficients(p), v, 2);
00118   }

vector< irreducible_factor< sparse_polynomial<C, monomial< vector<E> > , V> > > mmx::lacunaryx::intersect_factors	(	const vector< irreducible_factor< sparse_polynomial< C, monomial< vector< E > >, V > > > &	f1,
		const vector< irreducible_factor< sparse_polynomial< C, monomial< vector< E > >, V > > > &	f2
	)			`[inline]`

Definition at line 99 of file linear_factors_univariate.hpp.

References mmx::N(), and Sparse_factors.

Referenced by mmx::linear_factors_bivariate_naive().

00100                                                {
00101     Sparse_factors f;
00102     for (nat i=0; i<N(f1); i++) {
00103       for (nat j=0; j<N(f2); j++) {
00104         if ((f1[i].f == f2[j].f) || (f1[i].f == -f2[j].f)) {
00105           if ( f1[i].m < f2[j].m ) f << f1[i]; 
00106           else f << f2[j];
00107           break;
00108         }
00109       }
00110     }
00111     return f;
00112   }

nat mmx::lacunaryx::multiplicity	(	const polynomial< C > &	f,
		const polynomial< C > &	p
	)			`[inline]`

Definition at line 59 of file linear_factors_univariate.hpp.

References mmx::derive(), and Univariate_polynomial.

00060                                                     {
00061     nat m=0;
00062     Univariate_polynomial q= copy(p);
00063     while (divides (f,q)) {
00064       m+=1;
00065       q=derive (q);
00066     }
00067     return m;
00068   } //

void mmx::lacunaryx::set_as_bivariate_polynomial	(	polynomial< polynomial< C, V2 >, V1 > &	p,
		const sparse_polynomial< C, M, W > &	q
	)			`[inline]`

Definition at line 37 of file linear_factors_bivariate.hpp.

References mmx::CF(), mmx::deg(), and mmx::N().

Referenced by as_bivariate_polynomial().

00038                                                                        {
00039   nat n1= 1 + as<nat> (deg (q,0));
00040   vector<nat> n2 (0u, n1);
00041   for (nat i= 0; i < N(q); i++) {
00042     nat e1= as<nat> (deg (get_monomial (q, i),0));
00043     nat e2= as<nat> (deg (get_monomial (q, i),1));
00044     n2[e1]= max (n2[e1], e2);
00045   }
00046   n2= n2+1;
00047   vector<C*> buf ((C*) NULL,n1);
00048   vector<nat> l2 (0u, n1);
00049   for (nat i= 0; i < n1; i++) {
00050     l2[i]= aligned_size<C,V2> (n2[i]);
00051     buf[i]= mmx_new<C> (l2[i], promote (0,CF(q)));
00052   }
00053 
00054   for (nat i= 0; i < N(q); i++) {
00055     nat e1= as<nat> (deg (get_monomial (q, i),0));
00056     nat e2= as<nat> (deg (get_monomial (q, i),1));
00057     buf[e1][e2]= get_coefficient (q, i);
00058   }
00059   nat l1= aligned_size<C,V2> (n1);
00060   polynomial<C,V2>* c1= mmx_new<polynomial<C,V2> > (l1);
00061   for (nat i= 0; i < n1; i++)
00062     c1[i]= polynomial<C,V2> (buf[i],n2[i],l2[i],CF(q));
00063   polynomial<C,V2> sample (CF(q));  
00064   p= polynomial<polynomial<C,V2>,V1> (c1, n1, l1, get_format (sample));
00065     
00066   }

void mmx::lacunaryx::set_as_polynomial	(	polynomial< C, V > &	p,
		const sparse_polynomial< C, M, W > &	q
	)			`[inline]`

Definition at line 40 of file linear_factors_univariate.hpp.

References mmx::CF(), mmx::deg(), and mmx::N().

Referenced by as_polynomial().

00040                                                                                  {
00041     //ASSERT (dim(q) == 1, "wrong dimension");
00042     nat n= as<nat> (deg(q)+1);
00043     nat l= aligned_size<C,V>(n);
00044     C* c= mmx_new<C>(l,promote(0,CF(q)));
00045     for (nat i=0; i<N(q); i++) 
00046       c[as<nat> (deg(get_monomial(q,i)))]= get_coefficient(q,i);
00047     p= polynomial<C,V>(c,n,l,CF(q));
00048   }

vector<nat> mmx::lacunaryx::sort_poly	(	const sparse_polynomial< C, monomial< vector< E > >, V > &	q,
		nat	var
	)			`[inline]`

Definition at line 147 of file linear_factors_bivariate.hpp.

References mmx::deg(), Monomial, and mmx::N().

00147                                                               {
00148     vector<E> degrees= fill<E>(0,N(q));
00149     vector<nat> order= fill<nat>(0,N(q));
00150     
00151     for (nat i=0; i<N(q); i++) {
00152       Monomial m= get_monomial(q,i);
00153       degrees[i]= deg(m,var);
00154     }
00155   
00156     sort (degrees, order);
00157     return order;
00158   }

vector<nat> mmx::lacunaryx::sort_poly	(	const sparse_polynomial< C, monomial< vector< E > >, V > &	q,
		vector< E >	w
	)			`[inline]`

Definition at line 132 of file linear_factors_bivariate.hpp.

References Monomial, mmx::N(), and w_deg().

Referenced by mmx::partition_bivariate_helper(), and w_homogeneous_parts().

00132                                                                   {
00133     vector<E> degrees= fill<E>(0,N(q));
00134     vector<nat> order= fill<nat>(0,N(q));
00135     
00136     for (nat i=0; i<N(q); i++) {
00137       Monomial m= get_monomial(q,i);
00138       degrees[i]= w_deg(m,w);
00139     }
00140   
00141     sort (degrees, order);
00142     return order;
00143   }

sparse_polynomial<C, monomial< vector<E> > , V> mmx::lacunaryx::sparse_derive ( const sparse_polynomial< C, monomial< vector< E > >, V > & p ) [inline]

Definition at line 115 of file linear_factors_univariate.hpp.

References mmx::coefficients(), mmx::deg(), mmx::E, Monomial, mmx::N(), and Sparse_polynomial.

00115                                                                {
00116   
00117     E d= deg(get_monomial(p,0));
00118     vector<Monomial> monomials= fill<Monomial> (vec(0),N(p)-1);
00119     vector<C> coefficients= fill<C> (0,N(p)-1);
00120   
00121     for (nat i=1; i<N(p); i++) {
00122       pair<C,Monomial> term= p[i];
00123       monomials[i-1]= cdr(term)/Monomial(vec(d+1));
00124       coefficients[i-1]= car(term)*(as<C> (deg (cdr (term)) - d));
00125     }
00126     
00127     return Sparse_polynomial(coefficients,monomials,1);
00128   }

E mmx::lacunaryx::w_deg	(	const monomial< vector< E > >	m,
		vector< E >	w
	)			`[inline]`

Definition at line 126 of file linear_factors_bivariate.hpp.

00126                                           {
00127     return dot (multi_deg(m),w);
00128   }

E mmx::lacunaryx::w_deg	(	const sparse_polynomial< C, monomial< vector< E > >, V > &	p,
		vector< E >	w
	)			`[inline]`

Definition at line 121 of file linear_factors_bivariate.hpp.

Referenced by sort_poly(), and w_homogeneous_parts().

00121                                                     {
00122     return dot (multi_deg(p), w);
00123   }

vector< sparse_polynomial<C, monomial< vector<E> > , V> > mmx::lacunaryx::w_homogeneous_parts	(	const sparse_polynomial< C, monomial< vector< E > >, V > &	p,
		vector< E >	w
	)			`[inline]`

Definition at line 162 of file linear_factors_bivariate.hpp.

References mmx::E, mmx::N(), sort_poly(), and w_deg().

Referenced by mmx::linear_factors_bivariate(), and mmx::linear_factors_bivariate_naive().

00162                                                                 {
00163     vector<nat> o= sort_poly(p,w);
00164     vector<Sparse_polynomial> v;
00165     
00166     E d= w_deg (get_monomial (p,o[0]), w);
00167     nat imin=0;
00168     for (nat i=1; i<N(p); i++) {
00169       if (w_deg (get_monomial (p,o[i]), w) > d) {
00170         v << range_permute(p, imin, i, o);
00171         imin=i;
00172         d= w_deg (get_monomial (p,o[i]), w);
00173       }
00174     }
00175     v << range_permute(p, imin, N(p), o);
00176     return v;
00177   }