Class RealRootsSturm<C extends RingElem<C> & Rational>

java.lang.Object

edu.jas.root.RealRootsAbstract<C>

edu.jas.root.RealRootsSturm<C>

Type Parameters:

C - coefficient type.

All Implemented Interfaces:

RealRoots<C>, Serializable

public class RealRootsSturm<C extends RingElem<C> & Rational>
extends RealRootsAbstract<C>

Real root isolation using Sturm sequences.

See Also:

• Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
private static final boolean	debug
private static final org.apache.logging.log4j.Logger	logger

Constructor Summary

Constructors

Constructor	Description
RealRootsSturm()

Method Summary

Modifier and Type	Method	Description
Interval<C>	excludeZero(Interval<C> iv, List<GenPolynomial<C>> S)	Exclude zero v2.
Interval<C>	excludeZeroOld(Interval<C> iv, List<GenPolynomial<C>> S)	Exclude zero, old version.
Interval<C>	invariantSignInterval(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g)	Invariant interval for algebraic number sign.
Interval<C>	invariantSignInterval(Interval<C> iv, GenPolynomial<C> f, List<GenPolynomial<C>> Sg)	Invariant interval for algebraic number sign.
long	realRootCount(Interval<C> iv, GenPolynomial<C> f)	Number of real roots in interval.
long	realRootCount(Interval<C> iv, List<GenPolynomial<C>> S)	Number of real roots in interval.
List<Interval<C>>	realRoots(GenPolynomial<C> f)	Isolating intervals for the real roots.
List<Interval<C>>	realRoots(Interval<C> iv, List<GenPolynomial<C>> S)	Isolating intervals for the real roots.
List<GenPolynomial<C>>	sturmSequence(GenPolynomial<C> f)	Sturm sequence.

Methods inherited from class RealRootsAbstract

approximateRoot, approximateRoots, bisectionPoint, fourierSequence, halfInterval, invariantMagnitudeInterval, isApproximateRoot, isApproximateRoot, isApproximateRoot, magnitudeBound, realIntervalMagnitude, realIntervalMagnitudeInterval, realIntervalSign, realMagnitude, realMinimalRootBound, realMinimalRootSeparation, realRootBound, realRootNumber, realRoots, realRoots, realSign, refineInterval, refineIntervals, signChange, signSequence

Methods inherited from class Object

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

Field Details

logger

private static final org.apache.logging.log4j.Logger logger

debug

private static final boolean debug

Constructor Details

RealRootsSturm

public RealRootsSturm()

Method Details

sturmSequence

public List<GenPolynomial<C>> sturmSequence(GenPolynomial<C> f)

Sturm sequence.

Parameters:

f - univariate polynomial.

Returns:

a Sturm sequence for f.

realRoots

public List<Interval<C>> realRoots(GenPolynomial<C> f)

Isolating intervals for the real roots.

Specified by:

realRoots in interface RealRoots<C extends RingElem<C> & Rational>

Specified by:

realRoots in class RealRootsAbstract<C extends RingElem<C> & Rational>

Parameters:

f - univariate polynomial.

Returns:

a list of isolating intervals for the real roots of f.

realRoots

public List<Interval<C>> realRoots(Interval<C> iv,
 List<GenPolynomial<C>> S)

Isolating intervals for the real roots.

Parameters:

iv - interval with f(left) * f(right) != 0.

S - sturm sequence for f and I.

Returns:

a list of isolating intervals for the real roots of f in I.

realRootCount

public long realRootCount(Interval<C> iv,
 List<GenPolynomial<C>> S)

Number of real roots in interval.

Parameters:

iv - interval with f(left) * f(right) != 0.

S - sturm sequence for f and I.

Returns:

number of real roots of f in I.

realRootCount

public long realRootCount(Interval<C> iv,
 GenPolynomial<C> f)

Number of real roots in interval.

Specified by:

realRootCount in interface RealRoots<C extends RingElem<C> & Rational>

Specified by:

realRootCount in class RealRootsAbstract<C extends RingElem<C> & Rational>

Parameters:

iv - interval with f(left) * f(right) != 0.

f - univariate polynomial.

Returns:

number of real roots of f in I.

invariantSignInterval

public Interval<C> invariantSignInterval(Interval<C> iv,
 GenPolynomial<C> f,
 GenPolynomial<C> g)

Invariant interval for algebraic number sign.

Specified by:

invariantSignInterval in class RealRootsAbstract<C extends RingElem<C> & Rational>

Parameters:

iv - root isolating interval for f, with f(left) * f(right) < 0.

f - univariate polynomial, non-zero.

g - univariate polynomial, gcd(f,g) == 1.

Returns:

v with v a new interval contained in iv such that g(w) != 0 for w in v.

invariantSignInterval

public Interval<C> invariantSignInterval(Interval<C> iv,
 GenPolynomial<C> f,
 List<GenPolynomial<C>> Sg)

Invariant interval for algebraic number sign.

Parameters:

iv - root isolating interval for f, with f(left) * f(right) < 0.

f - univariate polynomial, non-zero.

Sg - Sturm sequence for (f,g), a univariate polynomial with gcd(f,g) == 1.

Returns:

v with v a new interval contained in iv such that g(w) != 0 for w in v.

excludeZeroOld

public Interval<C> excludeZeroOld(Interval<C> iv,
 List<GenPolynomial<C>> S)

Exclude zero, old version.

Parameters:

iv - root isolating interval with f(left) * f(right) < 0.

S - sturm sequence for f and I.

Returns:

a new interval v such that v < 0 or v > 0.

excludeZero

public Interval<C> excludeZero(Interval<C> iv,
 List<GenPolynomial<C>> S)

Exclude zero v2.

Parameters:

iv - root isolating interval with f(left) * f(right) < 0.

S - sturm sequence for f and I.

Returns:

a new interval v such that v < 0 or v > 0 or v == 0.