sub_resultant< PREM > Struct Template Reference

#include <subresultant.hpp>

List of all members.

Static Public Member Functions

Detailed Description

template<class PREM>
struct mmx::sub_resultant< PREM >

Definition at line 52 of file subresultant.hpp.

Member Function Documentation

static bool is_zero_seq ( const Seq< Pol > &  s  )  [inline, static]

Definition at line 147 of file subresultant.hpp.

References Seq< C, R >::size().

Referenced by sub_resultant< PREM >::subres_gcd().

00147                                   {
00148     for (unsigned i=0;i<s.size() ;i++) 
00149       if(s[i]!=0) return false;
00150     return true;
00151   }

static Pol resultant ( const Pol &  p,
const Pol &  q,
int  v 
) [inline, static]

Definition at line 140 of file subresultant.hpp.

References sub_resultant< PREM >::sequence(), and Seq< C, R >::size().

00140                                                  {
00141     Seq< Seq<Pol> > s = sequence(p,q,v);
00142     if(s.size()>0) return s[0][0];
00143     else return 0;
00144   }

static Pol::value_type resultant ( const Pol &  p,
const Pol &  q 
) [inline, static]

Definition at line 132 of file subresultant.hpp.

References sub_resultant< PREM >::sequence(), and Seq< C, R >::size().

00132                                           {
00133     Seq<Pol> s= sequence(p,q);
00134     if(s.size()>0) 
00135       return s[0][0];
00136     else return 0;
00137   }

static Seq<Seq<Polynomial> > sequence ( const Polynomial &  p,
const Polynomial &  q,
int  v 
) [inline, static]

Definition at line 107 of file subresultant.hpp.

References mmx::coefficients(), mmx::degree(), sub_resultant< PREM >::sequence(), and Seq< C, R >::size().

00107                                                                                            {
00108 
00109     Seq<Polynomial> 
00110       sp= coefficients(p,v),
00111       sq= coefficients(q,v);
00112 
00113     typedef polynomial< Polynomial, with<Univariate> > upolmpol_t;
00114     upolmpol_t 
00115       P(1,sp.size()-1),
00116       Q(1,sq.size()-1);
00117 
00118     for (unsigned i=0;i<sp.size();i++) P[i]= sp[i];
00119     for (unsigned i=0;i<sq.size();i++) Q[i]= sq[i];
00120 
00121     Seq< upolmpol_t > s = sub_resultant<euclidean>::sequence(P,Q);
00122     
00123     Seq< Seq<Polynomial> > res(s.size());
00124     for(unsigned i=0;i<s.size();i++)
00125       for(int j=0; j<=degree(s[i]);j++)
00126         res[i]<<s[i][j];
00127 
00128     return res;
00129   }

static Seq<Pol> sequence ( const Pol &  p,
const Pol &  q 
) [inline, static]

Definition at line 55 of file subresultant.hpp.

References assert, mmx::degree(), mmx::min(), mmx::N(), mmx::pow(), and Seq< C, R >::resize().

Referenced by mmx::polynomial_resultant(), mmx::polynomial_sturm_sequence(), sub_resultant< PREM >::resultant(), sub_resultant< PREM >::sequence(), and sub_resultant< PREM >::subres_gcd().

00055                                                          {
00056 
00057     typedef typename Pol::value_type coeff_type;
00058     assert(degree(p) >=0 && degree(q) >= 0);
00059     int n1 = degree(p), n2= degree(q);
00060     coeff_type lp = p[n1], lq = q[n2];
00061     
00062     Seq<Pol> tab;
00063     unsigned N = std::min(n1,n2);
00064     tab.resize(N);
00065     for(unsigned i=0;i<N;i++) tab[i]=Pol(0);
00066     int d,da,db;
00067     coeff_type la;
00068     Pol a, b, Sr;
00069     
00070     if (n1>=n2) {
00071         a=q;
00072         b=PREM::prem(p,q);
00073         d=n1-n2-1;
00074         la=pow(lq,n1-n2);
00075     } else {
00076       a=p;
00077       b=PREM::prem(q,p);
00078       d=n2-n1-1;
00079       la=pow(lp,n2-n1);
00080     }
00081     
00082     if (d!=0) {
00083       a*=(coeff_type)pow<int>(-1,d*(d+1)/2);
00084       b*=(coeff_type)pow<int>(-1,(d+2)*(d+3)/2);
00085     }
00086     da=degree(a);
00087     db=degree(b);
00088     if(db>=0) tab[db]=b;
00089     
00090     while (db>=0) {
00091       Sr =PREM::prem(a,b);
00092       Sr/=(coeff_type)(pow(la,da-db)*a[da]);
00093       Sr*=(coeff_type)pow<int>(-1,((da-db+1)*(da-db+2))/2);
00094       a  = b;
00095       a *=(coeff_type)pow(b[db],da-db-1);
00096       a /=(coeff_type)pow(la,da-db-1); 
00097       da=degree(a); 
00098       b=Sr; 
00099       la=a[da]; 
00100       db=degree(b);
00101       if (db>=0) tab[db]=b;
00102     }
00103     return tab;
00104   }

static Polynomial subres_gcd ( const Polynomial &  p,
const Polynomial &  q 
) [inline, static]

Definition at line 220 of file subresultant.hpp.

References mmx::max(), mmx::nbvar(), and sub_resultant< PREM >::subres_gcd().

00220                                                          {
00221     int v = std::max(nbvar(p)-1,nbvar(q)-1);
00222     return subres_gcd(p,q,v);
00223   }

static Polynomial subres_gcd ( const Polynomial &  p,
const Polynomial &  q,
int  v 
) [inline, static]

Definition at line 154 of file subresultant.hpp.

References C, mmx::coefficients(), mmx::content(), D, mmx::degree(), mmx::gcd(), sub_resultant< PREM >::is_zero_seq(), Monomial, mmx::nbvar(), Polynomial, sub_resultant< PREM >::sequence(), and Seq< C, R >::size().

Referenced by mmx::sr_gcd(), and sub_resultant< PREM >::subres_gcd().

00154                                                                 {
00155     typedef typename Polynomial::Monomial Monomial;    
00156     if(p==0) return q;
00157     if(q==0) return p;
00158     if(v==-1) return gcd(content(p),content(q));
00159 
00160     if(nbvar(p)==v+1 && nbvar(q)<= v) {
00161       Seq< Polynomial > s = coefficients(p,v);
00162       Polynomial d=q;
00163       for (unsigned i=0;i<s.size();i++) 
00164         d = subres_gcd(d,s[i]);
00165       return d;
00166     }
00167 
00168     if(nbvar(p)<=v && nbvar(q)== v+1) {
00169       Seq< Polynomial > s = coefficients(q,v);
00170       Polynomial d=p;
00171       for (unsigned i=0;i<s.size();i++) 
00172         d = subres_gcd(d,s[i]);
00173       return d;
00174     }
00175 
00176 
00177     // Remove content of p
00178     Polynomial dp=0;
00179     Seq<Polynomial> sp = coefficients(p,v);
00180     for(unsigned i=0;i< sp.size();i++) dp= subres_gcd(dp,sp[i]);
00181     Polynomial P= p/dp;
00182 
00183     // Remove content of q
00184     Polynomial dq=0;
00185     Seq<Polynomial> sq = coefficients(q,v);
00186     for(unsigned i=0;i< sq.size();i++) dq= subres_gcd(dq,sq[i]);
00187     Polynomial Q= q/dq;
00188 
00189     // Take gcd of contents
00190     Polynomial C= subres_gcd(dp,dq);
00191 
00192     // Subresultant sequence
00193     Seq< Seq<Polynomial> > s 
00194       = (degree(P)>=degree(Q)?sequence(P,Q,v):sequence(Q,P,v));
00195 
00196     unsigned i;
00197     for (i=0;i<s.size() && is_zero_seq(s[i]);i++) ;
00198 
00199     if(i==s.size()) return (degree(P)>=degree(Q)?Q*C:P*C);
00200 
00201     // Take last non-zero term
00202     Seq<Polynomial> D = s[i];
00203 
00204     // Remove content of last non-zero term.
00205     Polynomial d=0;
00206     for (i=0;i<D.size();i++) d = subres_gcd(d,D[i]);
00207     //    d/=content(d);
00208     for (i=0;i<D.size();i++) D[i]/=d;
00209 
00210     // Reconstruct the multivariate polynomial
00211     Polynomial r=0;
00212     for (i=0;i<D.size();i++) 
00213       r+= D[i]*Polynomial(Monomial(1,i,v));
00214     r/=content(r);
00215     r *= C;
00216     return r;
00217   }

The documentation for this struct was generated from the following file:
Generated on 6 Dec 2012 for realroot by  doxygen 1.6.1