edu.jas.root

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>, java.io.Serializable

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

Real root isolation using Sturm sequences.

Author:

Heinz Kredel

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
RealRootsSturm()

Method Summary

Modifier and Type	Method and Description
Interval<C>	excludeZero(Interval<C> iv, java.util.List<GenPolynomial<C>> S) Exclude zero.
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, java.util.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, java.util.List<GenPolynomial<C>> S) Number of real roots in interval.
java.util.List<Interval<C>>	realRoots(GenPolynomial<C> f) Isolating intervals for the real roots.
java.util.List<Interval<C>>	realRoots(Interval<C> iv, java.util.List<GenPolynomial<C>> S) Isolating intervals for the real roots.
java.util.List<GenPolynomial<C>>	sturmSequence(GenPolynomial<C> f) Sturm sequence.

Methods inherited from class edu.jas.root.RealRootsAbstract

approximateRoot, approximateRoots, bisectionPoint, halfInterval, invariantMagnitudeInterval, isApproximateRoot, isApproximateRoot, isApproximateRoot, magnitudeBound, realIntervalMagnitude, realIntervalSign, realMagnitude, realRootBound, realRoots, realRoots, realSign, refineInterval, refineIntervals, signChange

Methods inherited from class java.lang.Object

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

Constructor Detail

RealRootsSturm

public RealRootsSturm()

Method Detail

sturmSequence

public java.util.List<GenPolynomial<C>> sturmSequence(GenPolynomial<C> f)

Sturm sequence.

Parameters:

f - univariate polynomial.

Returns:

a Sturm sequence for f.

realRoots

public java.util.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 java.util.List<Interval<C>> realRoots(Interval<C> iv,
                                             java.util.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,
                          java.util.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,
                                         java.util.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 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.

excludeZero

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

Exclude zero.

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.