Source code

001/*
002 * $Id: RootFactory.java 5311 2015-10-25 22:28:29Z 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 (Map.Entry<GenPolynomial<C>,Long> me : SF.entrySet()) {
065            GenPolynomial<C> sp = me.getKey();
066            List<Interval<C>> iv = rr.realRoots(sp);
067            for (Interval<C> I : iv) {
068                RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I);
069                RealAlgebraicNumber<C> rn = rar.getGenerator();
070                long mult = me.getValue();
071                for ( int i = 0; i < mult; i++ ) {
072                     list.add(rn);
073                }
074            }
075        }
076        return list;
077    }
078
079
080    /**
081     * Real algebraic numbers.
082     * @param f univariate polynomial.
083     * @param eps rational precision.
084     * @return a list of different real algebraic numbers.
085     */
086    public static <C extends GcdRingElem<C> & Rational> 
087           List<RealAlgebraicNumber<C>> realAlgebraicNumbers(GenPolynomial<C> f, BigRational eps) {
088        RealRoots<C> rr = new RealRootsSturm<C>();
089        SquarefreeAbstract<C> engine = SquarefreeFactory.<C> getImplementation(f.ring.coFac);
090        Map<GenPolynomial<C>,Long> SF = engine.squarefreeFactors(f);
091        //Set<GenPolynomial<C>> S = SF.keySet();
092        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
093        for (Map.Entry<GenPolynomial<C>,Long> me : SF.entrySet()) {
094            GenPolynomial<C> sp = me.getKey();
095            List<Interval<C>> iv = rr.realRoots(sp,eps);
096            for (Interval<C> I : iv) {
097                RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I);
098                rar.setEps(eps);
099                RealAlgebraicNumber<C> rn = rar.getGenerator();
100                long mult = me.getValue();
101                for ( int i = 0; i < mult; i++ ) {
102                     list.add(rn);
103                }
104            }
105        }
106        return list;
107    }
108
109
110    /**
111     * Real algebraic numbers from a field.
112     * @param f univariate polynomial.
113     * @return a list of different real algebraic numbers from a field.
114     */
115    public static <C extends GcdRingElem<C> & Rational> 
116           List<RealAlgebraicNumber<C>> realAlgebraicNumbersField(GenPolynomial<C> f) {
117        RealRoots<C> rr = new RealRootsSturm<C>();
118        FactorAbstract<C> engine = FactorFactory.<C> getImplementation(f.ring.coFac);
119        Map<GenPolynomial<C>,Long> SF = engine.baseFactors(f);
120        //Set<GenPolynomial<C>> S = SF.keySet();
121        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
122        for (Map.Entry<GenPolynomial<C>,Long> me : SF.entrySet()) {
123            GenPolynomial<C> sp = me.getKey();
124            List<Interval<C>> iv = rr.realRoots(sp);
125            for (Interval<C> I : iv) {
126                RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I, true);//field
127                RealAlgebraicNumber<C> rn = rar.getGenerator();
128                long mult = me.getValue();
129                for ( int i = 0; i < mult; i++ ) {
130                     list.add(rn);
131                }
132            }
133        }
134        return list;
135    }
136
137
138    /**
139     * Real algebraic numbers from a field.
140     * @param f univariate polynomial.
141     * @param eps rational precision.
142     * @return a list of different real algebraic numbers from a field.
143     */
144    public static <C extends GcdRingElem<C> & Rational> 
145           List<RealAlgebraicNumber<C>> realAlgebraicNumbersField(GenPolynomial<C> f, BigRational eps) {
146        RealRoots<C> rr = new RealRootsSturm<C>();
147        FactorAbstract<C> engine = FactorFactory.<C> getImplementation(f.ring.coFac);
148        Map<GenPolynomial<C>,Long> SF = engine.baseFactors(f);
149        //Set<GenPolynomial<C>> S = SF.keySet();
150        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
151        for (Map.Entry<GenPolynomial<C>,Long> me : SF.entrySet()) {
152            GenPolynomial<C> sp = me.getKey();
153            List<Interval<C>> iv = rr.realRoots(sp,eps);
154            for (Interval<C> I : iv) {
155                RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I, true);//field
156                rar.setEps(eps);
157                RealAlgebraicNumber<C> rn = rar.getGenerator();
158                long mult = me.getValue();
159                for ( int i = 0; i < mult; i++ ) {
160                     list.add(rn);
161                }
162            }
163        }
164        return list;
165    }
166
167
168    /**
169     * Real algebraic numbers from a irreducible polynomial.
170     * @param f univariate irreducible polynomial.
171     * @return a list of different real algebraic numbers from a field.
172     */
173    public static <C extends GcdRingElem<C> & Rational> 
174           List<RealAlgebraicNumber<C>> realAlgebraicNumbersIrred(GenPolynomial<C> f) {
175        RealRoots<C> rr = new RealRootsSturm<C>();
176        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
177        List<Interval<C>> iv = rr.realRoots(f);
178        for (Interval<C> I : iv) {
179            RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(f, I, true);//field
180            RealAlgebraicNumber<C> rn = rar.getGenerator();
181            list.add(rn);
182        }
183        return list;
184    }
185
186
187    /**
188     * Real algebraic numbers from a irreducible polynomial.
189     * @param f univariate irreducible polynomial.
190     * @param eps rational precision.
191     * @return a list of different real algebraic numbers from a field.
192     */
193    public static <C extends GcdRingElem<C> & Rational> 
194           List<RealAlgebraicNumber<C>> realAlgebraicNumbersIrred(GenPolynomial<C> f, BigRational eps) {
195        RealRoots<C> rr = new RealRootsSturm<C>();
196        List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>();
197        List<Interval<C>> iv = rr.realRoots(f,eps);
198        for (Interval<C> I : iv) {
199            RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(f, I, true);//field
200            rar.setEps(eps);
201            RealAlgebraicNumber<C> rn = rar.getGenerator();
202            list.add(rn);
203        }
204        return list;
205    }
206
207
208    /**
209     * Is complex algebraic number a root of a polynomial.
210     * @param f univariate polynomial.
211     * @param r complex algebraic number.
212     * @return true, if f(r) == 0, else false;
213     */
214    public static <C extends GcdRingElem<C> & Rational> 
215           boolean isRoot(GenPolynomial<C> f, ComplexAlgebraicNumber<C> r) {
216        ComplexAlgebraicRing<C> cr = r.factory(); 
217        GenPolynomialRing<ComplexAlgebraicNumber<C>> cfac 
218           = new GenPolynomialRing<ComplexAlgebraicNumber<C>>(cr,f.factory());
219        GenPolynomial<ComplexAlgebraicNumber<C>> p;
220        p = PolyUtilRoot.<C> convertToComplexCoefficients(cfac,f);
221        ComplexAlgebraicNumber<C> a = PolyUtil.<ComplexAlgebraicNumber<C>> evaluateMain(cr,p,r);
222        return a.isZERO();
223    }
224
225
226    /**
227     * Is complex algebraic number a root of a complex polynomial.
228     * @param f univariate complex polynomial.
229     * @param r complex algebraic number.
230     * @return true, if f(r) == 0, else false;
231     */
232    public static <C extends GcdRingElem<C> & Rational> 
233           boolean isRootComplex(GenPolynomial<Complex<C>> f, ComplexAlgebraicNumber<C> r) {
234        ComplexAlgebraicRing<C> cr = r.factory(); 
235        GenPolynomialRing<ComplexAlgebraicNumber<C>> cfac 
236           = new GenPolynomialRing<ComplexAlgebraicNumber<C>>(cr,f.factory());
237        GenPolynomial<ComplexAlgebraicNumber<C>> p;
238        p = PolyUtilRoot.<C> convertToComplexCoefficientsFromComplex(cfac,f);
239        ComplexAlgebraicNumber<C> a = PolyUtil.<ComplexAlgebraicNumber<C>> evaluateMain(cr,p,r);
240        return a.isZERO();
241    }
242
243
244    /**
245     * Complex algebraic numbers.
246     * @param f univariate polynomial.
247     * @return a list of different complex algebraic numbers.
248     */
249    public static <C extends GcdRingElem<C> & Rational> 
250           List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbersComplex(GenPolynomial<Complex<C>> f) {
251        ComplexRoots<C> cr = new ComplexRootsSturm<C>(f.ring.coFac);
252        SquarefreeAbstract<Complex<C>> engine = SquarefreeFactory
253                .<Complex<C>> getImplementation(f.ring.coFac);
254        Map<GenPolynomial<Complex<C>>,Long> SF = engine.squarefreeFactors(f);
255        //Set<GenPolynomial<Complex<C>>> S = SF.keySet();
256        List<ComplexAlgebraicNumber<C>> list = new ArrayList<ComplexAlgebraicNumber<C>>();
257        for (Map.Entry<GenPolynomial<Complex<C>>,Long> me : SF.entrySet()) {
258            GenPolynomial<Complex<C>> sp = me.getKey();
259            List<Rectangle<C>> iv = cr.complexRoots(sp);
260            for (Rectangle<C> I : iv) {
261                ComplexAlgebraicRing<C> car = new ComplexAlgebraicRing<C>(sp, I);
262                ComplexAlgebraicNumber<C> cn = car.getGenerator();
263                long mult = me.getValue();
264                for ( int i = 0; i < mult; i++ ) {
265                     list.add(cn);
266                }
267            }
268        }
269        return list;
270    }
271
272
273    /**
274     * Complex algebraic numbers.
275     * @param f univariate polynomial.
276     * @param eps rational precision.
277     * @return a list of different complex algebraic numbers.
278     */
279    public static <C extends GcdRingElem<C> & Rational> 
280           List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbersComplex(GenPolynomial<Complex<C>> f, BigRational eps) {
281        ComplexRoots<C> cr = new ComplexRootsSturm<C>(f.ring.coFac);
282        SquarefreeAbstract<Complex<C>> engine = SquarefreeFactory
283                .<Complex<C>> getImplementation(f.ring.coFac);
284        Map<GenPolynomial<Complex<C>>,Long> SF = engine.squarefreeFactors(f);
285        //Set<GenPolynomial<Complex<C>>> S = SF.keySet();
286        List<ComplexAlgebraicNumber<C>> list = new ArrayList<ComplexAlgebraicNumber<C>>();
287        for (Map.Entry<GenPolynomial<Complex<C>>,Long> me : SF.entrySet()) {
288            GenPolynomial<Complex<C>> sp = me.getKey();
289            List<Rectangle<C>> iv = cr.complexRoots(sp);
290            for (Rectangle<C> I : iv) {
291                Rectangle<C> Iv = I;
292                try {
293                    Iv = cr.complexRootRefinement(I,sp,eps);
294                } catch (InvalidBoundaryException e) {
295                    e.printStackTrace();
296                }
297                ComplexAlgebraicRing<C> car = new ComplexAlgebraicRing<C>(sp, Iv);
298                car.setEps(eps);
299                ComplexAlgebraicNumber<C> cn = car.getGenerator();
300                long mult = me.getValue();
301                for ( int i = 0; i < mult; i++ ) {
302                     list.add(cn);
303                }
304            }
305        }
306        return list;
307    }
308
309
310    /**
311     * Complex algebraic numbers.
312     * @param f univariate (rational) polynomial.
313     * @return a list of different complex algebraic numbers.
314     */
315    public static <C extends GcdRingElem<C> & Rational> 
316           List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbers(GenPolynomial<C> f) {
317        if ( f.ring.coFac instanceof Complex ) {
318            throw new IllegalArgumentException("f already has Complex coefficients " + f.ring);
319        }
320        if ( f.ring.coFac instanceof ComplexAlgebraicRing ) {
321            throw new UnsupportedOperationException("unsupported ComplexAlgebraicRing coefficients " + f.ring);
322        }
323        ComplexRing<C> cr = new ComplexRing<C>( f.ring.coFac );
324        GenPolynomialRing<Complex<C>> fac = new GenPolynomialRing<Complex<C>>(cr,f.ring);
325        GenPolynomial<Complex<C>> fc = PolyUtil.<C>complexFromAny(fac,f); 
326        return complexAlgebraicNumbersComplex(fc);
327    }
328
329
330    /**
331     * Complex algebraic numbers.
332     * @param f univariate (rational) polynomial.
333     * @param eps rational precision.
334     * @return a list of different complex algebraic numbers.
335     */
336    public static <C extends GcdRingElem<C> & Rational> 
337                             List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbers(GenPolynomial<C> f, BigRational eps) {
338        if ( f.ring.coFac instanceof Complex ) {
339            throw new IllegalArgumentException("f already has Complex coefficients " + f.ring);
340        }
341        if ( f.ring.coFac instanceof ComplexAlgebraicRing ) {
342            throw new UnsupportedOperationException("unsupported ComplexAlgebraicRing coefficients " + f.ring);
343        }
344        ComplexRing<C> cr = new ComplexRing<C>( f.ring.coFac );
345        GenPolynomialRing<Complex<C>> fac = new GenPolynomialRing<Complex<C>>(cr,f.ring);
346        GenPolynomial<Complex<C>> fc = PolyUtil.<C>complexFromAny(fac,f); 
347        return complexAlgebraicNumbersComplex(fc,eps);
348    }
349
350}