edu.jas.root
Class RealRootsSturm<C extends RingElem<C> & Rational>

java.lang.Object
  edu.jas.root.RealRootAbstract<C>
      edu.jas.root.RealRootsSturm<C>

Type Parameters:

C - coefficient type.

All Implemented Interfaces:

RealRoots<C>

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

Real root isolation using Sturm sequences.

Author:

Heinz Kredel

Constructor Summary

RealRootsSturm()

Method Summary

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

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