UT/UT_RootFinder.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      David Wong
 *      Side Effects
 *      477 Richmond Street West
 *      Toronto, Ontario
 *      Canada   M5V 3E7
 *      416-504-9876
 *
 * NAME:        Root finding (C++)
 *
 * COMMENTS:
 *
 */

#ifndef _UT_RootFinder_h_
#define _UT_RootFinder_h_

#include "UT_API.h"

#include <SYS/SYS_Types.h>

template<typename T> class UT_VectorT;
typedef UT_VectorT<fpreal64> UT_Vector;
class UT_Matrix;
class UT_Complex;
class UT_FloatArray;
class UT_Vector2;
class UT_Vector3;

class UT_API UT_RootFinder {
public:
    // 1D root finders:
    //

    // Finds the real roots of a polynomial.  The coefficients of the
    // polynomial are specified in 'cf'.  'cf(i)' should contain the
    // coefficient for x^i.
    //
    // The roots are appended to 'roots'
    static void laguerre(const UT_FloatArray &cf, UT_FloatArray &roots,
                        int maxIters = 200);

    // Returns number of real roots.  The roots are found in v0 & v1.
    //  This is quite a stable solver handling many bad cases.
    //
    //  Note: if a, b and c are all zero, this function will return
    //  zero roots, even though the equation is zero for all values of v.
    static int  quadratic(fpreal32 a, fpreal32 b, fpreal32 c,
                            fpreal32 &v0, fpreal32 &v1);
    static int  quadratic(fpreal64 a, fpreal64 b, fpreal64 c,
                            fpreal64 &v0, fpreal64 &v1);

    // Returns number of real roots but calculates all of the roots,
    // the real returned in r_roots and imaginary in i_roots
    static int  quadratic(fpreal32 a, fpreal32 b, fpreal32 c,
                            UT_Vector2 &r_roots, UT_Vector2 &i_roots);

    // Returns number of real roots.  The roots are found in v0, v1, & v2.
    // a*v^3 + b*v^2 + c*v + d = 0
    //
    //  Note: if a, b, c and d are all zero, this function will return
    //  zero roots, even though the equation is zero for all values of v.
    static int  cubic(fpreal a, fpreal b, fpreal c, fpreal d,
                      float &v0, float &v1, float &v2);

    // Returns number of real roots.  Finds all the roots, however,
    // real parts in r_roots and imaginary in i_roots
    //
    //  Note: if a, b, c and d are all zero, this function will return
    //  zero roots, even though the equation is zero for all values of v.
    static int  cubic(fpreal a, fpreal b, fpreal c, fpreal d,
                      UT_Vector3 &r_roots, UT_Vector3 &i_roots);

    // Returns number of real roots.  The user must provide an interval [x1,x2]
    // which is to contain the roots they're interested in.  It is possible that
    // roots virtually on the end points might be missed, so increase your
    // interval to compensate.
    static int  cubic(fpreal a, fpreal b, fpreal c, fpreal d,
                      float x1, float x2, float r[3]);

    // Returns number of real roots.  The user must provide an interval [x1,x2]
    // which is to contain the roots they're interested in.  It is possible that
    // roots virtually on the end points might be missed, so increase your
    // interval to compensate.
    static int  quartic(fpreal a, fpreal b, fpreal c, fpreal d, fpreal e,
                      float x1, float x2, float r[4]);


    // No derivative is needed. Root bracketed by [x1,x2].
    int brent(float (*func)(float x, void *data), 
              void *data,
              fpreal x1, fpreal x2, 
              fpreal tol, float &result, int maxIter=200);

    // Derivative is needed. Root bracketed by [x1,x2].
    int newton(void (*func)(float x, float &val, float &der, void *data), 
               void *data,
               float x1, float x2,
               float tol, float &result, int maxIter=200);

    // Multi-dimensional root finders:
    //

    // Jacobian is needed. Specify initial guess in result.
    int newton(void (*func)(const UT_Vector &x, UT_Vector &val, UT_Matrix &jacobi, void *data),
               void *data,
               float tolx, float tolf,
               UT_Vector &result, int maxIter=200);

    // Jacobian is needed. Specify initial guess in result.
    // [x1,x2] specify the boundary that the func is defined within.
    int newton(void (*func)(const UT_Vector &x, UT_Vector &val, UT_Matrix &jacobi, void *data),
               void *data,
               const UT_Vector &x1, const UT_Vector &x2,
               float tolx, float tolf,
               UT_Vector &result, int maxIter=200);
};

#endif

---