001/*
002 * $Id: RealRoots.java 3989 2012-07-14 12:39:14Z kredel $
003 */
004
005package edu.jas.root;
006
007
008import java.io.Serializable;
009import java.util.List;
010
011import edu.jas.arith.Rational;
012import edu.jas.arith.BigRational;
013import edu.jas.poly.GenPolynomial;
014import edu.jas.structure.RingElem;
015import edu.jas.structure.GcdRingElem;
016
017
018/**
019 * Real roots interface.
020 * @param <C> coefficient type.
021 * @author Heinz Kredel
022 */
023public interface RealRoots<C extends RingElem<C> & Rational> extends Serializable {
024
025
026    /**
027     * Real root bound. With f(M) * f(-M) != 0.
028     * @param f univariate polynomial.
029     * @return M such that -M &lt; root(f) &gt; M.
030     */
031    public C realRootBound(GenPolynomial<C> f);
032
033
034    /**
035     * Isolating intervals for the real roots.
036     * @param f univariate polynomial.
037     * @return a list of isolating intervalls for the real roots of f.
038     */
039    public List<Interval<C>> realRoots(GenPolynomial<C> f);
040
041
042    /**
043     * Isolating intervals for the real roots.
044     * @param f univariate polynomial.
045     * @param eps requested intervals length.
046     * @return a list of isolating intervals v such that |v| &lt; eps.
047     */
048    public List<Interval<C>> realRoots(GenPolynomial<C> f, C eps);
049
050
051    /**
052     * Isolating intervals for the real roots.
053     * @param f univariate polynomial.
054     * @param eps requested intervals length.
055     * @return a list of isolating intervals v such that |v| &lt; eps.
056     */
057    public List<Interval<C>> realRoots(GenPolynomial<C> f, BigRational eps);
058
059
060    /**
061     * Sign changes on interval bounds.
062     * @param iv root isolating interval with f(left) * f(right) != 0.
063     * @param f univariate polynomial.
064     * @return true if f(left) * f(right) &lt; 0, else false
065     */
066    public boolean signChange(Interval<C> iv, GenPolynomial<C> f);
067
068
069    /**
070     * Number of real roots in interval.
071     * @param iv interval with f(left) * f(right) != 0.
072     * @param f univariate polynomial.
073     * @return number of real roots of f in I.
074     */
075    public long realRootCount(Interval<C> iv, GenPolynomial<C> f);
076
077
078    /**
079     * Refine interval.
080     * @param iv root isolating interval with f(left) * f(right) &lt; 0.
081     * @param f univariate polynomial, non-zero.
082     * @param eps requested interval length.
083     * @return a new interval v such that |v| &lt; eps.
084     */
085    public Interval<C> refineInterval(Interval<C> iv, GenPolynomial<C> f, C eps);
086
087
088    /**
089     * Refine intervals.
090     * @param V list of isolating intervals with f(left) * f(right) &lt; 0.
091     * @param f univariate polynomial, non-zero.
092     * @param eps requested intervals length.
093     * @return a list of new intervals v such that |v| &lt; eps.
094     */
095    public List<Interval<C>> refineIntervals(List<Interval<C>> V, GenPolynomial<C> f, C eps);
096
097
098    /**
099     * Real algebraic number sign.
100     * @param iv root isolating interval for f, with f(left) * f(right) &lt; 0.
101     * @param f univariate polynomial, non-zero.
102     * @param g univariate polynomial, gcd(f,g) == 1.
103     * @return sign(g(v)), with v a new interval contained in iv such that g(v) !=
104     *         0.
105     */
106    public int realSign(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g);
107
108
109    /**
110     * Real algebraic number magnitude.
111     * @param iv root isolating interval for f, with f(left) * f(right) &lt; 0.
112     * @param f univariate polynomial, non-zero.
113     * @param g univariate polynomial, gcd(f,g) == 1.
114     * @param eps length limit for interval length.
115     * @return g(iv).
116     */
117    public C realMagnitude(Interval<C> iv, GenPolynomial<C> f, GenPolynomial<C> g, C eps);
118
119}