Class 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.
      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.
      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.
      lower - lower limit on the bound.
      upper - Upper limit on the bound
      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.
      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..