continued_fraction_subdivision< K > Struct Template Reference

#include <solver_uv_continued_fraction.hpp>

List of all members.

Public Types

Static Public Member Functions

Detailed Description

template<class K>
struct mmx::continued_fraction_subdivision< K >

Definition at line 201 of file solver_uv_continued_fraction.hpp.

Member Typedef Documentation

typedef K::data data

Definition at line 211 of file solver_uv_continued_fraction.hpp.

typedef K::floating floating

Definition at line 206 of file solver_uv_continued_fraction.hpp.

typedef K::rational FT

Definition at line 203 of file solver_uv_continued_fraction.hpp.

typedef K::integer integer

Definition at line 204 of file solver_uv_continued_fraction.hpp.

typedef polynomial< floating, with<MonomialTensor> > polynomial_floating

Definition at line 210 of file solver_uv_continued_fraction.hpp.

typedef K::Polynomial polynomial_integer

Definition at line 208 of file solver_uv_continued_fraction.hpp.

typedef polynomial< rational, with<MonomialTensor> > polynomial_rational

Definition at line 209 of file solver_uv_continued_fraction.hpp.

typedef K::rational rational

Definition at line 205 of file solver_uv_continued_fraction.hpp.

typedef K::root_t root_t

Definition at line 207 of file solver_uv_continued_fraction.hpp.

typedef K::integer RT

Definition at line 202 of file solver_uv_continued_fraction.hpp.

Member Function Documentation

static void set_precision ( int  prec  )  [inline, static]

Definition at line 213 of file solver_uv_continued_fraction.hpp.

00213 {K::set_precision(prec);}

static void solve ( output &  sol,
const polynomial_floating &  f 
) [inline, static]

Definition at line 415 of file solver_uv_continued_fraction.hpp.

References mmx::degree(), and continued_fraction_subdivision< K >::solve_polynomial().

00415                                                       {
00416       //      std::cout << __FUNCTION__ << " R "<<f<<std::endl;
00417       polynomial_rational p(rational(0),degree(f));
00418 
00419       for(int i=0;i<degree(f)+1;i++) {
00420         p[i] = as<rational>(f[i]);
00421       }
00422       //solve_polynomial(sol,p);
00423       solve_polynomial(sol, univariate::numer<polynomial_integer> (p));
00424     }

static void solve ( output &  sol,
const polynomial_rational &  f 
) [inline, static]

Definition at line 409 of file solver_uv_continued_fraction.hpp.

References continued_fraction_subdivision< K >::solve_polynomial().

00409                                                       {
00410       //      std::cout << __FUNCTION__ << " R "<<f<<std::endl;
00411       solve_polynomial(sol, univariate::numer<polynomial_integer> (f));
00412     }

static void solve ( output &  sol,
const polynomial_integer &  f 
) [inline, static]

Definition at line 404 of file solver_uv_continued_fraction.hpp.

References continued_fraction_subdivision< K >::solve_polynomial().

00404                                                      {
00405       solve_polynomial(sol, f);
00406     }

static void solve_homography ( output &  sol,
const data_type &  ID,
const poly &   
) [inline, static]

Definition at line 244 of file solver_uv_continued_fraction.hpp.

References IntervalData< RT_, Poly_ >::b, IntervalData< RT_, Poly_ >::d, mmx::div_x(), IntervalData< RT_, Poly_ >::p, mmx::reverse(), mmx::reverse_shift_homography(), IntervalData< RT_, Poly_ >::s, mmx::scale(), mmx::shift(), mmx::shift_by_1(), mmx::sign_variation(), mmx::sparse::swap(), and mmx::to_FT().

Referenced by continued_fraction_subdivision< K >::solve_positive().

00244                                                                      {
00245         //            std::cout << __FUNCTION__ << " "<<ID.p<<std::endl;
00246 
00247 //        typename data_type::Poly X(1,0,1);
00248       //X[1] = RT(1); X[0]=RT(0);
00249 
00250       int iters  = 0;
00251       //const RT One(1);
00252       //FT Zero(0);
00253       //    std::cout << "Polynomial is " << ID.p << std::endl;
00254 
00255       typedef data_type IntervalData;
00256       std::stack< IntervalData > S;
00257       S.push( ID );
00258       while ( !S.empty() ) {
00259         ++iters;
00260         IntervalData ID = S.top();
00261         S.pop();
00262 
00263         //std::cout << "Polynomial is " << ID.p << std::endl;
00264         // Steps 3 - 4: Choose the method for computing the lower bound
00265         //--------------------------------------------------------------------
00266         RT a = K::lower_bound(ID.p);
00267         //    long k = Bd.lower_power_2( ID.p);
00268         //std::cout<< "\t Lower bound is "<< a<< std::endl;
00269 
00270         if ( a > RT(1) ) {
00271             scale(ID,a);
00272             a = RT(1);
00273         }
00274         //--------------------------------------------------------------------
00275         // Step 5 //
00276         if ( a >= RT(1) ) {
00277           shift(ID, a);
00278           //            std::cout<<"Shift by "<<a<<std::endl;
00279 
00280           if ( ID.p[0] == RT(0))
00281             {
00282               div_x(ID.p,1);
00283               sol << root_t( to_FT( ID.b, ID.d), to_FT( ID.b, ID.d ));
00284             }
00285           ID.s = sign_variation( ID.p);
00286         }
00287         //int s= Kernel::init_shift(ID);
00288         //--------------------------------------------------------------------
00289         if ( K::is_empty(ID) )
00290           continue;
00291         else if( K::is_good(ID) ) {
00292           sol << K::as_root(ID);
00293           continue;
00294         }
00295         //--------------------------------------------------------------------
00296         // Step 6
00297         IntervalData I1;
00298         shift_by_1( I1, ID);
00299 
00300         unsigned long r  = 0;
00301 
00302         if (I1.p[0] == RT(0)) {
00303           //    std::cout << "Zero at end point"<<std::endl;;
00304           sol << root_t( to_FT( I1.b, I1.d), to_FT(I1.b, I1.d) );
00305           div_x(I1.p,1);
00306           r = 1;
00307         }
00308         I1.s = sign_variation( I1.p);
00309 
00310         IntervalData I2;
00311         I2.s = ID.s - I1.s - r;
00312         reverse_shift_homography(I2,ID);
00313 
00314         // std::cout <<I1.s <<" "<<I2.s<<std::endl;
00315         // Step 7;
00316         if ( !K::is_empty(I2) && !K::is_good(I2) ) {
00317 
00318           //p2 = p2( 1 / (x+1));
00319           reverse( I2.p, ID.p);
00320           shift_by_1(I2.p);
00321 
00322           if ( I2.p[0] == 0) {
00323             div_x(I2.p,1);
00324           }
00325           I2.s = sign_variation( I2.p);
00326         }
00327 
00328         // Step 8
00329         if ( I1.s < I2.s ) {std::swap( I1, I2); }
00330 
00331         // Step 9
00332         if ( K::is_good(I1) ) {
00333           //    std::cout << "C) Sign variation: 1"<<std::endl;;
00334           sol << K::as_root(I1);
00335         } else if ( !K::is_empty(I1) ) {
00336           S.push(I1); //IntervalData( I1.a, I1.b, I1.c, I1.d, I1.p, I1.s));
00337         }
00338         // Step 10
00339         if ( K::is_good(I2) ) {
00340           //    std::cout << "D) Sign variation: 1"<<std::endl;;
00341           sol <<  K::as_root(I2);
00342         } else if ( !K::is_empty(I2) ) {
00343           S.push(I2); //IntervalData( I2.a, I2.b, I2.c, I2.d, I2.p, I2.s));
00344         }
00345       } // while
00346       //    std::cout << "-------------------- iters: " << iters << std::endl;
00347       return;
00348     }

static void solve_polynomial ( output &  sol,
const poly &  f,
int  mult = 1 
) [inline, static]

for (unsigned i = 0 ; i < isolating_intervals.size(); ++i) { if ( singleton( isolating_intervals[i]) ) { std::cout<<"XXX Singleton "<<isolating_intervals[i]<<std::endl; if ( lower( isolating_intervals[i]) == 0 ) continue;

polynomial_integer t= polynomial_integer("x")*denominator(lower(isolating_intervals[i])) - numerator( lower(isolating_intervals[i])); std::cout<<t<<" "<<p<<std::endl; polynomial_integer dummy; univariate::div_rem( dummy, p, t); std::cout<<dummy<<std::endl; //p = dummy; } }

Definition at line 352 of file solver_uv_continued_fraction.hpp.

References mmx::degree(), Seq< C, R >::size(), and continued_fraction_subdivision< K >::solve_positive().

Referenced by continued_fraction_subdivision< K >::solve().

00352                                                                {
00353       //      std::cout << __FUNCTION__ << " I "<<f<<std::endl;
00354       Seq < root_t > isolating_intervals;
00355       // Check if 0 is a root
00356       int idx;
00357       for (idx = 0; idx <= degree( f); ++idx) {
00358         if ( f[idx] != 0 ) break;
00359       }
00360 
00361       poly p;
00362       if ( idx == 0 ) { p = f; }
00363       else {
00364         p= poly(1,degree(f) - idx);
00365         for (int j = idx; j <= degree(f); j++)
00366           p[j-idx] = f[j];
00367       }
00368 
00369       // std::cout << "Solving: " << p << std::endl;
00370       // Isolate the negative roots
00371       //    for (int i = 1; i <= degree(p); i+=2) p[i] *= -1;
00372       solve_positive( isolating_intervals, p, false);
00373       // Is 0 a root?
00374       // std::cout << "ok negative" << std::endl;
00375       if (idx != 0) isolating_intervals << root_t( 0, 0);
00376       //    for (int i = 1; i <= degree(p); i+=2) p[i] *= -1;
00377       solve_positive( isolating_intervals, p, true);
00378       // sort( isolating_intervals.begin(), isolating_intervals.end(), CompareFIT());
00379       // std::cout << "ok positive" << std::endl;
00395       // std::cout << "now p: " << p << ",  #nr: " << isolating_intervals.size() << std::endl;
00396 
00397       //      std::cout << "Done...." << std::endl;
00398       for (unsigned i = 0 ; i < isolating_intervals.size(); ++i)
00399         {sol << isolating_intervals[i];}
00400       //    return sol;
00401     }

static void solve_positive ( Seq< root_t > &  sol,
const poly &  f,
bool  posneg 
) [inline, static]

Definition at line 217 of file solver_uv_continued_fraction.hpp.

References IntervalData< RT_, Poly_ >::a, mmx::bound_root(), mmx::degree(), IntervalData< RT_, Poly_ >::p, IntervalData< RT_, Poly_ >::s, mmx::sign_variation(), and continued_fraction_subdivision< K >::solve_homography().

Referenced by continued_fraction_subdivision< K >::solve_polynomial().

00217                                                                  {
00218       //      std::cout << __FUNCTION__ << " "<<f<<" "<<posneg<<std::endl;
00219 
00220       typedef typename K::data IntervalData;
00221 
00222             IntervalData ID(1, 0, 0, 1, f, 0);
00223             if (!posneg)
00224             {
00225                 ID.a=-1;
00226                 for (int i = 1; i <= degree(f); i+=2) ID.p[i] *= -1;
00227             }
00228             ID.s = sign_variation(ID.p);
00229 
00230             if ( K::is_empty(ID) ) { return; }
00231             if ( K::is_good(ID)  ) {
00232                 //std::cout << "A) Sign variation: 1"<<std::endl;;
00233                 FT B = bound_root( f, Cauchy<FT>());
00234                 if ( posneg )
00235                      sol << root_t( FT(0), B);
00236                 else sol << root_t( FT(0), FT(-B));
00237                 return;
00238             }
00239 
00240             solve_homography(sol,ID, poly());
00241     }

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