|
realroot_doc 0.1.1
|
|
realroot_doc 0.1.1
|
#include <subresultant.hpp>
Definition at line 52 of file subresultant.hpp.
| 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 subresultant< PREM >::subres_gcd().
{
for (unsigned i=0;i<s.size() ;i++)
if(s[i]!=0) return false;
return true;
}
| static Pol::value_type resultant | ( | const Pol & | p, |
| const Pol & | q | ||
| ) | [inline, static] |
Definition at line 132 of file subresultant.hpp.
References subresultant< PREM >::sequence(), and Seq< C, R >::size().
{
Seq<Pol> s= sequence(p,q);
if(s.size()>0)
return s[0][0];
else return 0;
}
| static Pol resultant | ( | const Pol & | p, |
| const Pol & | q, | ||
| int | v | ||
| ) | [inline, static] |
Definition at line 140 of file subresultant.hpp.
References subresultant< PREM >::sequence(), and Seq< C, R >::size().
{
Seq< Seq<Pol> > s = sequence(p,q,v);
if(s.size()>0) return s[0][0];
else return 0;
}
| 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(), subresultant< PREM >::sequence(), and Seq< C, R >::size().
{
Seq<Polynomial>
sp= coefficients(p,v),
sq= coefficients(q,v);
typedef polynomial< Polynomial, with<Univariate> > upolmpol_t;
upolmpol_t
P(1,sp.size()-1),
Q(1,sq.size()-1);
for (unsigned i=0;i<sp.size();i++) P[i]= sp[i];
for (unsigned i=0;i<sq.size();i++) Q[i]= sq[i];
Seq< upolmpol_t > s = subresultant<euclidean>::sequence(P,Q);
Seq< Seq<Polynomial> > res(s.size());
for(unsigned i=0;i<s.size();i++)
for(int j=0; j<=degree(s[i]);j++)
res[i]<<s[i][j];
return res;
}
| 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(), subresultant< PREM >::resultant(), subresultant< PREM >::sequence(), and subresultant< PREM >::subres_gcd().
{
typedef typename Pol::value_type coeff_type;
assert(degree(p) >=0 && degree(q) >= 0);
int n1 = degree(p), n2= degree(q);
coeff_type lp = p[n1], lq = q[n2];
Seq<Pol> tab;
unsigned N = std::min(n1,n2);
tab.resize(N);
for(unsigned i=0;i<N;i++) tab[i]=Pol(0);
int d,da,db;
coeff_type la;
Pol a, b, Sr;
if (n1>=n2) {
a=q;
b=PREM::prem(p,q);
d=n1-n2-1;
la=pow(lq,n1-n2);
} else {
a=p;
b=PREM::prem(q,p);
d=n2-n1-1;
la=pow(lp,n2-n1);
}
if (d!=0) {
a*=(coeff_type)pow<int>(-1,d*(d+1)/2);
b*=(coeff_type)pow<int>(-1,(d+2)*(d+3)/2);
}
da=degree(a);
db=degree(b);
if(db>=0) tab[db]=b;
while (db>=0) {
Sr =PREM::prem(a,b);
Sr/=(coeff_type)(pow(la,da-db)*a[da]);
Sr*=(coeff_type)pow<int>(-1,((da-db+1)*(da-db+2))/2);
a = b;
a *=(coeff_type)pow(b[db],da-db-1);
a /=(coeff_type)pow(la,da-db-1);
da=degree(a);
b=Sr;
la=a[da];
db=degree(b);
if (db>=0) tab[db]=b;
}
return tab;
}
| static Polynomial subres_gcd | ( | const Polynomial & | p, |
| const Polynomial & | q, | ||
| int | v | ||
| ) | [inline, static] |
Definition at line 154 of file subresultant.hpp.
References mmx::coefficients(), mmx::content(), mmx::degree(), mmx::gcd(), subresultant< PREM >::is_zero_seq(), Monomial, mmx::nbvar(), Polynomial, subresultant< PREM >::sequence(), and Seq< C, R >::size().
Referenced by mmx::gcd(), and subresultant< PREM >::subres_gcd().
{
typedef typename Polynomial::Monomial Monomial;
if(p==0) return q;
if(q==0) return p;
if(v==-1) return gcd(content(p),content(q));
if(nbvar(p)==v+1 && nbvar(q)<= v) {
Seq< Polynomial > s = coefficients(p,v);
Polynomial d=q;
for (unsigned i=0;i<s.size();i++)
d = subres_gcd(d,s[i]);
return d;
}
if(nbvar(p)<=v && nbvar(q)== v+1) {
Seq< Polynomial > s = coefficients(q,v);
Polynomial d=p;
for (unsigned i=0;i<s.size();i++)
d = subres_gcd(d,s[i]);
return d;
}
// Remove content of p
Polynomial dp=0;
Seq<Polynomial> sp = coefficients(p,v);
for(unsigned i=0;i< sp.size();i++) dp= subres_gcd(dp,sp[i]);
Polynomial P= p/dp;
// Remove content of q
Polynomial dq=0;
Seq<Polynomial> sq = coefficients(q,v);
for(unsigned i=0;i< sq.size();i++) dq= subres_gcd(dq,sq[i]);
Polynomial Q= q/dq;
// Take gcd of contents
Polynomial C= subres_gcd(dp,dq);
// Subresultant sequence
Seq< Seq<Polynomial> > s
= (degree(P)>=degree(Q)?sequence(P,Q,v):sequence(Q,P,v));
unsigned i;
for (i=0;i<s.size() && is_zero_seq(s[i]);i++) ;
if(i==s.size()) return (degree(P)>=degree(Q)?Q*C:P*C);
// Take last non-zero term
Seq<Polynomial> D = s[i];
// Remove content of last non-zero term.
Polynomial d=0;
for (i=0;i<D.size();i++) d = subres_gcd(d,D[i]);
// d/=content(d);
for (i=0;i<D.size();i++) D[i]/=d;
// Reconstruct the multivariate polynomial
Polynomial r=0;
for (i=0;i<D.size();i++)
r+= D[i]*Polynomial(Monomial(1,i,v));
r/=content(r);
r *= C;
return r;
}
| 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 subresultant< PREM >::subres_gcd().
{
int v = std::max(nbvar(p)-1,nbvar(q)-1);
return subres_gcd(p,q,v);
}
