# 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 Summary

Fields
Modifier and Type Field Description
`protected double[]` `f`
`protected Polynomial` `next`
`protected Polynomial` `previous`
`protected Polynomial` `result`
`protected Polynomial[]` `sequence`
`protected int` `sequenceLength`
• ## Constructor Summary

Constructors
Constructor Description
`SturmSequence​(int maxPolySize)`
Configures the algorithm.
• ## Method Summary

Modifier and Type Method Description
`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..
`int` ```countRealRoots​(double lower, double upper)```
Determines the number of real roots there are in the polynomial within the specified bounds.
`protected int` `countSignChanges()`
Looks at the value of each function in the sequence and counts the number of sign changes.
`void` `initialize​(Polynomial poly)`
Compute the Sturm sequence using a more efficient iterative implementation as outlined in [1].

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ## Field Details

• ### next

protected Polynomial next
• ### previous

protected Polynomial previous
• ### result

protected Polynomial result
• ### sequence

protected  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..