001/*
002 * $Id: RootFactory.java 3974 2012-07-01 12:29:44Z kredel $
003 */
004
005package edu.jas.root;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.Set;
011import java.util.Map;
012
013import edu.jas.arith.Rational;
014import edu.jas.arith.BigRational;
015import edu.jas.poly.Complex;
016import edu.jas.poly.ComplexRing;
017import edu.jas.poly.PolyUtil;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.structure.GcdRingElem;
021import edu.jas.ufd.FactorAbstract;
022import edu.jas.ufd.FactorFactory;
023import edu.jas.ufd.SquarefreeAbstract;
024import edu.jas.ufd.SquarefreeFactory;
025
026
027/**
028 * Roots factory.
029 * @author Heinz Kredel
030 */
031public class RootFactory {
032
033
034    /**
035     * Is real algebraic number a root of a polynomial.
036     * @param f univariate polynomial.
037     * @param r real algebraic number.
038     * @return true, if f(r) == 0, else false;
039     */
040    public static <C extends GcdRingElem<C> & Rational> 
041           boolean isRoot(GenPolynomial<C> f, RealAlgebraicNumber<C> r) {
042        RealAlgebraicRing<C> rr = r.factory(); 
043        GenPolynomialRing<RealAlgebraicNumber<C>> rfac 
044           = new GenPolynomialRing<RealAlgebraicNumber<C>>(rr,f.factory());
045        GenPolynomial<RealAlgebraicNumber<C>> p;
046        p = PolyUtilRoot.<C> convertToRealCoefficients(rfac,f);
047        RealAlgebraicNumber<C> a = PolyUtil.<RealAlgebraicNumber<C>> evaluateMain(rr,p,r);
048        return a.isZERO();
049    }
050
051
052    /**
053     * Real algebraic numbers.
054     * @param f univariate polynomial.
055     * @return a list of different real algebraic numbers.
056     */
057    public static <C extends GcdRingElem<C> & Rational> 
058           List<RealAlgebraicNumber<C>> realAlgebraicNumbers(GenPolynomial<C> f) {
059        RealRoots<C> rr = new RealRootsSturm<C>();
060        SquarefreeAbstract<C> engine = SquarefreeFactory.<C> getImplementation(f.ring.coFac);
061        Map<GenPolynomial<C>,Long> SF = engine.squarefreeFactors(f);
062        Set<GenPolynomial<C>> S = SF.keySet();
063        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
064        for (GenPolynomial<C> sp : S) {
065            List<Interval<C>> iv = rr.realRoots(sp);
066            for (Interval<C> I : iv) {
067                RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I);
068                RealAlgebraicNumber<C> rn = rar.getGenerator();
069                long mult = SF.get(sp);
070                for ( int i = 0; i < mult; i++ ) {
071                     list.add(rn);
072                }
073            }
074        }
075        return list;
076    }
077
078
079    /**
080     * Real algebraic numbers.
081     * @param f univariate polynomial.
082     * @param eps rational precision.
083     * @return a list of different real algebraic numbers.
084     */
085    public static <C extends GcdRingElem<C> & Rational> 
086           List<RealAlgebraicNumber<C>> realAlgebraicNumbers(GenPolynomial<C> f, BigRational eps) {
087        RealRoots<C> rr = new RealRootsSturm<C>();
088        SquarefreeAbstract<C> engine = SquarefreeFactory.<C> getImplementation(f.ring.coFac);
089        Map<GenPolynomial<C>,Long> SF = engine.squarefreeFactors(f);
090        Set<GenPolynomial<C>> S = SF.keySet();
091        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
092        for (GenPolynomial<C> sp : S) {
093            List<Interval<C>> iv = rr.realRoots(sp,eps);
094            for (Interval<C> I : iv) {
095                RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I);
096                rar.setEps(eps);
097                RealAlgebraicNumber<C> rn = rar.getGenerator();
098                long mult = SF.get(sp);
099                for ( int i = 0; i < mult; i++ ) {
100                     list.add(rn);
101                }
102            }
103        }
104        return list;
105    }
106
107
108    /**
109     * Real algebraic numbers from a field.
110     * @param f univariate polynomial.
111     * @return a list of different real algebraic numbers from a field.
112     */
113    public static <C extends GcdRingElem<C> & Rational> 
114           List<RealAlgebraicNumber<C>> realAlgebraicNumbersField(GenPolynomial<C> f) {
115        RealRoots<C> rr = new RealRootsSturm<C>();
116        FactorAbstract<C> engine = FactorFactory.<C> getImplementation(f.ring.coFac);
117        Map<GenPolynomial<C>,Long> SF = engine.baseFactors(f);
118        Set<GenPolynomial<C>> S = SF.keySet();
119        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
120        for (GenPolynomial<C> sp : S) {
121            List<Interval<C>> iv = rr.realRoots(sp);
122            for (Interval<C> I : iv) {
123                RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I, true);//field
124                RealAlgebraicNumber<C> rn = rar.getGenerator();
125                long mult = SF.get(sp);
126                for ( int i = 0; i < mult; i++ ) {
127                     list.add(rn);
128                }
129            }
130        }
131        return list;
132    }
133
134
135    /**
136     * Real algebraic numbers from a field.
137     * @param f univariate polynomial.
138     * @param eps rational precision.
139     * @return a list of different real algebraic numbers from a field.
140     */
141    public static <C extends GcdRingElem<C> & Rational> 
142           List<RealAlgebraicNumber<C>> realAlgebraicNumbersField(GenPolynomial<C> f, BigRational eps) {
143        RealRoots<C> rr = new RealRootsSturm<C>();
144        FactorAbstract<C> engine = FactorFactory.<C> getImplementation(f.ring.coFac);
145        Map<GenPolynomial<C>,Long> SF = engine.baseFactors(f);
146        Set<GenPolynomial<C>> S = SF.keySet();
147        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
148        for (GenPolynomial<C> sp : S) {
149            List<Interval<C>> iv = rr.realRoots(sp,eps);
150            for (Interval<C> I : iv) {
151                RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I, true);//field
152                rar.setEps(eps);
153                RealAlgebraicNumber<C> rn = rar.getGenerator();
154                long mult = SF.get(sp);
155                for ( int i = 0; i < mult; i++ ) {
156                     list.add(rn);
157                }
158            }
159        }
160        return list;
161    }
162
163
164    /**
165     * Real algebraic numbers from a irreducible polynomial.
166     * @param f univariate irreducible polynomial.
167     * @return a list of different real algebraic numbers from a field.
168     */
169    public static <C extends GcdRingElem<C> & Rational> 
170           List<RealAlgebraicNumber<C>> realAlgebraicNumbersIrred(GenPolynomial<C> f) {
171        RealRoots<C> rr = new RealRootsSturm<C>();
172        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
173        List<Interval<C>> iv = rr.realRoots(f);
174        for (Interval<C> I : iv) {
175            RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(f, I, true);//field
176            RealAlgebraicNumber<C> rn = rar.getGenerator();
177            list.add(rn);
178        }
179        return list;
180    }
181
182
183    /**
184     * Real algebraic numbers from a irreducible polynomial.
185     * @param f univariate irreducible polynomial.
186     * @param eps rational precision.
187     * @return a list of different real algebraic numbers from a field.
188     */
189    public static <C extends GcdRingElem<C> & Rational> 
190           List<RealAlgebraicNumber<C>> realAlgebraicNumbersIrred(GenPolynomial<C> f, BigRational eps) {
191        RealRoots<C> rr = new RealRootsSturm<C>();
192        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
193        List<Interval<C>> iv = rr.realRoots(f,eps);
194        for (Interval<C> I : iv) {
195            RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(f, I, true);//field
196            rar.setEps(eps);
197            RealAlgebraicNumber<C> rn = rar.getGenerator();
198            list.add(rn);
199        }
200        return list;
201    }
202
203
204    /**
205     * Is complex algebraic number a root of a polynomial.
206     * @param f univariate polynomial.
207     * @param r complex algebraic number.
208     * @return true, if f(r) == 0, else false;
209     */
210    public static <C extends GcdRingElem<C> & Rational> 
211           boolean isRoot(GenPolynomial<C> f, ComplexAlgebraicNumber<C> r) {
212        ComplexAlgebraicRing<C> cr = r.factory(); 
213        GenPolynomialRing<ComplexAlgebraicNumber<C>> cfac 
214           = new GenPolynomialRing<ComplexAlgebraicNumber<C>>(cr,f.factory());
215        GenPolynomial<ComplexAlgebraicNumber<C>> p;
216        p = PolyUtilRoot.<C> convertToComplexCoefficients(cfac,f);
217        ComplexAlgebraicNumber<C> a = PolyUtil.<ComplexAlgebraicNumber<C>> evaluateMain(cr,p,r);
218        return a.isZERO();
219    }
220
221
222    /**
223     * Is complex algebraic number a root of a complex polynomial.
224     * @param f univariate complex polynomial.
225     * @param r complex algebraic number.
226     * @return true, if f(r) == 0, else false;
227     */
228    public static <C extends GcdRingElem<C> & Rational> 
229           boolean isRootComplex(GenPolynomial<Complex<C>> f, ComplexAlgebraicNumber<C> r) {
230        ComplexAlgebraicRing<C> cr = r.factory(); 
231        GenPolynomialRing<ComplexAlgebraicNumber<C>> cfac 
232           = new GenPolynomialRing<ComplexAlgebraicNumber<C>>(cr,f.factory());
233        GenPolynomial<ComplexAlgebraicNumber<C>> p;
234        p = PolyUtilRoot.<C> convertToComplexCoefficientsFromComplex(cfac,f);
235        ComplexAlgebraicNumber<C> a = PolyUtil.<ComplexAlgebraicNumber<C>> evaluateMain(cr,p,r);
236        return a.isZERO();
237    }
238
239
240    /**
241     * Complex algebraic numbers.
242     * @param f univariate polynomial.
243     * @return a list of different complex algebraic numbers.
244     */
245    public static <C extends GcdRingElem<C> & Rational> 
246           List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbersComplex(GenPolynomial<Complex<C>> f) {
247        ComplexRoots<C> cr = new ComplexRootsSturm<C>(f.ring.coFac);
248        SquarefreeAbstract<Complex<C>> engine = SquarefreeFactory
249                .<Complex<C>> getImplementation(f.ring.coFac);
250        Map<GenPolynomial<Complex<C>>,Long> SF = engine.squarefreeFactors(f);
251        Set<GenPolynomial<Complex<C>>> S = SF.keySet();
252        List<ComplexAlgebraicNumber<C>> list = new ArrayList<ComplexAlgebraicNumber<C>>();
253        for (GenPolynomial<Complex<C>> sp : S) {
254            List<Rectangle<C>> iv = cr.complexRoots(sp);
255            for (Rectangle<C> I : iv) {
256                ComplexAlgebraicRing<C> car = new ComplexAlgebraicRing<C>(sp, I);
257                ComplexAlgebraicNumber<C> cn = car.getGenerator();
258                long mult = SF.get(sp);
259                for ( int i = 0; i < mult; i++ ) {
260                     list.add(cn);
261                }
262            }
263        }
264        return list;
265    }
266
267
268    /**
269     * Complex algebraic numbers.
270     * @param f univariate polynomial.
271     * @param eps rational precision.
272     * @return a list of different complex algebraic numbers.
273     */
274    public static <C extends GcdRingElem<C> & Rational> 
275           List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbersComplex(GenPolynomial<Complex<C>> f, BigRational eps) {
276        ComplexRoots<C> cr = new ComplexRootsSturm<C>(f.ring.coFac);
277        SquarefreeAbstract<Complex<C>> engine = SquarefreeFactory
278                .<Complex<C>> getImplementation(f.ring.coFac);
279        Map<GenPolynomial<Complex<C>>,Long> SF = engine.squarefreeFactors(f);
280        Set<GenPolynomial<Complex<C>>> S = SF.keySet();
281        List<ComplexAlgebraicNumber<C>> list = new ArrayList<ComplexAlgebraicNumber<C>>();
282        for (GenPolynomial<Complex<C>> sp : S) {
283            List<Rectangle<C>> iv = cr.complexRoots(sp);
284            for (Rectangle<C> I : iv) {
285                Rectangle<C> Iv = I;
286                try {
287                    Iv = cr.complexRootRefinement(I,sp,eps);
288                } catch (InvalidBoundaryException e) {
289                    e.printStackTrace();
290                }
291                ComplexAlgebraicRing<C> car = new ComplexAlgebraicRing<C>(sp, Iv);
292                car.setEps(eps);
293                ComplexAlgebraicNumber<C> cn = car.getGenerator();
294                long mult = SF.get(sp);
295                for ( int i = 0; i < mult; i++ ) {
296                     list.add(cn);
297                }
298            }
299        }
300        return list;
301    }
302
303
304    /**
305     * Complex algebraic numbers.
306     * @param f univariate (rational) polynomial.
307     * @return a list of different complex algebraic numbers.
308     */
309    public static <C extends GcdRingElem<C> & Rational> 
310           List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbers(GenPolynomial<C> f) {
311        if ( f.ring.coFac instanceof Complex ) {
312            throw new IllegalArgumentException("f already has Complex coefficients " + f.ring);
313        }
314        if ( f.ring.coFac instanceof ComplexAlgebraicRing ) {
315            throw new UnsupportedOperationException("unsupported ComplexAlgebraicRing coefficients " + f.ring);
316        }
317        ComplexRing<C> cr = new ComplexRing<C>( f.ring.coFac );
318        GenPolynomialRing<Complex<C>> fac = new GenPolynomialRing<Complex<C>>(cr,f.ring);
319        GenPolynomial<Complex<C>> fc = PolyUtil.<C>complexFromAny(fac,f); 
320        return complexAlgebraicNumbersComplex(fc);
321    }
322
323
324    /**
325     * Complex algebraic numbers.
326     * @param f univariate (rational) polynomial.
327     * @param eps rational precision.
328     * @return a list of different complex algebraic numbers.
329     */
330    public static <C extends GcdRingElem<C> & Rational> 
331                             List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbers(GenPolynomial<C> f, BigRational eps) {
332        if ( f.ring.coFac instanceof Complex ) {
333            throw new IllegalArgumentException("f already has Complex coefficients " + f.ring);
334        }
335        if ( f.ring.coFac instanceof ComplexAlgebraicRing ) {
336            throw new UnsupportedOperationException("unsupported ComplexAlgebraicRing coefficients " + f.ring);
337        }
338        ComplexRing<C> cr = new ComplexRing<C>( f.ring.coFac );
339        GenPolynomialRing<Complex<C>> fac = new GenPolynomialRing<Complex<C>>(cr,f.ring);
340        GenPolynomial<Complex<C>> fc = PolyUtil.<C>complexFromAny(fac,f); 
341        return complexAlgebraicNumbersComplex(fc,eps);
342    }
343
344}