solver_cffirst< Real, POL > Struct Template Reference

#include <solver_ucf.hpp>

List of all members.

Public Member Functions

Public Attributes

Detailed Description

template<class Real, class POL>
struct mmx::solver_cffirst< Real, POL >

Definition at line 210 of file solver_ucf.hpp.

Constructor & Destructor Documentation

solver_cffirst ( interval_rep< POL >  p  )  [inline]

Definition at line 215 of file solver_ucf.hpp.

References solver_cffirst< Real, POL >::eps, and solver_cffirst< Real, POL >::ir.

00215                                            {
00216             ir = p;
00217             eps= as<Real>(1e-7);
00218         }

Member Function Documentation

Seq< interval_rep< POL > > all_roots (  )  [inline]

Definition at line 321 of file solver_ucf.hpp.

References mmx::assign(), BOX, C, solver_cffirst< Real, POL >::eps, solver_cffirst< Real, POL >::ir, mmx::lower(), AkritasBound< RT >::lower_bound(), N_ITER, POL, and Real.

Referenced by solver_cffirst< Real, POL >::all_roots_isolate().

00322   {
00323     typedef interval_rep<POL> BOX;
00324     std::stack<BOX * > uboxes;
00325     typedef typename POL::scalar_t C;
00326 
00327     Real ev(0);
00328     Seq<interval_rep<POL> > sols;
00329     POL zero(0);
00330     Interval<Real> mid(0);
00331     BOX * b, * tmp;
00332     POL p;
00333     unsigned s, iters=0;
00334         
00335     Interval<Real> I;
00336     AkritasBound<C> lb;
00337     //HongBound<C> lb; 
00338     //Kioustelidis<C> lb; 
00339     //NISP<C> lb; 
00340     //Cauchy<C> lb; 
00341     
00342     C lower;
00343     b= new BOX(ir);
00344     uboxes.push (b);
00345     
00346     while ( !uboxes.empty() && iters++ < N_ITER )
00347     {
00348       b = uboxes.top() ;
00349       p = b->poly() ;
00350       uboxes.pop();
00351       
00352       if ( p==zero && (!uboxes.empty()) ) {
00353         sols<< *b;}
00354       
00355       I = b->template domain<Real>();
00356       // Interval<Real> ev= p( I ) ;
00357       // if ( ev.m * ev.M > 0  ) continue;
00358       s = b->sign_var() ;
00359       if ( s==1 && (!uboxes.empty()) ) {
00360         sols << *b; continue; }
00361       
00362       if ( s > 0 ) 
00363       {
00364         if ( (!uboxes.empty())  && b->template width<Real>() < eps*.1 )
00365         {std::cout<<
00366             "all_roots: multiple root?"<<b->template domain<Real>() <<std::endl; 
00367           std::cout<< b->poly()<<" , "<<b->template width<Real>()<<std::endl;
00368           std::cout<<"source: "<<ir.poly()<<std::endl;
00369 
00370         }
00371         else
00372         {
00373           lower= lb.lower_bound(p) ;
00374           if ( lower!=0 )
00375           {
00376             
00377             let::assign(ev,lower);
00378             if ( p(ev) == 0 )
00379               sols<< *b;
00380             
00381             tmp= new BOX( *b ) ;
00382             free(b);
00383             tmp->shift_box( lower );
00384             uboxes.push (tmp);
00385           }                     
00386           else
00387           {
00388             // right box
00389             tmp = new BOX( *b ) ;
00390             tmp->shift_box( 1 );
00391             uboxes.push ( tmp );                        
00392             //middle if needed
00393             ev=1;
00394             if ( p( ev ) == Real(0) )
00395             {   tmp = new BOX(zero, b->hom() ) ;
00396               uboxes.push ( tmp ); }
00397             //left
00398             tmp = new BOX( *b ) ;
00399             tmp->reverse_and_shift_box( 1 );
00400             tmp->reverse_box( 1 );
00401             uboxes.push ( tmp );
00402             
00403             free(b);
00404           }
00405         }
00406       }
00407     }
00408     return sols;
00409   }

Seq< Interval< Real > > all_roots_isolate (  )  [inline]

Definition at line 519 of file solver_ucf.hpp.

References solver_cffirst< Real, POL >::all_roots(), POL, and Seq< C, R >::size().

Referenced by solver_cffirst< Real, POL >::all_roots_separate(), solver< Ring, CFdecide >::solve(), and solver< Ring, CFallIsolate >::solve().

00520     {
00521         Seq<interval_rep<POL> > a( all_roots() );
00522         Seq<Interval<Real> > s;
00523         typename POL::scalar_t t(1);
00524 
00525         for ( unsigned i=0; i<a.size(); ++i)
00526             if (a[i].poly()==POL(0) ) 
00527                 s<< Interval<Real>(a[i].template point<Real>(t) );
00528             else
00529                 s<< a[i].template domain<Real>();
00530 
00531         return s;
00532     }

Seq< Real > all_roots_separate (  )  [inline]

Definition at line 535 of file solver_ucf.hpp.

References solver_cffirst< Real, POL >::all_roots_isolate(), Real, and Seq< C, R >::size().

Referenced by solver< Ring, CFseparate >::solve().

00536     {
00537         Seq< Interval<Real> > ints;
00538         Seq<Real> sep;
00539         
00540         ints= all_roots_isolate();
00541         for (unsigned i=1; i<ints.size(); ++i)
00542             sep << (ints[i-1].M + ints[i].m)*Real(0.5) ;
00543 
00544         return sep;
00545     }

interval_rep< POL > first_root (  )  [inline]

Definition at line 235 of file solver_ucf.hpp.

References BOX, C, solver_cffirst< Real, POL >::eps, solver_cffirst< Real, POL >::ir, mmx::lower(), AkritasBound< RT >::lower_bound(), N_ITER, POL, and Real.

Referenced by solver_cffirst< Real, POL >::first_root_approximate(), solver_cffirst< Real, POL >::first_root_floor(), and solver_cffirst< Real, POL >::first_root_isolate().

00236     {
00237         typedef interval_rep<POL> BOX;
00238         std::stack<BOX * > uboxes;
00239         typedef typename POL::scalar_t C;
00240         
00241         POL zero(0);
00242         Interval<Real> mid(0);
00243         BOX * b, * tmp;
00244         POL p;
00245         unsigned s, iters=0;
00246         
00247         Interval<Real> I;
00248         AkritasBound<C> lb;
00249         //HongBound<C> lb; 
00250         //Kioustelidis<C> lb; 
00251         //NISP<C> lb; 
00252         //Cauchy<C> lb; 
00253         
00254         C lower;
00255         b= new BOX(ir);
00256         uboxes.push (b);
00257         
00258         while ( !uboxes.empty() && iters++ < N_ITER )
00259             
00260         {
00261             b = uboxes.top() ;
00262             p = b->poly() ;
00263             uboxes.pop();
00264             
00265             if ( p==zero && (!uboxes.empty()) ) {
00266                 return *b;}
00267             
00268             s = b->sign_var() ;
00269             I = b->template domain<Real>();
00270             
00271             if ( s==1 && (!uboxes.empty()) ) {
00272                 return *b;}
00273             
00274             if ( s > 0 ) 
00275             {
00276                 if ( b->template width<Real>() < eps )
00277                 {std::cout<< "first_root: multiple root?"<<b->template domain<Real>() <<std::endl;}
00278                 else
00279                 {
00280                     lower= lb.lower_bound(p) ;
00281                     if ( lower!=0 )
00282                     {
00283                         if ( p( lower ) == 0 )
00284                             return *b;
00285                         
00286                         tmp= new BOX( *b ) ;
00287                         free(b);
00288                         tmp->shift_box( lower );
00289                         uboxes.push (tmp);
00290                     }
00291                     else
00292                     {
00293                         // right box
00294                         tmp = new BOX( *b ) ;
00295                         tmp->shift_box( 1 );
00296                         uboxes.push ( tmp );                    
00297                         //middle if needed
00298                         if ( p( Real(1) ) == Real(0) )
00299                         {   tmp = new BOX(zero, b->hom() ) ;
00300                             uboxes.push ( tmp ); }
00301                         //left
00302                         tmp = new BOX( *b ) ;
00303                         tmp->reverse_and_shift_box( 1 );
00304                         tmp->reverse_box( 1 );
00305                         uboxes.push ( tmp );
00306                         
00307                         free(b);
00308                     }
00309                 }
00310             }
00311         }
00312         /* -1 = No positive root */
00313         return BOX(-1);
00314     }

Real first_root_approximate (  )  [inline]

Definition at line 430 of file solver_ucf.hpp.

References BOX, C, solver_cffirst< Real, POL >::eps, solver_cffirst< Real, POL >::first_root(), POL, and Real.

Referenced by solver< Ring, CFfirstApproximate >::solve().

00431     {
00432         typedef interval_rep<POL> BOX;
00433         typedef typename POL::scalar_t C;
00434         BOX * l, * r= new BOX( first_root() ) ;
00435         C t(1);
00436         
00437         if ( r->poly()== POL(-1) ) 
00438             return (0);
00439         else 
00440             if (r->poly()==POL(0) ) 
00441                 return( r->template point<Real>(t) );
00442         else
00443         {
00444             /* Approximate */
00445             while ( r->template width<Real>() > eps )
00446             {
00447                 t= r->middle();
00448                 
00449                 if ( r->poly()( t ) == 0 ) return( r->template point<Real>(t) );
00450                 l= new BOX( *r) ;
00451                 l->shift_box( t );
00452                 
00453                 if ( l->sign_var() ) 
00454                 {   
00455                     free(r);
00456                     r=l; 
00457                     continue;
00458                 }
00459                 else 
00460                 {   
00461                     free(l);
00462                     r->contract_box(t);
00463                     r->reverse_and_shift_box(1);
00464                     r->reverse_box(1);
00465                 }  
00466             }
00467             
00468             return ( r->template domain<Real>() );
00469         }
00470     }

Real first_root_floor (  )  [inline]

Definition at line 473 of file solver_ucf.hpp.

References BOX, C, solver_cffirst< Real, POL >::first_root(), floor(), Interval< T, r >::M, Interval< T, r >::m, POL, Real, and mmx::rfloor().

Referenced by solver< Ring, CFfirstFloor >::solve().

00474     {
00475         typedef interval_rep<POL> BOX;
00476         typedef typename POL::scalar_t C;
00477 
00478         BOX * l, * r= new BOX( first_root() ) ;
00479         Interval<Real> I;
00480         C t(1);
00481         if ( r->poly()== POL(-1) ) 
00482             return (0);
00483         else 
00484             if (r->poly()==POL(0) ) 
00485                 return( r->template point<Real>(t) );
00486             else
00487             {
00488                 
00489                 I= r->template domain<Real>();
00490                 if ( r->poly() == POL(0) ) return as<Real> (floor(as<double>(r->template point<Real>(t))) );
00491                 while ( rfloor(I.m)!=rfloor(I.M) )
00492                 {
00493                     t= r->middle();
00494                     if ( r->poly()( t ) == 0 ) return as<Real>( floor(as<double>(r->template point<Real>(t))) ); 
00495                     
00496                     l= new BOX( *r) ;
00497                     l->shift_box( t );
00498                     
00499                     if ( l->sign_var() ) 
00500                     {   
00501                         free(r);
00502                         r=l; 
00503                         I= r->template domain<Real>(); 
00504                         continue;
00505                     }
00506                     else 
00507                     {   
00508                         free(l);
00509                         r->reverse_and_shift_box();
00510                         r->reverse_box();
00511                         I= r->template domain<Real>();
00512                     }  
00513                 }
00514             }
00515         return as<Real>( floor(as<double>(I.m)) );
00516     }/*first_root_floor*/

Interval< Real > first_root_isolate (  )  [inline]

Definition at line 415 of file solver_ucf.hpp.

References solver_cffirst< Real, POL >::first_root(), POL, and interval_rep< POL >::poly().

Referenced by solver< Ring, CFfirstIsolate >::solve().

00416     {
00417         interval_rep<POL> a( first_root() );
00418         typename POL::scalar_t t(1);
00419         
00420         if ( a.poly()== POL(-1) ) 
00421             return (0);
00422         else 
00423             if (a.poly()==POL(0) ) 
00424                 return( a.template point<Real>(t) );
00425         else
00426             return ( a.template domain<Real>() );
00427     }

Member Data Documentation

Real eps

Definition at line 213 of file solver_ucf.hpp.

Referenced by solver_cffirst< Real, POL >::all_roots(), solver_cffirst< Real, POL >::first_root(), solver_cffirst< Real, POL >::first_root_approximate(), and solver_cffirst< Real, POL >::solver_cffirst().

interval_rep<POL> ir

Definition at line 212 of file solver_ucf.hpp.

Referenced by solver_cffirst< Real, POL >::all_roots(), solver_cffirst< Real, POL >::first_root(), and solver_cffirst< Real, POL >::solver_cffirst().

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