HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_RootFinder.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: Root finding (C++)
7  *
8  * COMMENTS:
9  *
10  */
11 
12 #ifndef _UT_RootFinder_h_
13 #define _UT_RootFinder_h_
14 
15 #include "UT_API.h"
16 
17 #include "UT_Matrix.h"
18 #include "UT_Vector.h"
19 #include "UT_VectorTypes.h"
20 #include "UT_Complex.h"
21 #include <SYS/SYS_Types.h>
22 
23 template <typename T>
25 {
26 public:
27  // 1D root finders:
28  //
29 
30  // Finds the real roots of a polynomial. The coefficients of the
31  // polynomial are specified in 'cf'. 'cf(i)' should contain the
32  // coefficient for x^i.
33  //
34  // The roots are appended to 'roots'
35  static void laguerre(const UT_ValArray<T> &cf, UT_ValArray<T> &roots,
36  int maxIters = 200);
37 
38  // Returns number of real roots. The roots are found in v0 & v1.
39  // This is quite a stable solver handling many bad cases.
40  //
41  // Note: if a, b and c are all zero, this function will return
42  // zero roots, even though the equation is zero for all values of v.
43  static int quadratic(T a, T b, T c, T &v0, T &v1);
44 
45  // Returns number of real roots but calculates all of the roots,
46  // the real returned in r_roots and imaginary in i_roots
47  static int quadratic(T a, T b, T c,
48  UT_Vector2T<T> &r_roots, UT_Vector2T<T> &i_roots);
49 
50  // Returns number of real roots. The roots are found in v0, v1, & v2.
51  // a*v^3 + b*v^2 + c*v + d = 0
52  //
53  // Note: if a, b, c and d are all zero, this function will return
54  // zero roots, even though the equation is zero for all values of v.
55  static int cubic(T a, T b, T c, T d, T &v0, T &v1, T &v2);
56 
57  // Returns number of real roots. Finds all the roots, however,
58  // real parts in r_roots and imaginary in i_roots
59  //
60  // Note: if a, b, c and d are all zero, this function will return
61  // zero roots, even though the equation is zero for all values of v.
62  static int cubic(T a, T b, T c, T d,
63  UT_Vector3T<T> &r_roots, UT_Vector3T<T> &i_roots);
64 
65  // Returns number of real roots. The user must provide an interval [x1,x2]
66  // which is to contain the roots they're interested in. It is possible that
67  // roots virtually on the end points might be missed, so increase your
68  // interval to compensate.
69  static int cubic(T a, T b, T c, T d, T x1, T x2, T r[3]);
70 
71  // Returns number of real roots. The user must provide an interval [x1,x2]
72  // which is to contain the roots they're interested in. It is possible that
73  // roots virtually on the end points might be missed, so increase your
74  // interval to compensate.
75  static int quartic(T a, T b, T c, T d, T e, T x1, T x2, T r[4]);
76 
77 
78  // No derivative is needed. Root bracketed by [x1,x2].
79  static int brent(T (*func)(T x, void *data), void *data,
80  T x1, T x2, T tol, T &result, int maxIter=200);
81 
82  // Derivative is needed. Root bracketed by [x1,x2].
83  static int newton(void (*func)(T x, T &val, T &der, void *data), void *data,
84  T x1, T x2, T tol, T &result, int maxIter=200);
85 
86  // Multi-dimensional root finders:
87  //
88 
89  // Jacobian is needed. Specify initial guess in result.
90  template <typename S>
91  static int newton(void (*func)(const UT_VectorT<S> &x, UT_VectorT<S> &val, UT_MatrixT<T> &jacobi, void *data),
92  void *data,
93  S tolx, S tolf,
94  UT_VectorT<S> &result, int maxIter=200);
95 
96  // Jacobian is needed. Specify initial guess in result.
97  // [x1,x2] specify the boundary that the func is defined within.
98  template <typename S>
99  static int newton(void (*func)(const UT_VectorT<S> &x, UT_VectorT<S> &val, UT_MatrixT<T> &jacobi, void *data),
100  void *data,
101  const UT_VectorT<S> &x1, const UT_VectorT<S> &x2,
102  S tolx, S tolf,
103  UT_VectorT<S> &result, int maxIter=200);
104 };
105 
110 
111 #endif
UT_RootFinderT< float > UT_RootFinder
UT_RootFinderT< fpreal64 > UT_RootFinderD
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
#define UT_API
Definition: UT_API.h:12
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:817
UT_RootFinderT< fpreal > UT_RootFinderR
3D Vector class.
2D Vector class.
Definition: UT_Vector2.h:137
UT_RootFinderT< fpreal32 > UT_RootFinderF
GLboolean * data
Definition: glcorearb.h:130
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
GLfloat v0
Definition: glcorearb.h:815
GLenum func
Definition: glcorearb.h:782
GLint GLenum GLint x
Definition: glcorearb.h:408
GLfloat GLfloat v1
Definition: glcorearb.h:816
GLuint GLfloat * val
Definition: glcorearb.h:1607
GLboolean r
Definition: glcorearb.h:1221