Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

NUM::PolyRootSolver_Sturm Class Reference

Polynomial root solver based on the Sturm series of polynoms. More...

#include <rootsolve.h>

Inheritance diagram for NUM::PolyRootSolver_Sturm:

Inheritance graph
[legend]
Collaboration diagram for NUM::PolyRootSolver_Sturm:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 PolyRootSolver_Sturm ()
 ~PolyRootSolver_Sturm ()
int solve (int order, const dbl *c, dbl *r)

Public Attributes

Params par

Static Public Attributes

const Params defaults
 Default values of the parameters.


Private Member Functions

int modrf (int ord, dbl *coef, dbl a, dbl b, dbl *val)
int modp (poly *u, poly *v, poly *r)
int buildsturm (int ord, poly *sseq)
int numroots (int np, poly *sseq, int *atneg, int *atpos)
int numchanges (int np, poly *sseq, dbl a)
int sbisect (int np, poly *sseq, dbl min, dbl max, int atmin, int atmax, dbl *roots)

Detailed Description

Polynomial root solver based on the Sturm series of polynoms.

Author:
Wolfgang Wieser ] wwieser (a) gmx <*> de [, based upon:SturmSequences.c, Using Sturm Sequences to Bracket Real Roots of Polynomial Equations by D.G. Hook and P.R. McAree from "Graphics Gems", Academic Press, 1990.
This class implements a polynomial root solver based on the Sturm series of polynoms.

This class is completely thread-save; several threads may execute the solve() function at the same time.

Definition at line 113 of file rootsolve.h.

Constructor & Destructor Documentation

NUM::PolyRootSolver_Sturm::PolyRootSolver_Sturm (   ) 
 

Definition at line 543 of file sturm.cc.

NUM::PolyRootSolver_Sturm::~PolyRootSolver_Sturm (   ) 
 

Definition at line 550 of file sturm.cc.

Member Function Documentation

int NUM::PolyRootSolver_Sturm::buildsturm (  int  ord,
poly *  sseq
)  [private]
 

For internal use only.

Build Sturm sequence.

Definition at line 167 of file sturm.cc.

References NUM::PolyRootSolver_Sturm::poly::coef, dbl, NUM::fabs(), modp(), and NUM::PolyRootSolver_Sturm::poly::ord.

Referenced by solve().

int NUM::PolyRootSolver_Sturm::modp (  poly *  u,
poly *  v,
poly *  r
)  [private]
 

For internal use only.

Polynomial modulus.

Definition at line 121 of file sturm.cc.

References NUM::PolyRootSolver_Sturm::poly::coef, dbl, NUM::fabs(), NUM::PolyRootSolver_Sturm::Params::nearly_zero, NUM::PolyRootSolver_Sturm::poly::ord, and par.

Referenced by buildsturm().

int NUM::PolyRootSolver_Sturm::modrf (  int  ord,
dbl *  coef,
dbl  a,
dbl  b,
dbl *  val
)  [private]
 

For internal use only.

Modified regula falsa.

Definition at line 51 of file sturm.cc.

References dbl, NUM::fabs(), NUM::PolyRootSolver_Sturm::Params::modrf_maxit, par, and NUM::PolyRootSolver_Sturm::Params::relerror.

Referenced by sbisect().

int NUM::PolyRootSolver_Sturm::numchanges (  int  np,
poly *  sseq,
dbl  a
)  [private]
 

For internal use only.

Return the number of sign changes in the Sturm sequence.

Definition at line 296 of file sturm.cc.

References NUM::PolyRootSolver_Sturm::poly::coef, dbl, NUM::PolyRootSolver_Sturm::poly::ord, and NUM::PolvEval().

Referenced by sbisect(), and solve().

int NUM::PolyRootSolver_Sturm::numroots (  int  np,
poly *  sseq,
int *  atneg,
int *  atpos
)  [private]
 

For internal use only.

Return the number of distinct real roots.

Definition at line 201 of file sturm.cc.

References NUM::PolyRootSolver_Sturm::poly::coef, dbl, and NUM::PolyRootSolver_Sturm::poly::ord.

Referenced by solve().

int NUM::PolyRootSolver_Sturm::sbisect (  int  np,
poly *  sseq,
dbl  min,
dbl  max,
int  atmin,
int  atmax,
dbl *  roots
)  [private]
 

For internal use only.

Uses a bisection to isolate intervals in which roots occur.

Definition at line 344 of file sturm.cc.

References Assert, NUM::PolyRootSolver_Sturm::poly::coef, dbl, NUM::fabs(), NUM::max(), NUM::min(), modrf(), numchanges(), NUM::PolyRootSolver_Sturm::poly::ord, par, NUM::PolvEval(), NUM::PolyRootSolver_Sturm::Params::relerror, and NUM::PolyRootSolver_Sturm::Params::sbisect_maxit.

Referenced by solve().

int NUM::PolyRootSolver_Sturm::solve (  int  order,
const dbl *  c,
dbl *  r
)  [virtual]
 

[overriding a virtual]; Actually solve the roots of the polynomial using the Sturm sequence. Returns the number of roots; the roots will be returned in r[0..<=n-1]. c[0..n] holds the coefficiants of the polynomial
c[0] + c[1]*x + c[2]*x^2 + ... + c[n]*x^n
...whereas n=order.

Todo:
fix sturm root solver: brackets / borders!

#warning THIS IS FLAWED...

Reimplemented from NUM::PolyRootSolver.

Definition at line 462 of file sturm.cc.

References Assert, buildsturm(), NUM::PolyRootSolver_Sturm::poly::coef, dbl, NUM::max(), MAXPOW, NUM::min(), numchanges(), numroots(), NUM::PolyRootSolver_Sturm::poly::ord, and sbisect().

Member Data Documentation

const PolyRootSolver_Sturm::Params NUM::PolyRootSolver_Sturm::defaults [static]
 

Initial value:

 
{
    
    
    INIT_FIELD(nearly_zero) 1.0e-10,  
    INIT_FIELD(relerror) 1.0e-14,
    INIT_FIELD(sbisect_maxit) 64,
    INIT_FIELD(modrf_maxit) 64,
}
Default values of the parameters.

Definition at line 32 of file sturm.cc.

Params NUM::PolyRootSolver_Sturm::par
 

Definition at line 128 of file rootsolve.h.

Referenced by modp(), modrf(), and sbisect().

The documentation for this class was generated from the following files:
Generated on Sat Feb 19 22:35:59 2005 for Ray by doxygen 1.3.5