Package org.ddogleg.solver.impl

Class SturmSequence

java.lang.Object
org.ddogleg.solver.impl.SturmSequence
public class SturmSequence extends Object

A Sturm sequence has the property that the number of sign changes can be used to compute the number of real roots in a polynomial. The Sturm sequence is defined as follows:
[f(x) , deriv(f(x)) , f[0](x) % f[1](x) , ... , f[n-1](x) % f[n](x) ]
where f(x) is the polynomial evaluated at x, deriv computes the derivative relative to x, and f[i](x) refers to function 'i' in the sequence.

An efficient recursive implementation is used, as suggested in [1]. A more detailed description of the algorithm can be found in [2].

[1] David Nister "An Efficient Solution to the Five-Point Relative Pose Problem" Pattern Analysis and Machine Intelligence, 2004
[2] D. Hook, P. McAree, "Using Sturm Sequences to Bracket Real Roots of Polynomial Equations", Graphic Gems I, Academic Press, 416-423, 1990

  • Field Details

    • next

      protected Polynomial next

    • previous

      protected Polynomial previous

    • result

      protected Polynomial result

    • sequence

      protected Polynomial[] sequence

    • sequenceLength

      protected int sequenceLength

    • f

      protected double[] f

  • Constructor Details

    • SturmSequence

      public SturmSequence(int maxPolySize)
      Configures the algorithm.
      Parameters:
      maxPolySize - The maximum number of coefficients on the polynomial being processed.

  • Method Details

    • initialize

      public void initialize(Polynomial poly)
      Compute the Sturm sequence using a more efficient iterative implementation as outlined in [1]. For this formulation to work the polynomial must have 3 or more coefficients.
      Parameters:
      poly - Input polynomial

    • countRealRoots

      public int countRealRoots(double lower, double upper)
      Determines the number of real roots there are in the polynomial within the specified bounds. Must call initialize(Polynomial) first.
      Parameters:
      lower - lower limit on the bound.
      upper - Upper limit on the bound
      Returns:
      Number of real roots

    • countSignChanges

      protected int countSignChanges()
      Looks at the value of each function in the sequence and counts the number of sign changes. Values of zero are simply ignored.
      Returns:
      number of sign changes

    • computeFunctions

      protected void computeFunctions(double value)
      Computes the values for each function in the sequence iterative starting at the end and working its way towards the beginning..