ASRootIsolation.mesa
Last Edited by Arnon: November 27, 1987 10:49:49 am PST
Routines for isolation of the real roots of individual, or sets of, univariate polynomials over some real (complete, ordered, characteristic zero) field. As much as possible, the algorithms should be generic (independent of the particular field).
Although other forms may be accepted as input, individual polynomials actually dealt with internally are either primitive, positive squarefree integral polynomials, or monic squarefree polynomials over a (real) algebraic number field.
In fact, there should be input routines that allow mixed sets of arbitrary integral, rational, and algebraic polynomials, and convert them to one of the desired forms.
Sets of input polynomials actually dealt with internally are maintained as (squarefree) bases of polynomials, all elements being in one of the above two forms.
Key additional routines are the refinement routines, i.e. the ability to refine an existing isolation list by one or more new input polynomials. The output rep of such a refinement should distinguish new from old roots, e.g. it may be a revised isolation list (with narrower intervals) for the old polynomials, plus an isolation list for the new polynomials, plus specification for each root of the new list of which old roots it is between, or which old root it is equal to.
DIRECTORY
Rope,
AlgebraClasses;
ASRootIsolation: CEDAR DEFINITIONS
~ BEGIN
StronglyDisjointIntervalsSeq: TYPE = REF StronglyDisjointIntervalsSeqRec;
StronglyDisjointIntervalsSeqRec:
TYPE =
RECORD
[
SEQUENCE lengthPlus1: [1..4096]
OF RatIntervals.RatInterval];
Each interval has binary rational endpoints and is either left-open and right-closed, or a one-point interval.
RatApproxRoot:
PROC [poly:
POL.Polynomial, isolatingInterval:
RI.RatInterval, ratApproxBound:
RN.RatNum, coeffRing:
AC.Ring]
RETURNS [
RN.RatNum];
Return a rational approximation to the unique root of poly in isolatingInterval, accurate to within ratApproxBound. Should have the property that always produces the same RatNum for given inputs.
ModUspenskyRoots:
PROC [poly:
POL.Polynomial, coeffRing:
AC.Ring]
RETURNS [StronglyDisjointIntervalsSeq];
Isolate the roots of a univariate polynomial. We don't assume that it's monic or squarefree.
1. Make monic and sqfree.
2. Call ModUspenskyRootsSFPoly.
ModUspenskyRootsSFPoly:
PROC [monicSFPoly:
POL.Polynomial, coeffRing:
AC.Ring]
RETURNS [StronglyDisjointIntervalsSeq];
Isolate the roots of a monic squarefree univariate polynomial.
NumberRootsInOpenInterval:
PROC [poly:
POL.Polynomial, openInterval:
RI.RatInterval, coeffRing:
AC.Ring]
RETURNS [nRoots:
CARDINAL];
nRoots is the number of real roots which poly has in openInterval.
END.