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(x) % f(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 . A more detailed description of the algorithm can be found in .

 David Nister "An Efficient Solution to the Five-Point Relative Pose Problem" Pattern Analysis and Machine Intelligence, 2004
 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 .

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