Package edu.jas.root
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.
Method algebraicRoots()
from class RootFactory
computes both the real and complex algebraic roots of a univariate polynomial.
Method decimalRoots()
computes isolating intervals (or rectangles) for the roots
and then uses a numerical algorithm to get a decimal approximation of the roots.
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 as coefficients.
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: Wed Aug 17 23:32:35 CEST 2016
$Id$
-
Interface Summary Interface Description ComplexRoots<C extends RingElem<C> & Rational> Complex roots interface.RealRoots<C extends RingElem<C> & Rational> Real roots interface. -
Class Summary Class Description AlgebraicRoots<C extends GcdRingElem<C> & Rational> Container for the real and complex algebraic roots of a univariate polynomial.AlgFromRealCoeff<C extends GcdRingElem<C> & Rational> Coefficient to algebraic from real algebraic functor.Boundary<C extends RingElem<C> & Rational> Boundary determined by a rectangle and a polynomial.CoeffToComplex<C extends GcdRingElem<C> & Rational> Coefficient to complex algebraic functor.CoeffToComplexFromComplex<C extends GcdRingElem<C> & Rational> Coefficient to complex algebraic from complex functor.CoeffToReal<C extends GcdRingElem<C> & Rational> Coefficient to real algebraic functor.CoeffToReAlg<C extends GcdRingElem<C> & Rational> Coefficient to algebraic functor.CoeffToRecReAlg<C extends GcdRingElem<C> & Rational> Coefficient to recursive algebraic functor.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 RingFactory interface.ComplexRootsAbstract<C extends RingElem<C> & Rational> Complex roots abstract class.ComplexRootsSturm<C extends RingElem<C> & Rational> Complex roots implemented by Sturm sequences.DecimalRoots<C extends GcdRingElem<C> & Rational> Container for the real and complex algebraic roots of a univariate polynomial.Interval<C extends RingElem<C> & Rational> Interval.PolyToReAlg<C extends GcdRingElem<C> & Rational> Polynomial to algebraic functor.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 RingFactory interface.RealArithUtil Real arithmetic utilities.RealFromAlgCoeff<C extends GcdRingElem<C> & Rational> Coefficient to real algebriac from algebraic functor.RealRootsAbstract<C extends RingElem<C> & Rational> Real roots abstract class.RealRootsSturm<C extends RingElem<C> & Rational> Real root isolation using Sturm sequences.RealRootTuple<C extends GcdRingElem<C> & Rational> RealAlgebraicNumber root tuple.Rectangle<C extends RingElem<C> & Rational> Rectangle.RootFactory Roots factory.RootUtil Real root utilities. -
Exception Summary Exception Description InvalidBoundaryException Invalid boundary exception class.NoConvergenceException No convergence exception class.