org.ddogleg.solver.impl

Class SturmSequence

java.lang.Object

org.ddogleg.solver.impl.SturmSequence

public class SturmSequence
extends java.lang.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

Constructor Summary

Constructors

Constructor and Description
SturmSequence(int maxPolySize) Configures the algorithm.

Method Summary

Modifier and Type	Method and Description
int	countRealRoots(double lower, double upper) Determines the number of real roots there are in the polynomial within the specified bounds.
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

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SturmSequence

public SturmSequence(int maxPolySize)

Configures the algorithm.

Parameters:

maxPolySize - The maximum number of coefficients on the polynomial being processed.

Method Detail

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