Package edu.jas.root

Real and Complex Root Computation package.

See:
Description

Interface Summary

ComplexRoots<C extends RingElem<C> & Rational>	Complex roots interface.
RealRoots<C extends RingElem<C> & Rational>	Real roots interface.

Class Summary

Boundary<C extends RingElem<C> & Rational>	Boundary determined by a rectangle and a polynomial.
ComplexAlgebraicNumber<C extends GcdRingElem<C> & Rational>	Complex algebraic number class based on AlgebraicNumber.
ComplexAlgebraicRing<C extends GcdRingElem<C> & Rational>	Complex algebraic number factory class based on AlgebraicNumberRing with RingElem interface.
ComplexAlgebraicTest	ComplexAlgebraicNumber Test using JUnit.
ComplexRootsAbstract<C extends RingElem<C> & Rational>	Complex roots abstract class.
ComplexRootsSturm<C extends RingElem<C> & Rational>	Complex roots implemented by Sturm sequences.
ComplexRootTest	RootUtil tests with JUnit.
Interval<C extends RingElem<C> & Rational>	Interval.
PolyUtilRoot	Polynomial utilities related to real and complex roots.
RealAlgebraicNumber<C extends GcdRingElem<C> & Rational>	Real algebraic number class based on AlgebraicNumber.
RealAlgebraicRing<C extends GcdRingElem<C> & Rational>	Real algebraic number factory class based on AlgebraicNumberRing with RingElem interface.
RealAlgebraicTest	RealAlgebraicNumber Test using JUnit.
RealRootAbstract<C extends RingElem<C> & Rational>	Real roots abstract class.
RealRootsSturm<C extends RingElem<C> & Rational>	Real root isolation using Sturm sequences.
RealRootTest	RealRoot tests with JUnit.
RealRootTuple<C extends GcdRingElem<C> & Rational>	RealAlgebraicNumber root tuple.
Rectangle<C extends RingElem<C> & Rational>	Rectangle.
RootFactory	Roots factory.
RootUtil	Real root utilities.
RootUtilTest	RootUtil tests with JUnit.

Exception Summary

InvalidBoundaryException	Invalid boundary exception class.
NoConvergenceException	No convergence exception class.

Package edu.jas.root Description

Real and Complex Root Computation package.

This package contains classes for the computation of isolating and refining intervals of real roots and complex roots of univariate polynomials.

For the computation of real roots the main interface is RealRoots and main implementing class is RealRootsSturm. The implementation follows in part section 8.8 "Computation of real zeroes of Polynomial Systems" in Gröbner Bases, A computational Approach to Commutative Algebra, by Becker et al.
The class RealAlgebraicNumber is based on AlgebraicNumber with factory class RealAlgebraicRing based on AlgebraicNumberRing. They implement real algebraic numbers, which are algebraic numbers plus an isolating interval for a real root of the generator. RealRootsSturm can be applied to polynomials with real algebraic numbers.

For the computation of complex roots the main interface is ComplexRoots and the main implementing class is ComplexRootsSturm. The implementation provides an exact infallible method which follows the numeric method of Wilf (see Wilf: A global bisection algorithm for computing the zeros of polynomials in the complex plane). It uses Sturm sequences following the Routh-Hurwitz Method to count the number of complex roots within a rectangle in the complex plane. For a (eventually) more efficient method see: Collins and Krandick: An efficient algorithm for infallible polynomial complex root isolation, in ISSAC'92.

Heinz Kredel

Last modified: Sun Dec 20 22:33:25 CET 2009

$Id: package.html 2910 2009-12-20 21:34:00Z kredel $